Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

TR09-012 | 4th February 2009
Noga Alon, Shai Gutner

Balanced Hashing, Color Coding and Approximate Counting

Color Coding is an algorithmic technique for deciding efficiently
if a given input graph contains a path of a given length (or
another small subgraph of constant tree-width). Applications of the
method in computational biology motivate the study of similar
algorithms for counting the number of copies of a ... more >>>

TR06-088 | 9th July 2006
Per Austrin

Balanced Max 2-Sat might not be the hardest

We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate Max 2-Sat within $\alpha_{LLZ}^{-}+\epsilon$, where $0.9401 < \alpha_{LLZ}^{-} < 0.9402$ is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick.

This result is surprising considering the fact that balanced instances of Max 2-Sat, i.e. ... more >>>

TR11-068 | 27th April 2011
L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder

Balls and Bins: Smaller Hash Families and Faster Evaluation

A fundamental fact in the analysis of randomized algorithm is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n / \log \log n)$ balls. In various applications, however, the assumption that a truly random hash ... more >>>

TR17-162 | 26th October 2017
Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson

Barriers for Rank Methods in Arithmetic Complexity

Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than ... more >>>

TR15-180 | 4th November 2015
Bo Tang, Jiapeng Zhang

Barriers to Black-Box Constructions of Traitor Tracing Systems

Reducibility between different cryptographic primitives is a fundamental problem in modern cryptography. As one of the primitives, traitor tracing systems help content distributors recover the identities of users that collaborated in the pirate construction by tracing pirate decryption boxes. We present the first negative result on designing efficient traitor tracing ... more >>>

TR07-003 | 5th January 2007
Jin-Yi Cai, Pinyan Lu

Bases Collapse in Holographic Algorithms

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This ... more >>>

TR14-127 | 11th October 2014
Alexandros G. Dimakis, Anna Gal, Ankit Singh Rawat, Zhao Song

Batch Codes through Dense Graphs without Short Cycles

Consider a large database of $n$ data items that need to be stored using $m$ servers.
We study how to encode information so that a large number $k$ of read requests can be performed \textit{in parallel} while the rate remains constant (and ideally approaches one).
This problem is equivalent ... more >>>

TR01-078 | 6th November 2001
Matthias Krause

BDD-based Cryptanalysis of Keystream Generators

Many of the keystream generators which are used in practice are LFSR-based in the sense
that they produce the keystream according to a rule $y=C(L(x))$,
where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel
linear feedback shift registers (LFSRs),
and $C$ denotes ... more >>>

TR15-082 | 13th May 2015
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

