Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Small depth circuits:
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 >>>

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