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

TR21-095 | 8th July 2021
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Oliveira

LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic

We investigate randomized LEARN-uniformity, which captures the power of randomness and equivalence queries (EQ) in the construction of Boolean circuits for an explicit problem. This is an intermediate notion between P-uniformity and non-uniformity motivated by connections to learning, complexity, and logic. Building on a number of techniques, we establish the ... more >>>


TR21-094 | 6th July 2021
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

New Non-FPT Lower Bounds for Some Arithmetic Formulas

An Algebraic Formula for a polynomial $P\in F[x_1,\ldots,x_N]$ is an algebraic expression for $P(x_1,\ldots,x_N)$ using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class $\mathrm{NC}^1.$ Proving lower bounds against this model is thus an important problem.

It is known that, to prove ... more >>>


TR21-093 | 1st July 2021
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan

Bounded Indistinguishability for Simple Sources

Revisions: 1

A pair of sources $\mathbf{X},\mathbf{Y}$ over $\{0,1\}^n$ are $k$-indistinguishable if their projections to any $k$ coordinates are identically distributed. Can some $\mathit{AC^0}$ function distinguish between two such sources when $k$ is big, say $k=n^{0.1}$? Braverman's theorem (Commun. ACM 2011) implies a negative answer when $\mathbf{X}$ is uniform, whereas Bogdanov et ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint