Next

__
TR21-138
| 23rd September 2021
__

Rahul Santhanam, Iddo Tzameret#### Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity

__
TR21-137
| 14th September 2021
__

Xuangui Huang, Peter Ivanov, Emanuele Viola#### Affine extractors and AC0-Parity

__
TR21-136
| 13th September 2021
__

Gil Cohen, Tal Yankovitz#### LCC and LDC: Tailor-made distance amplification and a refined separation

Next

Rahul Santhanam, Iddo Tzameret

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 >>>

Xuangui Huang, Peter Ivanov, Emanuele Viola

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 >>>

Gil Cohen, Tal Yankovitz

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