Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CONSTANT DEPTH CIRCUITS:
Reports tagged with Constant depth circuits:
TR07-050 | 25th May 2007

#### Discrepancy and the power of bottom fan-in in depth-three circuits

We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'Number on the Forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the Degree-Discrepancy Lemma in the recent work of Sherstov (STOC'07). ... more >>>

TR08-001 | 5th January 2008
Ran Raz

#### Elusive Functions and Lower Bounds for Arithmetic Circuits

A basic fact in linear algebra is that the image of the curve
$f(x)=(x^1,x^2,x^3,...,x^m)$, say over $C$, is not contained in any
$m-1$ dimensional affine subspace of $C^m$. In other words, the image
of $f$ is not contained in the image of any polynomial-mapping
$G:C^{m-1} ---> C^m$ ... more >>>

TR13-102 | 17th July 2013
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

#### Small Depth Proof Systems

A proof system for a language $L$ is a function $f$ such that Range$(f)$ is exactly $L$. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by ... more >>>

TR17-129 | 27th August 2017
Or Meir

#### An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds

Revisions: 8

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations:
Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean
function $f$ there is a corresponding communication problem $\mathrm{KW}_{f}$,
more >>>

TR17-193 | 31st December 2017
Oded Goldreich, Avishay Tal

#### On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions

We consider new complexity measures for the model of multilinear circuits with general multilinear gates introduced by Goldreich and Wigderson (ECCC, 2013).
These complexity measures are related to the size of canonical constant-depth Boolean circuits, which extend the definition of canonical depth-three Boolean circuits.
We obtain matching lower and upper ... more >>>

TR18-156 | 8th September 2018
Mark Bun, Robin Kothari, Justin Thaler

#### Quantum algorithms and approximating polynomials for composed functions with shared inputs

Revisions: 1

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give ... more >>>

TR20-094 | 24th June 2020
Ronen Shaltiel

#### Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

Yao's XOR lemma states that for every function $f:\set{0,1}^k \ar \set{0,1}$, if $f$ has hardness $2/3$ for $P/poly$ (meaning that for every circuit $C$ in $P/poly$, $\Pr[C(X)=f(X)] \le 2/3$ on a uniform input $X$), then the task of computing $f(X_1) \oplus \ldots \oplus f(X_t)$ for sufficiently large $t$ has hardness ... more >>>

ISSN 1433-8092 | Imprint