Beating the random assignment on constraint satisfaction problems of bounded degree

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac{1}{2} + \Omega(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. ... more >>>

TR11-027 | 28th February 2011
Venkatesan Guruswami, Johan Hastad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar

Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation
resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ... more >>>

TR07-109 | 7th October 2007
Venkatesan Guruswami, Atri Rudra

Better Binary List-Decodable Codes via Multilevel Concatenation

We give a polynomial time construction of binary codes with the best
currently known trade-off between rate and error-correction
radius. Specifically, we obtain linear codes over fixed alphabets
that can be list decoded in polynomial time up to the so called
Blokh-Zyablov bound. Our work ... more >>>

TR17-072 | 25th April 2017
Eric Allender, Andreas Krebs, Pierre McKenzie

Better Complexity Bounds for Cost Register Machines

Revisions: 1

Cost register automata (CRA) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the semiring (N,min,+) can simulate polynomial time computation, proving along ... more >>>

TR03-080 | 12th November 2003
Venkatesan Guruswami

Better Extractors for Better Codes?

We present an explicit construction of codes that can be list decoded
from a fraction $(1-\eps)$ of errors in sub-exponential time and which
have rate $\eps/\log^{O(1)}(1/\eps)$. This comes close to the optimal
rate of $\Omega(\eps)$, and is the first sub-exponential complexity
construction to beat the rate of $O(\eps^2)$ achieved by ... more >>>

TR10-164 | 4th November 2010
Falk Unger

Better gates can make fault-tolerant computation impossible

Revisions: 1

We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with ... more >>>

TR12-123 | 28th September 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

Better pseudorandom generators from milder pseudorandom restrictions

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near optimal seed-length even in ... more >>>

TR04-090 | 3rd November 2004
Kazuyuki Amano, Akira Maruoka

Better Simulation of Exponential Threshold Weights by Polynomial Weights

We give an explicit construction of depth two threshold circuit with polynomial weights and $\tilde{O}(n^5)$ gates that computes an arbitrary threshold function. We also give the construction of such circuits with $O(n^3/\log n)$ gates computing the COMPARISON and CARRY functions, and that with $O(n^4/\log n)$ gates computing the ADDITION function. ... more >>>

TR14-125 | 9th October 2014
Anindya De

Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums

In this paper, we construct pseudorandom generators for the class of \emph{combinatorial sums}, a class of functions first studied by \cite{GMRZ13}
and defined as follows: A function $f: [m]^n \rightarrow \{0,1\}$ is said to be a combinatorial sum if there exists functions $f_1, \ldots, f_n: [m] \rightarrow \{0,1\}$ such that
more >>>

TR02-005 | 3rd January 2002
A. Pavan, Alan L. Selman

Bi-Immunity Separates Strong NP-Completeness Notions

We prove that if for some epsilon > 0 NP contains a set that is
DTIME(2^{n^{epsilon}})-bi-immune, then NP contains a set that 2-Turing
complete for NP but not 1-truth-table complete for NP. Lutz and Mayordomo
(LM96) and Ambos-Spies and Bentzien (AB00) previously obtained the
same consequence using strong ... more >>>

TR13-138 | 5th October 2013
Itai Benjamini, Gil Cohen, Igor Shinkar

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

Revisions: 1

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even $n \in {\mathbb N}$ there exists an explicit bijection $\psi \colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$ such that for every ... more >>>

TR15-096 | 5th June 2015
Abhishek Bhowmick, Shachar Lovett

Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial ... more >>>

TR16-112 | 18th July 2016
Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz

Bicovering: Covering edges with two small subsets of vertices

We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and that every edge $e$ belongs to either the graph induced by $A$ or to the graph induced by $B$. The ... more >>>

TR15-177 | 9th November 2015
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

Bipartite Perfect Matching is in quasi-NC

Revisions: 2

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>

TR09-005 | 7th December 2008
Emanuele Viola

Bit-Probe Lower Bounds for Succinct Data Structures

We prove lower bounds on the redundancy necessary to
represent a set $S$ of objects using a number of bits
close to the information-theoretic minimum $\log_2 |S|$,
while answering various queries by probing few bits. Our
main results are:

\item To represent $n$ ternary values $t \in
\zot^n$ in ... more >>>

TR07-042 | 7th May 2007
Zohar Karnin, Amir Shpilka

Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in

Revisions: 2 , Comments: 1

In this paper we consider the problem of determining whether an
unknown arithmetic circuit, for which we have oracle access,
computes the identically zero polynomial. Our focus is on depth-3
circuits with a bounded top fan-in. We obtain the following

1. A quasi-polynomial time deterministic black-box identity testing algorithm ... more >>>

TR01-050 | 24th June 2001
Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

We show that any concurrent zero-knowledge protocol for a non-trivial
language (i.e., for a language outside $\BPP$), whose security is proven
via black-box simulation, must use at least $\tilde\Omega(\log n)$
rounds of interaction. This result achieves a substantial improvement
over previous lower bounds, and is the first bound to rule ... more >>>

TR15-056 | 3rd April 2015
Sanjam Garg, Steve Lu, Rafail Ostrovsky

Black-Box Garbled RAM

Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations ... more >>>

TR11-046 | 2nd April 2011
Shubhangi Saraf, Ilya Volkovich

Black-Box Identity Testing of Depth-4 Multilinear Circuits

We study the problem of identity testing for multilinear $\Spsp(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. We give the first polynomial-time deterministic
identity testing algorithm for such circuits. Our results also hold in the black-box setting.

The running time of our algorithm is ... more >>>

TR10-102 | 12th May 2010
Per Kristian Lehre, Carsten Witt

Black-Box Search by Unbiased Variation

Revisions: 1

The complexity theory for black-box algorithms, introduced by
Droste et al. (2006), describes common limits on the efficiency of
a broad class of randomised search heuristics. There is an
obvious trade-off between the generality of the black-box model
and the strength of the bounds that can be proven in such ... more >>>

TR07-044 | 23rd April 2007
Philipp Hertel

Black-White Pebbling is PSPACE-Complete

The complexity of the Black-White Pebbling Game has remained an open problem for 30 years. It was devised to capture the power of non-deterministic space bounded computation. Since then it has been continuously studied and applied to problems in diverse areas of computer science including VLSI design and more recently ... more >>>

TR10-167 | 5th November 2010
Nitin Saxena, C. Seshadhri

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F.
It is a major open problem to design a deterministic polynomial time blackbox algorithm
that tests if C is identically zero.
Klivans & Spielman (STOC 2001) observed ... more >>>

TR09-032 | 16th April 2009
Neeraj Kayal, Shubhangi Saraf

Blackbox Polynomial Identity Testing for Depth 3 Circuits

We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001).

Our main technical result is ... more >>>

TR12-160 | 20th November 2012
Frederic Green, Daniel Kreymer, Emanuele Viola

Block-symmetric polynomials correlate with parity better than symmetric

We show that degree-$d$ block-symmetric polynomials in
$n$ variables modulo any odd $p$ correlate with parity
exponentially better than degree-$d$ symmetric
polynomials, if $n \ge c d^2 \log d$ and $d \in [0.995
\cdot p^t - 1,p^t)$ for some $t \ge 1$. For these
infinitely many degrees, our result ... more >>>

TR95-049 | 19th October 1995
Anna Gal, Avi Wigderson

Boolean complexity classes vs. their arithmetic analogs

This paper provides logspace and small circuit depth analogs
of the result of Valiant-Vazirani, which is a randomized (or
nonuniform) reduction from NP to its arithmetic analog ParityP.
We show a similar randomized reduction between the
Boolean classes NL and semi-unbounded fan-in Boolean circuits and
their arithmetic counterparts. These ... more >>>

TR13-191 | 26th December 2013
Petr Savicky

Boolean functions with a vertex-transitive group of automorphisms

Revisions: 2 , Comments: 1

A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. Several constructions of vertex-transitive functions and some of their properties are presented.

more >>>

TR13-141 | 8th October 2013
Leonid Gurvits

Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications

Revisions: 1

We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorthmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated with
boolean matrices with prescribed row and (uniformly bounded) column sums within simply ... more >>>

TR07-131 | 16th November 2007
Satyen Kale

Boosting and hard-core set constructions: a simplified approach

We revisit the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio. We present a boosting algorithm with a certain smoothness property that is necessary for hard-core set constructions: the distributions it generates do not put too much weight on any single example. We then use ... more >>>

TR13-135 | 27th September 2013
Scott Aaronson

BosonSampling Is Far From Uniform

Revisions: 2

BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random ... more >>>

TR04-121 | 7th December 2004
Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan

Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.

In this paper we study the complexity of Bounded Color
Multiplicity Graph Isomorphism (BCGI): the input is a pair of
vertex-colored graphs such that the number of vertices of a given
color in an input graph is bounded by $b$. We show that BCGI is in the
#L hierarchy ... more >>>

TR99-012 | 19th April 1999
Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

Bounded Depth Arithmetic Circuits: Counting and Closure

Comments: 1

Constant-depth arithmetic circuits have been defined and studied
in [AAD97,ABL98]; these circuits yield the function classes #AC^0
and GapAC^0. These function classes in turn provide new
characterizations of the computational power of threshold circuits,
and provide a link between the circuit classes AC^0 ... more >>>

TR16-099 | 13th June 2016
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

A Boolean function $f: \{0,1\}^n \to \{0,1\}$ is weighted symmetric if there exist a function $g: \mathbb{Z} \to \{0,1\}$ and integers $w_0, w_1, \ldots, w_n$ such that $f(x_1,\ldots,x_n) = g(w_0+\sum_{i=1}^n w_i x_i)$ holds.

In this paper, we present algorithms for the circuit satisfiability problem of bounded depth circuits with AND, ... more >>>

TR09-117 | 18th November 2009
Ilias Diakonikolas, Daniel Kane, Jelani Nelson

Bounded Independence Fools Degree-2 Threshold Functions

Revisions: 1

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of ... more >>>

TR09-016 | 21st February 2009
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

Bounded Independence Fools Halfspaces

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps)/\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>

TR16-169 | 3rd November 2016
Elad Haramaty, Chin Ho Lee, Emanuele Viola

Bounded independence plus noise fools products

Let $D$ be a $b$-wise independent distribution over
$\{0,1\}^m$. Let $E$ be the ``noise'' distribution over
$\{0,1\}^m$ where the bits are independent and each bit is 1
with probability $\eta/2$. We study which tests $f \colon
\{0,1\}^m \to [-1,1]$ are $\e$-fooled by $D+E$, i.e.,
$|\E[f(D+E)] - \E[f(U)]| \le \e$ where ... more >>>

TR16-102 | 4th July 2016
Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

Bounded independence vs. moduli

Let $k=k(n)$ be the largest integer such that there
exists a $k$-wise uniform distribution over $\zo^n$ that
is supported on the set $S_m := \{x \in \zo^n : \sum_i
x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We
show that $\Omega(n/m^2 \log m) \le k \le 2n/m + ... more >>>

TR15-182 | 13th November 2015
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

Bounded Indistinguishability and the Complexity of Recovering Secrets

Revisions: 1

We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by ... more >>>

TR16-093 | 4th June 2016
Cyrus Rashtchian

Bounded Matrix Rigidity and John's Theorem

Using John's Theorem, we prove a lower bound on the bounded rigidity of a sign matrix, defined as the Hamming distance between this matrix and the set of low-rank, real-valued matrices with entries bounded in absolute value. For Hadamard matrices, our asymptotic leading constant is tighter than known results by ... more >>>

TR07-051 | 18th April 2007
Pilar Albert, Elvira Mayordomo, Philippe Moser

Bounded Pushdown dimension vs Lempel Ziv information density

In this paper we introduce a variant of pushdown dimension called bounded pushdown (BPD) dimension, that measures the density of information contained in a sequence, relative to a BPD automata, i.e. a finite state machine equipped with an extra infinite memory stack, with the additional requirement that every input symbol ... more >>>

TR97-035 | 31st July 1997
Richard Chang

Bounded Queries, Approximations and the Boolean Hierarchy

Revisions: 1

This paper introduces a new model of computation for describing the
complexity of NP-approximation problems. The results show that the
complexity of NP-approximation problems can be characterized by classes of
multi-valued functions computed by nondeterministic polynomial time Turing
machines with a bounded number of oracle queries to an NP-complete
language. ... more >>>

TR10-115 | 17th July 2010
Shachar Lovett, Emanuele Viola

Bounded-depth circuits cannot sample good codes

We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of $1-1/n^{\Omega(1)}$ on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a.~$\mathrm{AC}^0$) circuit $f : \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}^n$, and (ii) the uniform distribution ... more >>>

TR02-023 | 16th April 2002
Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal

Bounded-depth Frege lower bounds for weaker pigeonhole principles

Revisions: 1

We prove a quasi-polynomial lower bound on the size of bounded-depth
Frege proofs of the pigeonhole principle $PHP^{m}_n$ where
$m= (1+1/{\polylog n})n$.
This lower bound qualitatively matches the known quasi-polynomial-size
bounded-depth Frege proofs for these principles.
Our technique, which uses a switching lemma argument like other lower bounds
for ... more >>>

TR01-037 | 21st February 2001
Rustam Mubarakzjanov

Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable

Restricted branching programs are considered by the investigation
of relationships between complexity classes of Boolean functions.
Read-once ordered branching programs (or OBDDs) form the most restricted class
of this computation model.
Since the problem of proving exponential lower bounds on the complexity
for general probabilistic OBDDs is open so ... more >>>

TR12-096 | 17th July 2012
Albert Atserias, Sergi Oliva

Bounded-width QBF is PSPACE-complete

Revisions: 3

Tree-width is a well-studied parameter of structures that measures their similarity to a tree. Many important NP-complete problems, such as Boolean satisfiability (SAT), are tractable on bounded tree-width instances. In this paper we focus on the canonical PSPACE-complete problem QBF, the fully-quantified version of SAT. It was shown by Pan ... more >>>

TR16-142 | 11th September 2016
Jason Li, Ryan O'Donnell

Bounding laconic proof systems by solving CSPs in parallel

Revisions: 1

We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that MIP1$[k,c,s] \subseteq $ PSPACE provided $s/c \leq (.62-o(1))k/2^k$, resolving a question of Austrin, Håstad, and ... more >>>

TR10-049 | 24th March 2010
Alexey Pospelov

Bounds for Bilinear Complexity of Noncommutative Group Algebras

Revisions: 1 , Comments: 1

We study the complexity of multiplication in noncommutative group algebras which is closely related to the complexity of matrix multiplication. We characterize such semisimple group algebras of the minimal bilinear complexity and show nontrivial lower bounds for the rest of the group algebras. These lower bounds are built on the ... more >>>

TR17-071 | 14th April 2017
Young Kun Ko, Arial Schvartzman

Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria

Revisions: 1

In the recent paper of~\cite{BR16}, the authors show that, for any constant $10^{-15} > \varepsilon > 0$ the communication complexity of $\varepsilon$-approximate Nash equilibria in $2$-player $n \times n$ games is $n^{\Omega(\varepsilon)}$, resolving the long open problem of whether or not there exists a polylogarithmic communication protocol. In this paper ... more >>>

TR94-012 | 12th December 1994

Bounds for the Computational Power and Learning Complexity of Analog Neural Nets

It is shown that high order feedforward neural nets of constant depth with piecewise
polynomial activation functions and arbitrary real weights can be simulated for boolean
inputs and outputs by neural nets of a somewhat larger size and depth with heaviside
gates and weights ... more >>>

TR13-136 | 27th September 2013
Paul Goldberg, Aaron Roth

Bounds for the Query Complexity of Approximate Equilibria

We analyze the number of payoff queries needed to compute approximate correlated equilibria. For multi-player, binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player's behavior must always be approximately optimal, in the ... more >>>

TR03-019 | 3rd April 2003
Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

Bounds on 2-Query Codeword Testing.

Revisions: 1

We present upper bounds on the size of codes that are locally
testable by querying only two input symbols. For linear codes, we
show that any $2$-locally testable code with minimal distance
$\delta n$ over a finite field $F$ cannot have more than
$|F|^{3/\delta}$ codewords. This result holds even ... more >>>

TR09-138 | 14th December 2009
Gillat Kol, Ran Raz

Bounds on 2-Query Locally Testable Codes with Affine Tests

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field F, with codeword testers that only use tests of the form $av_i + bv_j = c$, where v is ... more >>>

TR03-033 | 6th May 2003
Meir Feder, Dana Ron, Ami Tavory

Bounds on Linear Codes for Network Multicast

Comments: 1

Traditionally, communication networks are composed of
routing nodes, which relay and duplicate data. Work in
recent years has shown that for the case of multicast, an
improvement in both rate and code-construction complexity can be
gained by replacing these routing nodes by linear coding
nodes. These nodes transmit linear combinations ... more >>>

TR09-142 | 17th December 2009
Aaron Potechin

Bounds on Monotone Switching Networks for Directed Connectivity

Revisions: 1

We prove that any monotone switching network solving directed connectivity on $N$ vertices must have size $N^{\Omega(\log N)}$

more >>>

TR98-044 | 31st July 1998
Jiri Sgall

Bounds on Pairs of Families with Restricted Intersections

We study pairs of families ${\cal A},{\cal B}\subseteq
2^{\{1,\ldots,r\}}$ such that $|A\cap B|\in L$ for any
$A\in{\cal A}$, $B\in{\cal B}$. We are interested in the maximal
product $|{\cal A}|\cdot|{\cal B}|$, given $r$ and $L$. We give
asymptotically optimal bounds for $L$ containing only elements
of $s<q$ residue classes modulo ... more >>>

TR16-013 | 12th January 2016
Ludwig Staiger

Bounds on the Kolmogorov complexity function for infinite words

Revisions: 1

The Kolmogorov complexity function of an infinite word $\xi$ maps a natural
number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We
investigate the maximally achievable complexity function if $\xi$ is taken
from a constructively describable set of infinite words. Here we are
interested ... more >>>

TR03-029 | 1st April 2003
Philippe Moser

BPP has effective dimension at most 1/2 unless BPP=EXP

We prove that BPP has Lutz's p-dimension at most 1/2 unless BPP equals EXP.
Next we show that BPP has Lutz's p-dimension zero unless BPP equals EXP
on infinitely many input lengths.
We also prove that BPP has measure zero in the smaller complexity
class ... more >>>

TR11-103 | 31st July 2011
Yang Li


We initiate the study of the relationship between two complexity classes, BQP
(Bounded-Error Quantum Polynomial-Time) and PPAD (Polynomial Parity Argument,
Directed). We first give a conjecture that PPAD is contained in BQP, and show
a necessary and sufficient condition for the conjecture to hold. Then we prove
that the conjecture ... more >>>

TR09-104 | 26th October 2009
Scott Aaronson

BQP and the Polynomial Hierarchy

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis.

First, we show that there ... more >>>

TR01-048 | 3rd June 2001
Jui-Lin Lee

Branching program, commutator, and icosahedron, part I

In this paper we give a direct proof of $N_0=N_0^\prime$, i.e., the equivalence of
uniform $NC^1$ based on different recursion principles: one is OR-AND complete
binary tree (in depth $\log n$) and the other is the recursion on notation with value
bounded in $[0,k]$ and $|x|(=n)$ many ... more >>>

TR05-098 | 4th September 2005
Oded Goldreich

Bravely, Moderately: A Common Theme in Four Recent Results

We highlight a common theme in four relatively recent works
that establish remarkable results by an iterative approach.
Starting from a trivial construct,
each of these works applies an ingeniously designed
sequence of iterations that yields the desired result,
which is highly non-trivial. Furthermore, in each iteration,
more >>>

TR05-124 | 2nd November 2005
Kooshiar Azimian

Breaking Diffie-Hellman is no Easier than Root Finding

In this paper we compare hardness of two well known problems: the Diffie-Hellman problem and the root finding problem. We prove that in any cyclic group computing Diffie-Hellman is not weaker than root finding if certain circumstances are met. As will be discussed in the paper this theorem can affect ... more >>>

TR10-068 | 15th April 2010
Shir Ben-Israel, Eli Ben-Sasson, David Karger

Breaking local symmetries can dramatically reduce the length of propositional refutations

This paper shows that the use of ``local symmetry breaking'' can dramatically reduce the length of propositional refutations. For each of the three propositional proof systems known as (i) treelike resolution, (ii) resolution, and (iii) k-DNF resolution, we describe families of unsatisfiable formulas in conjunctive normal form (CNF) that are ... more >>>

TR07-098 | 2nd October 2007
Tali Kaufman, Simon Litsyn, Ning Xie

Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. The interest in this problem is partly due to its relation to PCP constructions and hardness of ... more >>>

TR14-009 | 21st January 2014
Alexander A. Sherstov

Breaking the Minsky-Papert Barrier for Constant-Depth Circuits

The threshold degree of a Boolean function $f$ is the minimum degree of
a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969
monograph, Minsky and Papert constructed a polynomial-size constant-depth
$\{\wedge,\vee\}$-circuit in $n$ variables with threshold degree $\Omega(n^{1/3}).$ This bound underlies ... more >>>

TR13-160 | 20th November 2013
Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Breaking the quadratic barrier for 3-LCCs over the Reals

We prove that 3-query linear locally correctable codes over the Reals of dimension $d$ require block length $n>d^{2+\lambda}$ for some fixed, positive $\lambda >0$. Geometrically, this means that if $n$ vectors in $R^d$ are such that each vector is spanned by a linear number of disjoint triples of others, then ... more >>>

TR16-090 | 27th May 2016
Bernhard Haeupler, Ameya Velingker

Bridging the Capacity Gap Between Interactive and One-Way Communication

We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise.

Recently, Haeupler (FOCS '14) showed that if an $\epsilon > 0$ fraction of transmissions are corrupted, adversarially or randomly, then it is possible to ... more >>>

TR15-202 | 11th December 2015
Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

Building above read-once polynomials: identity testing and hardness of representation

Polynomial Identity Testing (PIT) algorithms have focused on
polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted
formulas. Read-once polynomials (ROPs) are computed by read-once
formulas (ROFs) and are the simplest of read-restricted polynomials.
Building structures above these, we show the following:
\item A deterministic polynomial-time non-black-box ... more >>>

TR10-127 | 9th August 2010
Brett Hemenway, Rafail Ostrovsky

Building Injective Trapdoor Functions From Oblivious Transfer

Revisions: 1

Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we give a novel construction of injective trapdoor functions based on oblivious transfer for long strings.

Our main result is to show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for ... more >>>

TR06-068 | 6th April 2006
Patrick Briest, Piotr Krysta

Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing

We investigate non-parametric unit-demand pricing problems, in which the goal is to find revenue maximizing prices for a set of products based on consumer profiles obtained, e.g., from an e-Commerce website. A consumer profile consists of a number of non-zero budgets and a ranking of all the products the consumer ... more >>>

TR10-177 | 16th November 2010
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

Bypassing UGC from some optimal geometric inapproximability results

Revisions: 1

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... more >>>

ISSN 1433-8092 | Imprint