Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > GUY WEISSENBERG:
All reports by Author Guy Weissenberg:

TR26-227 | 4th October 2026
Guy Weissenberg

Interactive Proof of Proximity for Bipartiteness without Mixing

Testing whether a bounded-degree $n$-vertex graph is bipartite or far from bipartite requires $\widetilde\Theta(\sqrt n)$ queries (Goldreich--Ron, Combinatorica'99, Algorithmica'02). An interactive proof of proximity (IPP) is a hybrid model of property testing and interactive proofs: the verifier faces the same task with the same query access, but it now interacts ... more >>>


TR25-217 | 16th December 2025
Tom Gur, Dor Minzer, Guy Weissenberg, Kai Zhe Zheng

$3$-Query RLDCs are Strictly Stronger than $3$-Query LDCs

We construct $3$-query relaxed locally decodable codes (RLDCs) with constant alphabet size and length $\tilde{O}(k^2)$ for $k$-bit messages. Combined with the lower bound of $\tilde{\Omega}(k^3)$ of [Alrabiah, Guruswami, Kothari, Manohar, STOC 2023] on the length of locally decodable codes (LDCs) with the same parameters, we obtain a separation between RLDCs ... more >>>




ISSN 1433-8092 | Imprint