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-104 | 18th July 2022
Nader Bshouty

On One-Sided Testing Affine Subspaces

Revisions: 1

We study the query complexity of one-sided $\epsilon$-testing the class of Boolean functions $f:F^n\to \{0,1\}$ that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where $F$ is any finite field. We give a polynomial-time $\epsilon$-testers that ask $\tilde O(1/\epsilon)$ queries. This improves the query complexity $\tilde O(|F|/\epsilon)$ ... more >>>


TR22-103 | 15th July 2022
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Almost Chor--Goldreich Sources and Adversarial Random Walks

Revisions: 2

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>


TR22-102 | 15th July 2022
Venkatesan Guruswami, Xin Lyu, Xiuhan Wang

Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness

In the range avoidance problem, the input is a multi-output Boolean circuit with more outputs than inputs, and the goal is to find a string outside its range (which is guaranteed to exist). We show that well-known explicit construction questions such as finding binary linear codes achieving the Gilbert-Varshamov bound ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint