Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with composition:
TR98-050 | 6th July 1998
Farid Ablayev, Svetlana Ablayeva

A Discrete Approximation and Communication Complexity Approach to the Superposition Problem

The superposition (or composition) problem is a problem of
representation of a function $f$ by a superposition of "simpler" (in a
different meanings) set $\Omega$ of functions. In terms of circuits
theory this means a possibility of computing $f$ by a finite circuit
with 1 fan-out gates $\Omega$ of functions. ... more >>>

TR09-042 | 5th May 2009
Irit Dinur, Prahladh Harsha

Composition of low-error 2-query PCPs using decodable PCPs

The main result of this paper is a simple, yet generic, composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored ... more >>>

TR11-072 | 1st May 2011
Danny Hermelin, Xi Wu

Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization

Revisions: 1

We introduce a new form of composition called \emph{weak composition} that allows us to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let $d \ge 2$ be some constant and let $L_1, L_2 \subseteq \{0,1\}^* \times \N$ be two parameterized problems where the unparameterized version of $L_1$ is \NP-hard. ... more >>>

TR13-190 | 28th December 2013
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Revisions: 11

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the ... more >>>

TR15-085 | 23rd May 2015
Irit Dinur, Prahladh Harsha, Guy Kindler

Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition

We show that every language in NP has a PCP verifier that tosses $O(\log n)$ random coins, has perfect completeness, and a soundness error of at most $1/poly(n)$, while making at most $O(poly\log\log n)$ queries into a proof over an alphabet of size at most $n^{1/poly\log\log n}$. Previous constructions that ... more >>>

TR17-146 | 1st October 2017
Or Meir

On Derandomized Composition of Boolean Functions

Revisions: 3

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

TR18-160 | 12th September 2018
Anna Gal, Avishay Tal, Adrian Trejo Nuñez

Cubic Formula Size Lower Bounds Based on Compositions with Majority

We define new functions based on the Andreev function and prove that they require $n^{3}/polylog(n)$ formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the ... more >>>

ISSN 1433-8092 | Imprint