Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SWITCHING LEMMA:
Reports tagged with switching lemma:
TR03-004 | 24th December 2002

#### Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games

We present a simple proof of the bounded-depth Frege lower bounds of
Pitassi et. al. and Krajicek et. al. for the pigeonhole
principle. Our method uses the interpretation of proofs as two player
games given by Pudlak and Buss. Our lower bound is conceptually
simpler than previous ones, and relies ... more >>>

TR05-043 | 5th April 2005
Emanuele Viola

#### Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates

We exhibit an explicitly computable pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>>

TR12-116 | 13th September 2012
Luca Trevisan

#### A Derandomized Switching Lemma and an Improved Derandomization of AC0

Revisions: 1

We describe a new pseudorandom generator for AC0. Our generator $\epsilon$-fools circuits of depth $d$ and size $M$ and uses a seed of length $\tilde O( \log^{d+4} M/\epsilon)$. The previous best construction for $d \geq 3$ was due to Nisan, and had seed length $O(\log^{2d+6} M/\epsilon)$.
A seed length of ... more >>>

TR13-152 | 7th November 2013
Oded Goldreich, Avi Wigderson

#### On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

{\em Does derandomization of probabilistic algorithms become easier when the number of `bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ... more >>>

TR17-142 | 21st September 2017

#### On small-depth Frege proofs for Tseitin for grids

Revisions: 1

We prove that a small-depth Frege refutation of the Tseitin contradiction
on the grid requires subexponential size.
We conclude that polynomial size Frege refutations
of the Tseitin contradiction must use formulas of almost
logarithmic depth.

more >>>

TR18-040 | 21st February 2018
Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan

#### Non-Malleable Codes for Small-Depth Circuits

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay ... more >>>

TR19-137 | 24th September 2019
Shachar Lovett, Kewen Wu, Jiapeng Zhang

#### Decision list compression by mild random restrictions

Revisions: 1

A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whole term is satisfied by the input. Decision ... more >>>

TR20-182 | 3rd December 2020
Zander Kelley

#### An Improved Derandomization of the Switching Lemma

Revisions: 1

We prove a new derandomization of Håstad's switching lemma, showing how to efficiently generate restrictions satisfying the switching lemma for DNF or CNF formulas of size $m$ using only $\widetilde{O}(\log m)$ random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing ... more >>>

TR21-161 | 16th November 2021
Shuichi Hirahara, Mikito Nanashima

#### On Worst-Case Learning in Relativized Heuristica

A PAC learning model involves two worst-case requirements: a learner must learn all functions in a class on all example distributions. However, basing the hardness of learning on NP-hardness has remained a key challenge for decades. In fact, recent progress in computational complexity suggests the possibility that a weaker assumption ... more >>>

TR22-021 | 19th February 2022
Xin Lyu

#### Improved Pseudorandom Generators for $\mathrm{AC}^0$ Circuits

We give PRG for depth-$d$, size-$m$ $\mathrm{AC}^0$ circuits with seed length $O(\log^{d-1}(m)\log(m/\varepsilon)\log\log(m))$. Our PRG improves on previous work [TX13, ST19, Kel21] from various aspects. It has optimal dependence on $\frac{1}{\varepsilon}$ and is only one “$\log\log(m)$” away from the lower bound barrier. For the case of $d=2$, the seed length tightly ... more >>>

ISSN 1433-8092 | Imprint