Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SWITCHING LEMMA:
Reports tagged with switching lemma:
TR03-004 | 24th December 2002
Eli Ben-Sasson, Prahladh Harsha

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
Johan Håstad

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


TR22-182 | 16th December 2022
Prahladh Harsha, Tulasi mohan Molli, A. Shankar

Criticality of AC0-Formulae

Revisions: 1

Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function $f : \{0, 1\}^n\to \{0, 1\}$ is the minimum $\lambda \geq 1$ such that for all positive integers $t$,
\[Pr_{\rho\sim R_p} [\text{DT}_{\text{depth}}(f|_\rho) \geq t] \leq (p\lambda)^t.\]
.
Håstad’s celebrated switching lemma ... more >>>


TR23-042 | 3rd April 2023
Johan Håstad

On small-depth Frege proofs for PHP

We study Frege proofs for the one-to-one graph Pigeon Hole Principle
defined on the $n\times n$ grid where $n$ is odd.
We are interested in the case where each formula
in the proof is a depth $d$ formula in the basis given by
$\land$, $\lor$, and $\neg$. We prove that ... more >>>


TR23-045 | 13th April 2023
Vinayak Kumar

Tight Correlation Bounds for Circuits Between AC0 and TC0

Revisions: 1

We initiate the study of generalized $AC^0$ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight $\ge k$ (up to negations of the input bits), which we denote $GC^0(k)$. The gate set of this class includes biased LTFs like the $k$-$OR$ ... more >>>




ISSN 1433-8092 | Imprint