Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR22-148 | 11th November 2022
Peter Ivanov, Raghu Meka, Emanuele Viola

Efficient resilient functions

An $n$-bit boolean function is resilient to coalitions of size $q$
if no fixed set of $q$ bits is likely to influence the value of the
function when the other $n-q$ bits are chosen uniformly at random,
even though the function is nearly balanced. We construct explicit
functions resilient to ... more >>>


TR22-147 | 10th November 2022
Samir Datta, Chetan Gupta

Evaluating Monotone Circuits on Surfaces

Revisions: 3

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be ... more >>>


TR22-146 | 9th November 2022
Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai

Interactive Coding with Small Memory

In this work, we design an interactive coding scheme that converts any two party interactive protocol $\Pi$ into another interactive protocol $\Pi'$, such that even if errors are introduced during the execution of $\Pi'$, the parties are able to determine what the outcome of running $\Pi$ would be in an ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint