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

TR24-042 | 22nd February 2024
Lisa Jaser, Jacobo Toran

Pebble Games and Algebraic Proof Systems Meet Again

Comments: 1

Analyzing refutations of the well known
pebbling formulas we prove some new strong connections between pebble games and algebraic proof system, showing that
there is a parallelism between the reversible, black and black-white pebbling games on one side, and
the three algebraic proof systems NS, MC and ... more >>>


TR24-041 | 1st March 2024
Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

Launching Identity Testing into (Bounded) Space

In this work, we initiate the study of the space complexity of the Polynomial Identity Testing problem (PIT).
First, we observe that the majority of the existing (time-)efficient ``blackbox'' PIT algorithms already give rise to space-efficient ``whitebox'' algorithms for the respective classes of arithmetic formulas via a space-efficient ... more >>>


TR24-040 | 29th February 2024
Kuan Cheng, Ruiyang Wu

Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors

Revisions: 1

We study extractors computable in uniform $\mathrm{AC}^0$ and uniform $\mathrm{NC}^1$.

For the $\mathrm{AC}^0$ setting, we give a construction such that for every $k \ge n/ \mathrm{poly} \log n, \eps \ge 2^{-\mathrm{poly} \log n}$, it can extract $(1-\gamma)k$ randomness from an $(n, k)$ source for an arbitrary constant ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint