Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPOSITION:
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

#### 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
Dmytro 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: 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 >>>

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