Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
Next

TR21-138 | 23rd September 2021
Rahul Santhanam, Iddo Tzameret

#### Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity

We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally.

We give an explicit sequence of CNF formulas $\{\phi_n\}$ such that VNP$\neq$VP iff there are ... more >>>

TR21-137 | 14th September 2021
Xuangui Huang, Peter Ivanov, Emanuele Viola

#### Affine extractors and AC0-Parity

We study a simple and general template for constructing affine extractors by composing a linear transformation with resilient functions. Using this we show that good affine extractors can be computed by non-explicit circuits of various types, including AC0-Xor circuits: AC0 circuits with a layer of parity gates at the input. ... more >>>

TR21-136 | 13th September 2021
Gil Cohen, Tal Yankovitz

#### LCC and LDC: Tailor-made distance amplification and a refined separation

The Alon-Edmonds-Luby distance amplification procedure (FOCS 1995) is an algorithm that transforms a code with vanishing distance to a code with constant distance. AEL was invoked by Kopparty, Meir, Ron-Zewi, and Saraf (J. ACM 2017) for obtaining their state-of-the-art LDC, LCC and LTC. Cohen and Yankovitz (CCC 2021) devised a ... more >>>

Next

ISSN 1433-8092 | Imprint