Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KRW COMPOSITION CONJECTURE:
Reports tagged with KRW composition conjecture:
TR16-035 | 11th March 2016
Irit Dinur, Or Meir

Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

Revisions: 2

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected'' with respect to the composition of functions $f\circ g$. They showed that this conjecture, ... more >>>

TR17-146 | 1st October 2017
Or Meir

On Derandomized Composition of Boolean Functions

Revisions: 4

The composition of two Boolean functions $f:\left\{0,1\right\}^{m}\to\left\{0,1\right\}$, $g:\left\{0,1\right\}^{n}\to\left\{0,1\right\}$
is the function $f \diamond g$ that takes as inputs $m$ strings $x_{1},\ldots,x_{m}\in\left\{0,1\right\}^{n}$
and computes
$(f \diamond g)(x_{1},\ldots,x_{m})=f\left(g(x_{1}),\ldots,g(x_{m})\right).$
This operation has been used several times for amplifying different
hardness measures of $f$ and $g$. This comes at a cost: the ... more >>>

TR17-148 | 6th October 2017
Or Meir, Avishay Tal

The Choice and Agreement Problems of a Random Function

Revisions: 3

The direct-sum question is a classical question that asks whether
performing a task on $m$ independent inputs is $m$ times harder
than performing it on a single input. In order to study this question,
Beimel et. al (Computational Complexity 23(1), 2014) introduced the following related problems:

* The choice ... more >>>

TR19-120 | 11th September 2019
Or Meir

Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation

Revisions: 1

One of the major open problems in complexity theory is proving super-logarithmic
lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions $f ... more >>> TR20-099 | 6th July 2020 Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere KRW Composition Theorems via Lifting Revisions: 1 One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e.,$\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions$f ... more >>>

ISSN 1433-8092 | Imprint