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

TR14-032 | 8th March 2014
Olaf Beyersdorff, Leroy Chew

Tableau vs. Sequent Calculi for Minimal Entailment

In this paper we compare two proof systems for minimal entailment: a tableau system OTAB and a sequent calculus MLK, both developed by Olivetti (J. Autom. Reasoning, 1992). Our main result shows that OTAB-proofs can be efficiently translated into MLK-proofs, i.e., MLK p-simulates OTAB. The simulation is technically very involved ... more >>>

TR00-033 | 22nd May 2000
Jan Krajicek

Tautologies from pseudo-random generators

Revisions: 1

We consider tautologies formed from a pseudo-random
number generator, defined in Kraj\'{\i}\v{c}ek \cite{Kra99}
and in Alekhnovich et.al. \cite{ABRW}.
We explain a strategy of proving their hardness for EF via
a conjecture about bounded arithmetic formulated
in Kraj\'{\i}\v{c}ek \cite{Kra99}. Further we give a
purely finitary statement, in a ... more >>>

TR15-025 | 22nd February 2015
Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff

Teaching and compressing for low VC-dimension

In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. We present relatively efficient constructions of {\em sample compression schemes} and
for classes of low VC-dimension. Let $C$ be a finite boolean concept class of VC-dimension $d$. Set $k ... more >>>

TR09-007 | 9th January 2009
Eli Ben-Sasson, Michael Viderman

Tensor Products of Weakly Smooth Codes are Robust

We continue the study of {\em robust} tensor codes and expand the
class of base codes that can be used as a starting point for the
construction of locally testable codes via robust two-wise tensor
products. In particular, we show that all unique-neighbor expander
codes and all locally correctable codes, ... more >>>

TR12-004 | 10th January 2012
Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima

Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication

Revisions: 3

In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak with classical proofs, and iii) weak with quantum proofs. Here we focus on the first one. A strong quantum nondeterministic protocol accepts a correct input ... more >>>

TR11-010 | 1st February 2011
Boris Alexeev, Michael Forbes, Jacob Tsimerman

Tensor Rank: Some Lower and Upper Bounds

The results of Strassen and Raz show that good enough tensor rank lower bounds have implications for algebraic circuit/formula lower bounds.

We explore tensor rank lower and upper bounds, focusing on explicit tensors. For odd d, we construct field-independent explicit 0/1 tensors T:[n]^d->F with rank at least 2n^(floor(d/2))+n-Theta(d log n). ... more >>>

TR10-002 | 4th January 2010
Ran Raz

Tensor-Rank and Lower Bounds for Arithmetic Formulas

We show that any explicit example for a tensor $A:[n]^r \rightarrow \mathbb{F}$ with tensor-rank
$\geq n^{r \cdot (1- o(1))}$,
(where $r = r(n) \leq \log n / \log \log n$), implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over $\mathbb{F}$. This shows that strong enough ... more >>>

TR12-011 | 7th February 2012
Nader Bshouty

Testers and their Applications

We develop a new notion called {\it tester of a class $\cM$ of
functions} $f:\cA\to \cC$ that maps the elements $\bfa\in \cA$ in
the domain $\cA$ of the function to a finite number (the size of
the tester) of elements $\bfb_1,\ldots,\bfb_t$ in a smaller
sub-domain $\cB\subset \cA$ where the property ... more >>>

TR11-057 | 15th April 2011
Madhav Jha, Sofya Raskhodnikova

Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy

Revisions: 2

A function $f : D \to R$ has Lipschitz constant $c$ if $d_R(f(x),f(y)) \leq c\cdot d_D(x,y)$ for all $x,y$ in $D$, where $d_R$ and $d_D$ denote the distance functions on the range and domain of $f$, respectively. We say a function is Lipschitz if it has Lipschitz constant 1. (Note ... more >>>

TR97-010 | 2nd April 1997
Marcos Kiwi

Testing and Weight Distributions of Dual Codes

We study the testing problem, that is, the problem of determining (maybe
probabilistically) if a function to which we have oracle access
satisfies a given property.

We propose a framework in which to formulate and carry out the analyzes
of several known tests. This framework establishes a connection between
more >>>

TR12-103 | 16th August 2012
Arnab Bhattacharyya, Yuichi Yoshida

Testing Assignments of Boolean CSPs

Given an instance $\mathcal{I}$ of a CSP, a tester for $\mathcal{I}$ distinguishes assignments satisfying $\mathcal{I}$ from those which are far from any assignment satisfying $\mathcal{I}$. The efficiency of a tester is measured by its query complexity, the number of variable assignments queried by the algorithm. In this paper, we characterize ... more >>>

TR12-031 | 4th April 2012
Tom Gur, Omer Tamuz

Testing Booleanity and the Uncertainty Principle

Revisions: 1

Let $f:\{-1,1\}^n \to \mathbb{R}$ be a real function on the hypercube, given
by its discrete Fourier expansion, or, equivalently, represented as
a multilinear polynomial. We say that it is Boolean if its image is
in $\{-1,1\}$.

We show that every function on the hypercube with a ... more >>>

TR11-041 | 24th March 2011
Dana Ron, Gilad Tsur

Testing Computability by Width-Two OBDDs

Property testing is concerned with deciding whether an object
(e.g. a graph or a function) has a certain property or is ``far''
(for a prespecified distance measure) from every object with
that property. In this work we consider the property of being
computable by a read-once ... more >>>

TR11-101 | 26th July 2011
Angsheng Li, Yicheng Pan, Pan Peng

Testing Conductance in General Graphs

In this paper, we study the problem of testing the conductance of a
given graph in the general graph model. Given distance parameter
$\varepsilon$ and any constant $\sigma>0$, there exists a tester
whose running time is $\mathcal{O}(\frac{m^{(1+\sigma)/2}\cdot\log
n\cdot\log\frac{1}{\varepsilon}}{\varepsilon\cdot\Phi^2})$, where
$n$ is the number of vertices and $m$ is the number ... more >>>

TR06-053 | 6th April 2006
Eldar Fischer, Orly Yahalom

Testing Convexity Properties of Tree Colorings

A coloring of a graph is {\it convex} if it
induces a partition of the vertices into connected subgraphs.
Besides being an interesting property from a theoretical point of
view, tests for convexity have applications in various areas
involving large graphs. Our results concern the important subcase
of testing for ... more >>>

TR16-086 | 29th May 2016
Noga Alon, Klim Efremenko, Benny Sudakov

Testing Equality in Communication Graphs

Revisions: 1

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose
that on each vertex of the graph there is a player having an $n$-bit
string. Each player is allowed to communicate with its neighbors according
to an agreed communication protocol, and the players must decide,
deterministically, if their inputs ... more >>>

TR14-003 | 10th January 2014
Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka

Testing Equivalence of Polynomials under Shifts

Revisions: 2 , Comments: 1

Two polynomials $f, g \in F[x_1, \ldots, x_n]$ are called shift-equivalent if there exists a vector $(a_1, \ldots, a_n) \in {F}^n$ such that the polynomial identity $f(x_1+a_1, \ldots, x_n+a_n) \equiv g(x_1,\ldots,x_n)$ holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our ... more >>>

TR07-076 | 25th July 2007
Satyen Kale, C. Seshadhri

Testing Expansion in Bounded Degree Graphs

Revisions: 1

We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and ... more >>>

TR07-077 | 7th August 2007
Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

Testing for Concise Representations

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>

TR00-083 | 18th September 2000
Eldar Fischer

Testing graphs for colorability properties

Revisions: 1

Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a
randomized algorithm which, given the ability to make queries whether
a desired pair of vertices of an input graph $G$ with $n$ vertices are
adjacent or not, distinguishes, with high probability, between the
case of $G$ satisfying ... more >>>

TR07-128 | 10th November 2007
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

Testing Halfspaces

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w ⋅ x - θ). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... more >>>

TR07-083 | 23rd August 2007
Artur Czumaj, Asaf Shapira, Christian Sohler

Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs

We study property testing in the model of bounded degree graphs. It
is well known that in this model many graph properties cannot be
tested with a constant number of queries and it seems reasonable to
conjecture that only few are testable with o(sqrt{n}) queries.
Therefore in this paper ... more >>>

TR17-058 | 7th April 2017
Noga Alon, Omri Ben-Eliezer, Eldar Fischer

Testing hereditary properties of ordered graphs and matrices

Revisions: 1

We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries.
We also explain how the proof can ... more >>>

TR17-006 | 15th December 2016
Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath

Testing Ising Models

Revisions: 2

Given samples from an unknown multivariate distribution $p$, is it possible to distinguish whether $p$ is the product of its marginals versus $p$ being far from every product distribution? Similarly, is it possible to distinguish whether $p$ equals a given distribution $q$ versus $p$ and $q$ being far from each ... more >>>

TR16-136 | 31st August 2016
Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer

Testing k-Monotonicity

Revisions: 1

A Boolean $k$-monotone function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$-monotone functions are natural generalizations of the classical monotone functions, which are the $1$-monotone functions.

Motivated by the ... more >>>

TR11-005 | 20th January 2011
Madhu Sudan

Testing Linear Properties: Some general themes

Revisions: 1

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, ... more >>>

TR08-088 | 13th September 2008
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Testing Linear-Invariant Non-Linear Properties

Revisions: 1

We consider the task of testing properties of Boolean functions that
are invariant under linear transformations of the Boolean cube. Previous
work in property testing, including the linearity test and the test
for Reed-Muller codes, has mostly focused on such tasks for linear
properties. The one exception is a test ... more >>>

TR10-116 | 21st July 2010
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Testing linear-invariant non-linear properties: A short report

The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied ... more >>>

TR12-076 | 12th June 2012
Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

Testing Lipschitz Functions on Hypergrid Domains

A function $f(x_1, ... , x_d)$, where each input is an integer from 1 to $n$ and output is a real number, is Lipschitz if changing one of the inputs by 1 changes the output by at most 1. In other words, Lipschitz functions are not very sensitive to small ... more >>>

TR12-001 | 1st January 2012
Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett

Testing Low Complexity Affine-Invariant Properties

Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, ... more >>>

TR10-027 | 28th February 2010
Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant

Testing monotonicity of distributions over general partial orders

We investigate the number of samples required for testing the monotonicity of a distribution with respect to an arbitrary underlying partially ordered set. Our first result is a nearly linear lower bound for the sample complexity of testing monotonicity with respect to the poset consisting of a directed perfect matching. ... more >>>

TR11-075 | 6th May 2011
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Testing Odd-Cycle-Freeness in Boolean Functions

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... more >>>

TR10-065 | 13th April 2010
Tali Kaufman, Shachar Lovett

Testing of exponentially large codes, by a new extension to Weil bound for character sums

Revisions: 1

In this work we consider linear codes which are locally testable
in a sublinear number of queries. We give the first general family
of locally testable codes of exponential size. Previous results of
this form were known only for codes of quasi-polynomial size (e.g.
Reed-Muller codes). We accomplish this by ... more >>>

TR05-153 | 9th December 2005
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Testing Orientation Properties

We propose a new model for studying graph related problems
that we call the \emph{orientation model}. In this model, an undirected
graph $G$ is fixed, and the input is any possible edge orientation
of $G$. A property is now a property of the directed graph that is
obtained by a ... more >>>

TR04-092 | 3rd November 2004
Oded Lachish, Ilan Newman

Testing Periodicity

A string $\alpha\in\Sigma^n$ is called {\it p-periodic},
if for every $i,j \in \{1,\dots,n\}$, such that $i\equiv j \bmod p$,
$\alpha_i = \alpha_{j}$, where $\alpha_i$ is the $i$-th place of $\alpha$.
A string $\alpha\in\Sigma^n$ is said to be $period(\leq g)$,
if there exists $p\in \{1,\dots,g\}$ such that $\alpha$ ... more >>>

TR12-094 | 19th July 2012
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Testing Permanent Oracles -- Revisited

Suppose we are given an oracle that claims to approximate the permanent for most matrices $X$, where $X$ is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task.

... more >>>

TR14-021 | 18th February 2014
Clement Canonne, Ronitt Rubinfeld

Testing probability distributions underlying aggregated data

In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution $D$ over $[n]$. More precisely, we define both the dual and extended ... more >>>

TR12-155 | 15th November 2012
Clement Canonne, Dana Ron, Rocco Servedio

Testing probability distributions using conditional samples

Revisions: 1

We study a new framework for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle. \footnote{Independently from our work, Chakraborty et al. [CFGM13] also considered this framework. We discuss their work in Subsection 1.4.} This is an oracle that takes as ... more >>>

TR10-157 | 24th October 2010
Reut Levi, Dana Ron, Ronitt Rubinfeld

Testing Properties of Collections of Distributions

Revisions: 1

We propose a framework for studying property testing of collections of distributions,
where the number of distributions in the collection is a parameter of the problem.
Previous work on property testing of distributions considered
single distributions or pairs of distributions. We suggest two models that differ
in the way the ... more >>>

TR07-054 | 25th May 2007
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Testing Properties of Constraint-Graphs

We study a model of graph related formulae that we call
the \emph{Constraint-Graph model}. A
constraint-graph is a labeled multi-graph (a graph where loops
and parallel edges are allowed), where each edge $e$ is labeled
by a distinct Boolean variable and every vertex is
associate with a Boolean function over ... more >>>

TR12-055 | 4th May 2012
Reut Levi, Dana Ron, Ronitt Rubinfeld

Testing Similar Means

We consider the problem of testing a basic property of collections of distributions: having similar means. Namely, the algorithm should accept collections of distributions in which all distributions have means that do not differ by more than some given parameter, and should reject collections that are relatively far from having ... more >>>

TR07-135 | 26th December 2007
Paul Valiant, Paul Valiant

Testing Symmetric Properties of Distributions

We introduce the notion of a Canonical Tester for a class of properties, that is, a tester strong and
general enough that ``a property is testable if and only if the
Canonical Tester tests it''. We construct a Canonical Tester
for the class of symmetric properties of one or two
more >>>

TR07-118 | 27th November 2007
Asaf Nachmias, Asaf Shapira

Testing the Expansion of a Graph

We study the problem of testing the expansion of
graphs with bounded degree d in sublinear time. A graph is said to
be an \alpha-expander if every vertex set U \subset V of size at
most |V|/2 has a neighborhood of size at least \alpha|U|.

We show that the algorithm ... more >>>

TR03-076 | 8th September 2003
Michael Langberg

Testing the independence number of hypergraphs

A $k$-uniform hypergraph $G$ of size $n$ is said to be $\varepsilon$-far from having an independent set of size $\rho n$ if one must remove at least $\varepsilon n^k$ edges of $G$ in order for the remaining hypergraph to have an independent set of size $\rho n$. In this work, ... more >>>

TR11-076 | 7th May 2011
Eric Miles, Emanuele Viola

The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous
constructions. In particular, we ... more >>>

TR13-040 | 11th March 2013
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie

The Algebraic Theory of Parikh Automata

Revisions: 2

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theory of typed monoids is used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh ... more >>>

TR99-043 | 5th November 1999
Venkatesan Guruswami

The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses

We prove hardness results for approximating set splitting problems and
also instances of satisfiability problems which have no ``mixed'' clauses,
i.e all clauses have either all their literals unnegated or all of them
negated. Recent results of Hastad imply tight hardness results for set
splitting when all sets ... more >>>

TR12-169 | 22nd November 2012
Noga Alon, Santosh Vempala

The Approximate Rank of a Matrix and its Algorithmic Applications

Revisions: 2

We introduce and study the \epsilon-rank of a real matrix A, defi ned, for any  \epsilon > 0 as the minimum rank over matrices that approximate every entry of A to within an additive \epsilon. This parameter is connected to other notions of approximate rank and is motivated by ... more >>>

TR04-079 | 30th August 2004
John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn

The Arithmetical Complexity of Dimension and Randomness

Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1].

Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong ... more >>>

TR15-143 | 31st August 2015
Benjamin Rossman

The Average Sensitivity of Bounded-Depth Formulas

We show that unbounded fan-in boolean formulas of depth $d+1$ and size $s$ have average sensitivity $O(\frac{1}{d}\log s)^d$. In particular, this gives a tight $2^{\Omega(d(n^{1/d}-1))}$ lower bound on the size of depth $d+1$ formulas computing the PARITY function. These results strengthen the corresponding $2^{\Omega(n^{1/d})}$ and $O(\log s)^d$ bounds for circuits ... more >>>

TR16-181 | 15th November 2016
Avishay Tal

The Bipartite Formula Complexity of Inner-Product is Quadratic

A bipartite formula on binary variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves may compute any function of either the $x$ or $y$ variables. We show that any bipartite formula for the Inner-Product ... more >>>

TR07-125 | 11th October 2007
Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka

The black-box query complexity of polynomial summation

For any given Boolean formula $\phi(x_1,\dots,x_n)$, one can
efficiently construct (using \emph{arithmetization}) a low-degree
polynomial $p(x_1,\dots,x_n)$ that agrees with $\phi$ over all
points in the Boolean cube $\{0,1\}^n$; the constructed polynomial
$p$ can be interpreted as a polynomial over an arbitrary field
$\mathbb{F}$. The problem ... more >>>

TR96-032 | 12th March 1996
Manindra Agrawal, Thomas Thierauf

The Boolean Isomorphism Problem

We investigate the computational complexity of the Boolean Isomorphism problem (BI):
on input of two Boolean formulas F and G decide whether there exists a permutation of
the variables of G such that F and G become equivalent.

Our main result is a one-round interactive proof ... more >>>

TR16-096 | 14th June 2016
Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay

The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Revisions: 2

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this ... more >>>

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

The Choice and Agreement Problems of a Random Function

Revisions: 1

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

TR15-066 | 20th April 2015
Scott Aaronson, Daniel Grier, Luke Schaeffer

The Classification of Reversible Bit Operations

We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical ... more >>>

TR17-090 | 15th May 2017
Chin Ho Lee, Emanuele Viola

The coin problem for product tests

Let $X_{m, \eps}$ be the distribution over $m$ bits $(X_1, \ldots, X_m)$
where the $X_i$ are independent and each $X_i$ equals $1$ with
probability $(1+\eps)/2$ and $0$ with probability $(1-\eps)/2$. We
consider the smallest value $\eps^*$ of $\eps$ such that the distributions
$X_{m,\eps}$ and $X_{m,0}$ can be distinguished with constant
more >>>

TR11-152 | 12th November 2011
Emanuele Viola

The communication complexity of addition

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>>

TR06-151 | 10th December 2006
Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

The communication complexity of correlation

We examine the communication required for generating random variables
remotely. One party Alice will be given a distribution D, and she
has to send a message to Bob, who is then required to generate a
value with distribution exactly D. Alice and Bob are allowed
to share random bits generated ... more >>>

TR01-019 | 2nd March 2001
Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

The Communication Complexity of Enumeration, Elimination, and Selection

Normally, communication Complexity deals with how many bits
Alice and Bob need to exchange to compute f(x,y)
(Alice has x, Bob has y). We look at what happens if
Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n
and they want to compute f(x_1,y_1)... f(x_n,y_n).
THis seems hard. We look at various ... more >>>

TR11-063 | 19th April 2011
Alexander A. Sherstov

The Communication Complexity of Gap Hamming Distance

In the gap Hamming distance problem, two parties must
determine whether their respective strings $x,y\in\{0,1\}^n$
are at Hamming distance less than $n/2-\sqrt n$ or greater
than $n/2+\sqrt n.$ In a recent tour de force, Chakrabarti and
Regev (STOC '11) proved the long-conjectured $\Omega(n)$ bound
on the randomized communication ... more >>>

TR15-044 | 2nd April 2015
Timothy Gowers, Emanuele Viola

The communication complexity of interleaved group products

Revisions: 1

Alice receives a tuple $(a_1,\ldots,a_t)$ of $t$ elements
from the group $G = \text{SL}(2,q)$. Bob similarly
receives a tuple $(b_1,\ldots,b_t)$. They are promised
that the interleaved product $\prod_{i \le t} a_i b_i$
equals to either $g$ and $h$, for two fixed elements $g,h
\in G$. Their task is to decide ... more >>>

TR15-002 | 2nd January 2015
Mark Braverman, Rotem Oshman

The Communication Complexity of Number-In-Hand Set Disjointness with No Promise

Set disjointness is one of the most fundamental problems in communication complexity. In the multi-party number-in-hand version of set disjointness, $k$ players receive private inputs $X_1,\ldots,X_k\subseteq \{1,\ldots,n\}$, and their goal is to determine whether or not $\bigcap_{i = 1}^k X_i = \emptyset$. In this paper we prove a tight lower ... more >>>

TR04-061 | 30th June 2004
Scott Aaronson

The Complexity of Agreement

A celebrated 1976 theorem of Aumann asserts that honest, rational
Bayesian agents with common priors will never "agree to disagree": if
their opinions about any topic are common knowledge, then those
opinions must be equal. Economists have written numerous papers
examining the assumptions behind this theorem. But two key questions
more >>>

TR05-115 | 27th September 2005
Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou

The complexity of computing a Nash equilibrium

We resolve the question of the complexity of Nash equilibrium by
showing that the problem of computing a Nash equilibrium in a game
with 4 or more players is complete for the complexity class PPAD.
Our proof uses ideas from the recently-established equivalence
between polynomial-time solvability of normal-form games and
more >>>

TR98-022 | 14th April 1998
Steffen Reith, Heribert Vollmer

The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

We consider the problems of finding the lexicographically
minimal (or maximal) satisfying assignment of propositional
formulae for different restricted formula classes. It turns
out that for each class from our framework, the above problem
is either polynomial time solvable or complete for ... more >>>

TR01-061 | 13th July 2001
Mitsunori Ogihara, Seinosuke Toda

The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs

Revisions: 2

Valiant (SIAM Journal on Computing 8, pages 410--421) showed that the
roblem of counting the number of s-t paths in graphs (both in the case
of directed graphs and in the case of undirected graphs) is complete
for #P under polynomial-time one-Turing reductions (namely, some
post-computation is needed to ... more >>>

TR01-077 | 24th September 2001
Andrei Krokhin, Peter Jeavons, Peter Jonsson

The complexity of constraints on intervals and lengths

We study interval-valued constraint satisfaction problems (CSPs),
in which the aim is to find an assignment of intervals to a given set of
variables subject to constraints on the relative positions of intervals.
Many well-known problems such as Interval Graph Recognition
and Interval Satisfiability can be considered as examples of ... more >>>

TR04-020 | 8th March 2004
Emanuele Viola

The Complexity of Constructing Pseudorandom Generators from Hard Functions

We study the complexity of building
pseudorandom generators (PRGs) from hard functions.

We show that, starting from a function f : {0,1}^l -> {0,1} that
is mildly hard on average, i.e. every circuit of size 2^Omega(l)
fails to compute f on at least a 1/poly(l)
fraction of inputs, we can ... more >>>

TR14-016 | 16th January 2014
Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz

The Complexity of Debate Checking

We study probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. We consider debates of partial and zero information, where the prover is prevented from seeing some or all of ... more >>>

TR07-045 | 24th April 2007
Heribert Vollmer

The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis

We study the complexity of the following algorithmic problem: Given a Boolean function $f$ and a finite set of Boolean functions $B$, decide if there is a circuit with basis $B$ that computes $f$. We show that if both $f$ and all functions in $B$ are given by their truth-table, ... more >>>

TR13-124 | 9th September 2013
Thomas Watson

The Complexity of Deciding Statistical Properties of Samplable Distributions

Revisions: 2

We consider the problems of deciding whether the joint distribution sampled by a given circuit satisfies certain statistical properties such as being i.i.d., being exchangeable, being pairwise independent, having two coordinates with identical marginals, having two uncorrelated coordinates, and many other variants. We give a proof that simultaneously shows all ... more >>>

TR06-049 | 9th April 2006
Guy Wolfovitz

The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions

We give tight lower bounds for the size of depth-3 circuits with limited bottom fanin computing symmetric Boolean functions. We show that any depth-3 circuit with bottom fanin $k$ which computes the Boolean function $EXACT_{n/(k+1)}^{n}$, has at least $(1+1/k)^{n+\O(\log n)}$ gates. We show that this lower bound is tight, by ... more >>>

TR14-099 | 7th August 2014
Gil Cohen, Igor Shinkar

The Complexity of DNF of Parities

We study depth 3 circuits of the form $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{XOR}$, or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a $2^{\Omega(n)}$ lower bound for explicit functions. Several related models have gained attention in the last few years, such as ... more >>>

TR12-070 | 26th May 2012
Thomas Watson

The Complexity of Estimating Min-Entropy

Revisions: 1

Goldreich, Sahai, and Vadhan (CRYPTO 1999) proved that the promise problem for estimating the Shannon entropy of a distribution sampled by a given circuit is NISZK-complete. We consider the analogous problem for estimating the min-entropy and prove that it is SBP-complete, even when restricted to 3-local samplers. For logarithmic-space samplers, ... more >>>

TR10-111 | 14th July 2010
Venkatesan Guruswami, Ali Kemal Sinop

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

We prove almost tight hardness results for finding independent sets in bounded degree graphs and hypergraphs that admit a good
coloring. Our specific results include the following (where $\Delta$, assumed to be a constant, is a bound on the degree, and
$n$ is the number of vertices):

... more >>>

TR06-149 | 7th December 2006
Lance Fortnow, Rakesh Vohra

The Complexity of Forecast Testing

Consider a weather forecaster predicting a probability of rain for
the next day. We consider tests that given a finite sequence of
forecast predictions and outcomes will either pass or fail the
forecaster. Sandroni (2003) shows that any test which passes a
forecaster who knows the distribution of nature, can ... more >>>

TR06-153 | 19th October 2006
Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

The Complexity of Generalized Satisfiability for Linear Temporal Logic

Revisions: 1

In a seminal paper from 1985, Sistla and Clarke showed
that satisfiability for Linear Temporal Logic (LTL) is either
NP-complete or PSPACE-complete, depending on the set of temporal
operators used

If, in contrast, the set of propositional operators is restricted, the
complexity may ... more >>>

TR14-070 | 14th May 2014
Vikraman Arvind, Gaurav Rattan

The Complexity of Geometric Graph Isomorphism

We study the complexity of Geometric Graph Isomorphism, in
$l_2$ and other $l_p$ metrics: given two sets of $n$ points $A,
B\subset \mathbb{Q}^k$ in
$k$-dimensional euclidean space the problem is to
decide if there is a bijection $\pi:A \rightarrow B$ such that for
... more >>>

TR12-090 | 2nd July 2012
Michael Blondin, Andreas Krebs, Pierre McKenzie

The Complexity of Intersecting Finite Automata Having Few Final States

The problem of determining whether several finite automata accept a word in common is closely related to the well-studied membership problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For automata with two final states, we show the problem ... more >>>

TR08-053 | 27th March 2008
Stephen A. Fenner, William Gasarch, Brian Postow

The complexity of learning SUBSEQ(A)

Higman showed that if A is *any* language then SUBSEQ(A)
is regular, where SUBSEQ(A) is the language of all
subsequences of strings in A. (The result we attribute
to Higman is actually an easy consequence of his work.)
Let s_1, s_2, s_3, ... more >>>

TR08-034 | 19th January 2008
Dan Gutfreund, Guy Rothblum

The Complexity of Local List Decoding

Revisions: 1

We study the complexity of locally list-decoding binary error correcting codes with good parameters (that are polynomially related to information theoretic bounds). We show that computing majority over $\Theta(1/\eps)$ bits is essentially equivalent to locally list-decoding binary codes from relative distance $1/2-\eps$ with list size $\poly(1/\eps)$. That is, a local-decoder ... more >>>

TR96-024 | 21st March 1996
Eric Allender, Robert Beals, Mitsunori Ogihara

The complexity of matrix rank and feasible systems of linear equations

We characterize the complexity of some natural and important
problems in linear algebra. In particular, we identify natural
complexity classes for which the problems of (a) determining if a
system of linear equations is feasible and (b) computing the rank of
an integer matrix, ... more >>>

TR95-040 | 26th July 1995
Uri Zwick, Michael S. Paterson

The complexity of mean payoff games on graphs

We study the complexity of finding the values and optimal strategies of
MEAN PAYOFF GAMES on graphs, a family of perfect information games
introduced by Ehrenfeucht and Mycielski and considered by Gurvich,
Karzanov and Khachiyan. We describe a pseudo-polynomial time algorithm
for the solution of such games, the decision ... more >>>

TR00-082 | 17th August 2000
Lefteris Kirousis, Phokion G. Kolaitis

The Complexity of Minimal Satisfiability Problems

Revisions: 2

A dichotomy theorem for a class of decision problems is
a result asserting that certain problems in the class
are solvable in polynomial time, while the rest are NP-complete.
The first remarkable such dichotomy theorem was proved by
T.J. Schaefer in 1978. It concerns the ... more >>>

TR99-001 | 4th January 1999
Detlef Sieling

The Complexity of Minimizing FBDDs

Revisions: 1

Free Binary Decision Diagrams (FBDDs) are a data structure
for the representation and manipulation of Boolean functions.
Efficient algorithms for most of the important operations are known if
only FBDDs respecting a fixed graph ordering are considered. However,
the size of such an FBDD may strongly depend on the chosen ... more >>>

TR06-034 | 9th March 2006
Moni Naor, Guy Rothblum

The Complexity of Online Memory Checking

Suppose you want to store a large file on a remote and unreliable server. You would like to verify that your file has not been corrupted, so you store a small private (randomized)``fingerprint'' of the file on your own computer. This is the setting for the well-studied authentication problem, and ... more >>>

TR07-023 | 26th February 2007
Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor

The Complexity of Problems for Quantified Constraints

In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>>

TR13-038 | 13th March 2013
Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen

The complexity of proving that a graph is Ramsey

Revisions: 1

We say that a graph with $n$ vertices is $c$-Ramsey if it does not contain either a clique or an independent set of size $c \log n$. We define a CNF formula which expresses this property for a graph $G$. We show a superpolynomial lower bound on the length of ... more >>>

TR17-065 | 20th April 2017
Boaz Barak

The Complexity of Public-Key Cryptograph

We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for public-key encryption schemes, and the types of evidence we have for the veracity of these assumptions.

This is a survey that appeared in a book of surveys in honor of ... more >>>

TR16-109 | 18th July 2016
Scott Aaronson

The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

This mini-course will introduce participants to an exciting frontier for quantum computing theory: namely, questions involving the computational complexity of preparing a certain quantum state or applying a certain unitary transformation. Traditionally, such questions were considered in the context of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, ... more >>>

TR08-021 | 3rd March 2008
Shankar Kalyanaraman, Chris Umans

The Complexity of Rationalizing Matchings

Given a set of observed economic choices, can one infer
preferences and/or utility functions for the players that are
consistent with the data? Questions of this type are called {\em
rationalization} or {\em revealed preference} problems in the
economic literature, and are the subject of a rich body of work.

... more >>>

TR09-145 | 20th December 2009
Shankar Kalyanaraman, Chris Umans

The Complexity of Rationalizing Network Formation

We study the complexity of {\em rationalizing} network formation. In
this problem we fix an underlying model describing how selfish
parties (the vertices) produce a graph by making individual
decisions to form or not form incident edges. The model is equipped
with a notion of stability (or equilibrium), and we ... more >>>

TR04-100 | 23rd November 2004
Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

Revisions: 1

Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer's dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are ... more >>>

TR11-053 | 11th April 2011
Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek

The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions

Instances of optimization problems with multiple objectives can have several optimal solutions whose cost vectors are incomparable. This ambiguity leads to several reasonable notions for solving multiobjective problems. Each such notion defines a class of multivalued functions. We systematically investigate the computational complexity of these classes.

Some solution notions S ... more >>>

TR12-151 | 6th November 2012
Subhash Khot, Madhur Tulsiani, Pratik Worah

The Complexity of Somewhat Approximation Resistant Predicates

Revisions: 1

A boolean predicate $f:\{0,1\}^k\to\{0,1\}$ is said to be {\em somewhat approximation resistant} if for some constant $\tau > \frac{|f^{-1}(1)|}{2^k}$, given a $\tau$-satisfiable instance of the MAX-$k$-CSP$(f)$ problem, it is NP-hard to find an assignment that {\it strictly beats} the naive algorithm that outputs a uniformly random assignment. Let $\tau(f)$ denote ... more >>>

TR00-036 | 29th May 2000
Carsten Damm, Markus Holzer, Pierre McKenzie

The Complexity of Tensor Calculus

Tensor calculus over semirings is shown relevant to complexity
theory in unexpected ways. First, evaluating well-formed tensor
formulas with explicit tensor entries is shown complete for $\olpus\P$,
for $\NP$, and for $\#\P$ as the semiring varies. Indeed the
permanent of a matrix is shown expressible as ... more >>>

TR10-114 | 17th July 2010
Zhixiang Chen, Bin Fu

The Complexity of Testing Monomials in Multivariate Polynomials

The work in this paper is to initiate a theory of testing
monomials in multivariate polynomials. The central question is to
ask whether a polynomial represented by certain economically
compact structure has a multilinear monomial in its sum-product
expansion. The complexity aspects of this problem and its variants
are investigated ... more >>>

TR07-093 | 27th July 2007
Andrei A. Bulatov

The complexity of the counting constraint satisfaction problem

Revisions: 1

The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite
relational structure H can be expressed as follows: given a
relational structure G over the same vocabulary,
determine the number of homomorphisms from G to H.
In this paper we characterize relational structures H for which
#CSP(H) can be solved in ... more >>>

TR08-011 | 21st November 2007
Kazuo Iwama, Suguru Tamaki

The Complexity of the Hajos Calculus for Planar Graphs

The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the HajLos calculus is polynomially bounded.

more >>>

TR01-028 | 16th March 2001
Thanh Minh Hoang, Thomas Thierauf

The Complexity of the Minimal Polynomial

We investigate the computational complexity
of the minimal polynomial of an integer matrix.

We show that the computation of the minimal polynomial
is in AC^0(GapL), the AC^0-closure of the logspace
counting class GapL, which is contained in NC^2.
Our main result is that the problem is hard ... more >>>

TR13-016 | 17th January 2013
Olaf Beyersdorff

The Complexity of Theorem Proving in Autoepistemic Logic

Revisions: 1

Autoepistemic logic is one of the most successful formalisms for nonmonotonic reasoning. In this paper we provide a proof-theoretic analysis of sequent calculi for credulous and sceptical reasoning in propositional autoepistemic logic, introduced by Bonatti and Olivetti (ACM ToCL, 2002). We show that the calculus for credulous reasoning obeys almost ... more >>>

TR14-014 | 28th January 2014
Olaf Beyersdorff, Leroy Chew

The Complexity of Theorem Proving in Circumscription and Minimal Entailment

Circumscription is one of the main formalisms for non-monotonic reasoning. It uses reasoning with minimal models, the key idea being that minimal models have as few exceptions as possible. In this contribution we provide the first comprehensive proof-complexity analysis of different proof systems for propositional circumscription. In particular, we investigate ... more >>>

TR14-028 | 27th February 2014
Vikraman Arvind, S Raja

The Complexity of Two Register and Skew Arithmetic Computation

We study two register arithmetic computation and skew arithmetic circuits. Our main results are the following:

(1) For commutative computations, we show that an exponential circuit size lower bound
for a model of 2-register straight-line programs (SLPs) which is a universal model
of computation (unlike width-2 algebraic branching programs that ... more >>>

TR06-069 | 11th May 2006
Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner

The Complexity of Unions of Disjoint Sets

This paper is motivated by the open question
whether the union of two disjoint NP-complete sets always is
NP-complete. We discover that such unions retain
much of the complexity of their single components. More precisely,
they are complete with respect to more general reducibilities.

more >>>

TR14-083 | 19th June 2014
Irit Dinur, Shafi Goldwasser, Huijia Lin

The Computational Benefit of Correlated Instances

The starting point of this paper is that instances of computational problems often do not exist in isolation. Rather, multiple and correlated instances of the same problem arise naturally in the real world. The challenge is how to gain computationally from instance correlations when they exist. We will be interested ... more >>>

TR04-055 | 27th May 2004
Kousha Etessami, Andreas Lochbihler

The computational complexity of Evolutionarily Stable Strategies

Game theory has been used for a long time to study phenomena in evolutionary biology, beginning systematically with the seminal work of John Maynard Smith. A central concept in this connection has been the notion of an evolutionarily stable strategy (ESS) in a symmetric two-player strategic form game. A regular ... more >>>

TR10-170 | 11th November 2010
Scott Aaronson, Alex Arkhipov

The Computational Complexity of Linear Optics

We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a
model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count ... more >>>

TR05-052 | 5th May 2005
Grant Schoenebeck, Salil Vadhan

The Computational Complexity of Nash Equilibria in Concisely Represented Games

Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number ... more >>>

TR97-009 | 12th March 1997
Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit

The Computational Complexity of Some Problems of Linear Algebra

We consider the computational complexity of some problems
dealing with matrix rank. Let E,S be subsets of a
commutative ring R. Let x_1, x_2, ..., x_t be variables.
Given a matrix M = M(x_1, x_2, ..., x_t) with entries
chosen from E union {x_1, x_2, ..., ... more >>>

TR14-013 | 30th January 2014
Mark Braverman, Kanika Pasricha

The computational hardness of pricing compound options

It is generally assumed that you can make a financial asset out of any underlying event or combination thereof, and then sell a security. We show that while this is theoretically true from the financial engineering perspective, compound securities might be intractable to price. Even given no information asymmetries, or ... more >>>

TR96-025 | 22nd March 1996
Berthold Ruf

The Computational Power of Spiking Neurons Depends on the Shape of the Postsynaptic Potentials

Recently one has started to investigate the
computational power of spiking neurons (also called ``integrate and
fire neurons''). These are neuron models that are substantially
more realistic from the biological point of view than the
ones which are traditionally employed in artificial neural nets.
It has turned out that the ... more >>>

TR01-005 | 27th October 2000
Pascal Tesson, Denis Thérien

The Computing Power of Programs over Finite Monoids

The formalism of programs over monoids has been studied for its close
connection to parallel complexity classes defined by small-depth
boolean circuits. We investigate two basic questions about this
model. When is a monoid rich enough that it can recognize arbitrary
languages (provided no restriction on length is imposed)? When ... more >>>

TR06-094 | 29th July 2006
Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Revisions: 1

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

TR04-022 | 31st March 2004
Nayantara Bhatnagar, Parikshit Gopalan

The Degree of Threshold Mod 6 and Diophantine Equations

We continue the study of the degree of polynomials representing threshold functions modulo 6 initiated by Barrington, Beigel and Rudich. We use the framework established by the authors relating representations by symmetric polynomials to simultaneous protocols. We show that proving bounds on the degree of Threshold functions is equivalent to ... more >>>

TR09-030 | 5th April 2009
Shachar Lovett

The density of weights of Generalized Reed-Muller codes

We study the density of the weights of Generalized Reed--Muller codes. Let $RM_p(r,m)$ denote the code of multivariate polynomials over $\F_p$ in $m$ variables of total degree at most $r$. We consider the case of fixed degree $r$, when we let the number of variables $m$ tend to infinity. We ... more >>>

TR14-124 | 7th October 2014
Periklis Papakonstantinou

The Depth Irreducibility Hypothesis

We propose the following computational assumption: in general if we try to compress the depth of a circuit family (parallel time) more than a constant factor we will suffer super-quasi-polynomial blowup in the size (number of processors). This assumption is only slightly stronger than the popular assumption about the robustness ... more >>>

TR98-059 | 15th September 1998
C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer

The Descriptive Complexity Approach to LOGCFL

Building upon the known generalized-quantifier-based first-order
characterization of LOGCFL, we lay the groundwork for a deeper
investigation. Specifically, we examine subclasses of LOGCFL arising
from varying the arity and nesting of groupoidal quantifiers. Our
work extends the elaborate theory relating monoidal quantifiers to
NC^1 and its subclasses. In the ... more >>>

TR06-035 | 19th January 2006
Till Tantau

The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters

The reachability problem for graphs cannot be described, in the
sense of descriptive complexity theory, using a single first-order
formula. This is true both for directed and undirected graphs, both
in the finite and infinite. However, if we restrict ourselves to
graphs in which a certain graph parameter is fixed ... more >>>

TR12-087 | 4th July 2012
Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn

The Deterministic and Randomized Query Complexity of a Simple Guessing Game

Revisions: 1

We study the $\leadingones$ game, a Mastermind-type guessing game first
regarded as a test case in the complexity theory of randomized search
heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a
permutation $\pi$ of $[n]$.
The goal of the second player, Paul, is to ... more >>>

TR17-128 | 15th August 2017
Or Meir

The Direct Sum of Universal Relations

Revisions: 3 , Comments: 1

The universal relation is the communication problem in which Alice and Bob get as inputs two distinct strings, and they are required to find a coordinate on which the strings differ. The study of this problem is motivated by its connection to Karchmer-Wigderson relations, which are communication problems that are ... more >>>

TR05-148 | 6th December 2005
Eric Allender, Samir Datta, Sambuddha Roy

The Directed Planar Reachability Problem

Revisions: 1

We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to ... more >>>

TR11-146 | 1st November 2011
Bireswar Das, Manjish Pal, Vijay Visavaliya

The Entropy Influence Conjecture Revisited

In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$
satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai (Proc. AMS'96)\cite{FG96}. The conjecture says that the Entropy of a boolean function is at most a constant times the Influence of ... more >>>

TR10-128 | 15th August 2010
Scott Aaronson

The Equivalence of Sampling and Searching

Revisions: 1

In a sampling problem, we are given an input $x\in\left\{0,1\right\} ^{n}$, and asked to sample approximately from a probability
distribution $D_{x}$ over poly(n)-bit strings. In a search problem, we are given an input
$x\in\left\{ 0,1\right\} ^{n}$, and asked to find a member of a nonempty set
$A_{x}$ with high probability. ... more >>>

TR05-049 | 1st April 2005
Joan Boyar, rene peralta

The Exact Multiplicative Complexity of the Hamming Weight Function

We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the ... more >>>

TR13-162 | 1st October 2013
Janka Chlebíková, Morgan Chopin

The Firefighter Problem: A Structural Analysis

Revisions: 1

We consider the complexity of the firefighter problem where ${b \geq 1}$ firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al. 2007) and on trees of bounded degree $b+3$ for any fixed budget ... more >>>

TR07-097 | 8th October 2007
Miklos Ajtai, Cynthia Dwork

The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.

We describe a public-key cryptosystem with worst-case/average case
equivalence. The cryptosystem has an amortized plaintext to
ciphertext expansion of $O(n)$, relies on the hardness of the
$\tilde O(n^2)$-unique shortest vector problem for lattices, and
requires a public key of size at most $O(n^4)$ bits. The new
cryptosystem generalizes a conceptually ... more >>>

TR16-025 | 26th February 2016
Shachar Lovett

The Fourier structure of low degree polynomials

Revisions: 1

We study the structure of the Fourier coefficients of low degree multivariate polynomials over finite fields. We consider three properties: (i) the number of nonzero Fourier coefficients; (ii) the sum of the absolute value of the Fourier coefficients; and (iii) the size of the linear subspace spanned by the nonzero ... more >>>

TR12-180 | 21st December 2012
Chaim Even-Zohar, Shachar Lovett

The Freiman-Ruzsa Theorem in Finite Fields

Let $G$ be a finite abelian group of torsion $r$ and let $A$ be a subset of $G$.
The Freiman-Ruzsa theorem asserts that if $|A+A| \le K|A|$
then $A$ is contained in a coset of a subgroup of $G$ of size at most $K^2 r^{K^4} |A|$. It was ... more >>>

TR13-161 | 23rd October 2013
Jack H. Lutz

The Frequent Paucity of Trivial Strings

Revisions: 1

A 1976 theorem of Chaitin, strengthening a 1969 theorem of Meyer,says that infinitely many lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. ... more >>>

TR02-047 | 3rd August 2002
Oded Goldreich

The GGM Construction does NOT yield Correlation Intractable Function Ensembles.

We consider the function ensembles emerging from the
construction of Goldreich, Goldwasser and Micali (GGM),
when applied to an arbitrary pseudoramdon generator.
We show that, in general, such functions
fail to yield correlation intractable ensembles.
Specifically, it may happen that, given a description of such a ... more >>>

TR99-034 | 30th August 1999
Wolfgang Merkle

The global power of additional queries to p-random oracles.

We consider separations of reducibilities in the context of
resource-bounded measure theory. First, we show a result on
polynomial-time bounded reducibilities: for every p-random set R,
there is a set which is reducible to R with k+1 non-adaptive
queries, but is not reducible to any other p-random set with ... more >>>

TR96-054 | 2nd November 1996
Oded Goldreich

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Comments: 1

The Graph Clustering Problem is parameterized by a sequence
of positive integers, $m_1,...,m_t$.
The input is a sequence of $\sum_{i=1}^{t}m_i$ graphs,
and the question is whether the equivalence classes
under the graph isomorphism relation have sizes which match
the sequence of parameters.
In this note
we show ... more >>>

TR98-006 | 27th January 1998
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

The input to the {\em Graph Clustering Problem}\/
consists of a sequence of integers $m_1,...,m_t$
and a sequence of $\sum_{i=1}^{t}m_i$ graphs.
The question is whether the equivalence classes,
under the graph isomorphism relation,
of the input graphs have sizes which match the input sequence of integers.
In this note ... more >>>

TR16-020 | 8th February 2016
Zachary Remscrim

The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

In this paper, we apply tools from algebraic geometry to prove new results concerning extractors for algebraic sets, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over $\mathbb{F}_2$ of substantially higher degree than the ... more >>>

TR07-095 | 13th July 2007
Vikraman Arvind, Partha Mukhopadhyay

The Ideal Membership Problem and Polynomial Identity Testing

Revisions: 2

Given a monomial ideal $I=\angle{m_1,m_2,\cdots,m_k}$ where $m_i$
are monomials and a polynomial $f$ as an arithmetic circuit the
\emph{Ideal Membership Problem } is to test if $f\in I$. We study
this problem and show the following results.
\item[(a)] If the ideal $I=\angle{m_1,m_2,\cdots,m_k}$ for a
more >>>

TR01-104 | 17th December 2001
Irit Dinur, Shmuel Safra

The Importance of Being Biased

We show Minimum Vertex Cover NP-hard to approximate to within a factor
of 1.3606. This improves on the previously known factor of 7/6.

more >>>

TR94-014 | 12th December 1994
Miklos Ajtai

The Independence of the modulo p Counting Principles

The modulo $p$ counting principle is a first-order axiom
schema saying that it is possible to count modulo $p$ the number of
elements of the first-order definable subsets of the universe (and of
the finite Cartesian products of the universe with itself) in a
consistent way. It trivially holds on ... more >>>

TR11-033 | 8th March 2011
Rahul Jain, Shengyu Zhang

The influence lower bound via query elimination

We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function $f$ in terms of the maximum influence of any variable of $f$. Our lower bound also applies to ... more >>>

TR07-018 | 1st March 2007
Christian Glaßer, Alan L. Selman, Liyu Zhang

The Informational Content of Canonical Disjoint NP-Pairs

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions.

Q1: Where does the implication [can(f) \le_m can(g) => f \le_s ... more >>>

TR09-098 | 9th October 2009
Alexander A. Sherstov

The intersection of two halfspaces has high threshold degree

Revisions: 1

The threshold degree of a Boolean function
$f\colon\{0,1\}\to\{-1,+1\}$ is the least degree of a real
polynomial $p$ such $f(x)\equiv\mathrm{sgn}\; p(x).$ We
construct two halfspaces on $\{0,1\}^n$ whose intersection has
threshold degree $\Theta(\sqrt n),$ an exponential improvement on
previous lower bounds. This solves an open problem due to Klivans
(2002) and ... more >>>

TR12-181 | 20th December 2012
Anindya De, Ilias Diakonikolas, Rocco Servedio

The Inverse Shapley Value Problem

For $f$ a weighted voting scheme used by $n$ voters to choose between two candidates, the $n$ \emph{Shapley-Shubik Indices} (or {\em Shapley values}) of $f$ provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley ... more >>>

TR09-053 | 20th May 2009
Johannes Köbler, Sebastian Kuhnert

The Isomorphism Problem for k-Trees is Complete for Logspace

Revisions: 1

We show that k-tree isomorphism can be decided in logarithmic
space by giving a logspace canonical labeling algorithm. This improves
over the previous StUL upper bound and matches the lower bound. As a
consequence, the isomorphism, the automorphism, as well as the
canonization problem for k-trees ... more >>>

TR07-068 | 24th July 2007
Thomas Thierauf, Fabian Wagner

The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class AC^1.

In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to ... more >>>

TR96-040 | 21st May 1996
Thomas Thierauf

The Isomorphismproblem for One-Time-Only Branching Programs

Revisions: 1 , Comments: 1

We investigate the computational complexity of the
isomorphism problem for one-time-only branching programs (BP1-Iso):
on input of two one-time-only branching programs B and B',
decide whether there exists a permutation of the variables of B'
such that it becomes equivalent to B.

Our main result is a two-round interactive ... more >>>

TR16-199 | 15th December 2016
Pavel Hubacek, Moni Naor, Eylon Yogev

The Journey from NP to TFNP Hardness

The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one ... more >>>

TR06-070 | 23rd May 2006
Ludwig Staiger

The Kolmogorov complexity of infinite words

We present a brief survey of results on relations between the Kolmogorov
complexity of infinite strings and several measures of information content
(dimensions) known from dimension theory, information theory or fractal

Special emphasis is laid on bounds on the complexity of strings in
more >>>

TR15-049 | 3rd April 2015
Mika Göös, Toniann Pitassi, Thomas Watson

The Landscape of Communication Complexity Classes

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $P$ and $PSPACE$, short of proving lower bounds against classes for which no explicit lower bounds were already known. Our article also serves as an up-to-date survey on ... more >>>

TR06-106 | 18th August 2006
Scott Aaronson

The Learnability of Quantum States

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible ... more >>>

TR13-153 | 8th November 2013
Mrinal Kumar, Shubhangi Saraf

The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of {\it depth reduction} developed in the works of Agrawal-Vinay [AV08], Koiran [Koi12] and Tavenas [Tav13], and the use of the shifted partial derivative complexity measure ... more >>>

TR11-106 | 6th August 2011
Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

The Limits of Two-Party Differential Privacy

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and ... more >>>

TR96-063 | 6th November 1996
Martin Dietzfelbinger

The Linear-Array Problem in Communication Complexity Resolved

Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k,
connected by k links to form a linear array, compute a function f(x,y), for
inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and
y is only known to P_k; the intermediate ... more >>>

TR08-111 | 14th November 2008
Shachar Lovett, Tali Kaufman

The List-Decoding Size of Reed-Muller Codes

Revisions: 2

In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Previous bounds of Gopalan, Klivans and Zuckerman~\cite{GKZ08} on the ... more >>>

TR03-073 | 11th June 2003
Amin Coja-Oghlan

The Lovasz number of random graph

We study the Lovasz number theta along with two further SDP relaxations $\thetI$, $\thetII$
of the independence number and the corresponding relaxations of the
chromatic number on random graphs G(n,p). We prove that \theta is
concentrated about its mean, and that the relaxations of the chromatic
number in the case ... more >>>

TR17-084 | 2nd May 2017
Iftach Haitner, Salil Vadhan

The Many Entropies in One-Way Functions

Revisions: 1

Computational analogues of information-theoretic notions have given rise to some of the most interesting phenomena in the theory of computation. For example, computational indistinguishability, Goldwasser and Micali '84, which is the computational analogue of statistical distance, enabled the bypassing of Shanon's impossibility results on perfectly secure encryption, and provided the ... more >>>

TR17-059 | 6th April 2017
Ola Svensson, Jakub Tarnawski

The Matching Problem in General Graphs is in Quasi-NC

Revisions: 1

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in $O(\log^3 n)$ time on $n^{O(\log^2 n)}$ processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the ... more >>>

TR09-017 | 20th February 2009
Joshua Brody

The Maximum Communication Complexity of Multi-party Pointer Jumping.

We study the one-way number-on-the-forhead (NOF) communication
complexity of the k-layer pointer jumping problem. Strong lower
bounds for this problem would have important implications in circuit
complexity. All of our results apply to myopic protocols (where
players see only one layer ahead, but can still ... more >>>

TR98-071 | 26th November 1998
Itsik Pe'er, Ron Shamir

The median problems for breakpoints are NP-complete

The breakpoint distance between two $n$-permutations is the number
of pairs that appear consecutively in one but not in the other. In
the median problem for breakpoints one is given a set of
permutations and has to construct a permutation that minimizes the
sum of breakpoint ... more >>>

TR14-176 | 16th December 2014
Eric Allender, Dhiraj Holden, Valentine Kabanets

The Minimum Oracle Circuit Size Problem

We consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP$^{QBF}$ is known to be complete for PSPACE under ZPP reductions. We show that it is not ... more >>>

TR16-110 | 19th July 2016
Alexander Golovnev, Oded Regev, Omri Weinstein

The Minrank of Random Graphs

Revisions: 1

The minrank of a graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching ones to zeros (i.e., deleting edges) and setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of ... more >>>

TR95-059 | 21st November 1995
Nader H. Bshouty

The Monotone Theory for the PAC-Model

We show that a DNF formula that has a CNF representation that contains
at least one ``$1/poly$-heavy''
clause with respect to a distribution $D$ is weakly learnable
under this distribution. So DNF that are not weakly
learnable under the distribution $D$ do not have
any ``$1/poly$-heavy'' clauses in any of ... more >>>

TR16-127 | 12th August 2016
Timothy Gowers, Emanuele Viola

The multiparty communication complexity of interleaved group products

Party $A_i$ of $k$ parties $A_1,\dots,A_k$ receives on
its forehead a $t$-tuple $(a_{i1},\dots,a_{it})$ of
elements from the group $G=\text{SL}(2,q)$. The parties
are promised that the interleaved product $a_{11}\dots
a_{k1}a_{12}\dots a_{k2}\dots a_{1t}\dots a_{kt}$ is
equal either to the identity $e$ or to some other fixed
element $g\in G$. Their goal is ... more >>>

TR11-145 | 2nd November 2011
Alexander A. Sherstov

The Multiparty Communication Complexity of Set Disjointness

We study the set disjointness problem in the number-on-the-forehead model.

(i) We prove that $k$-party set disjointness has randomized and nondeterministic
communication complexity $\Omega(n/4^k)^{1/4}$ and Merlin-Arthur complexity $\Omega(n/4^k)^{1/8}.$
These bounds are close to tight. Previous lower bounds (2007-2008) for $k\geq3$ parties
were weaker than $n^{1/(k+1)}/2^{k^2}$ in all ... more >>>

TR07-082 | 27th July 2007
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Kalai, Vahab Mirrokni, Christos H. Papadimitriou

The Myth of the Folk Theorem

The folk theorem suggests that finding Nash Equilibria
in repeated games should be easier than in one-shot games. In
contrast, we show that the problem of finding any (epsilon) Nash
equilibrium for a three-player infinitely-repeated game is
computationally intractable (even when all payoffs are in
{-1,0,-1}), unless all of PPAD ... more >>>

TR94-022 | 12th December 1994
Christoph Meinel, Stephan Waack

The Möbius Function, Variations Ranks, and Theta(n)--Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem

We prove that the modular communication complexity of the
undirected graph connectivity problem UCONN equals Theta(n),
in contrast to the well-known Theta(n*log n) bound in the
deterministic case, and to the Omega(n*loglog n) lower bound
in the nondeterministic case, recently proved by ... more >>>

TR09-110 | 5th November 2009
Scott Aaronson, Andris Ambainis

The Need for Structure in Quantum Speedups

Revisions: 1

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.

First, we show that for any problem that ... more >>>

TR11-155 | 22nd November 2011
Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen

The NOF Multiparty Communication Complexity of Composed Functions

We study the $k$-party `number on the forehead' communication complexity of composed functions $f \circ \vec{g}$, where $f:\{0,1\}^n \to \{\pm 1\}$, $\vec{g} = (g_1,\ldots,g_n)$, $g_i : \{0,1\}^k \to \{0,1\}$ and for $(x_1,\ldots,x_k) \in (\{0,1\}^n)^k$, $f \circ \vec{g}(x_1,\ldots,x_k) = f(\ldots,g_i(x_{1,i},\ldots,x_{k,i}), \ldots)$. When $\vec{g} = (g,g,\ldots,g)$ we denote $f \circ \vec{g}$ by ... more >>>

TR02-011 | 14th October 2001
Boris Ryabko

The nonprobabilistic approach to learning the best prediction.

The problem of predicting a sequence $x_1, x_2,.... $ where each $x_i$ belongs
to a finite alphabet $A$ is considered. Each letter $x_{t+1}$ is predicted
using information on the word $x_1, x_2, ...., x_t $ only. We use the game
theoretical interpretation which can be traced to Laplace where there ... more >>>

TR05-128 | 27th October 2005
Miroslava Sotáková

The normal form of reversible circuits consisting of CNOT and NOT gates

This paper deals with the reversible circuits with n input and
output nodes, consisting of the reversible gates FAN-IN=FAN-OUT<3.
We define a normal form of such type of circuits and describe a reduction
algorithm to transform a circuit in this form. Furthermore we use it for
checking whether two circuits ... more >>>

TR95-007 | 1st January 1995
U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern


The {\it nucleon} is introduced as a new allocation concept for
non-negative cooperative n-person transferable utility games.
The nucleon may be viewed as the multiplicative analogue of
Schmeidler's nucleolus.
It is shown that the nucleon of (not necessarily bipartite) matching
games ... more >>>

TR95-047 | 5th October 1995
Martin Loebbing, Ingo Wegener

The Number of Knight's Tours Equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams

An increasing number of results in graph theory, combinatorics and
theoretical computer science is obtained with the help of computers,
e.g. the proof of the Four Colours Theorem or the computation of
certain Ramsey numbers. Binary decision diagrams, known as tools in
hardware verification ... more >>>

TR06-087 | 25th July 2006
Iordanis Kerenidis, Ran Raz

The one-way communication complexity of the Boolean Hidden Matching Problem

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for ... more >>>

TR97-025 | 26th May 1997
Harald Hempel, Gerd Wechsung

The Operators min and max on the Polynomial Hierarchy

We define a general maximization operator max and a general minimization
operator min for complexity classes and study the inclusion structure of
the classes max.P, max.NP, max.coNP, min.P, min.NP, and min.coNP.
It turns out that Krentel's class OptP fits naturally into this frame-
work (it can be ... more >>>

TR07-110 | 24th October 2007
Beate Bollig

The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function

Branching programs are computation models
measuring the space of (Turing machine) computations.
Read-once branching programs (BP1s) are the
most general model where each graph-theoretical path is the computation
path for some input. Exponential lower bounds on the size of read-once
branching programs are known since a long time. Nevertheless, there ... more >>>

TR16-194 | 4th December 2016
Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan

The Optimality of Correlated Sampling

In the "correlated sampling" problem, two players, say Alice and Bob, are given two distributions, say $P$ and $Q$ respectively, over the same universe and access to shared randomness. The two players are required to output two elements, without any interaction, sampled according to their respective distributions, while trying to ... more >>>

TR96-028 | 9th April 1996
Sanjeev Khanna, Madhu Sudan

The Optimization Complexity of Constraint Satisfaction Problems

In 1978, Schaefer considered a subclass of languages in
NP and proved a ``dichotomy theorem'' for this class. The subclass
considered were problems expressible as ``constraint satisfaction
problems'', and the ``dichotomy theorem'' showed that every language in
this class is either in P, or is NP-hard. This result is in ... more >>>

TR08-052 | 29th April 2008
Vikraman Arvind, T.C. Vijayaraghavan

The Orbit problem is in the GapL Hierarchy

Revisions: 1

The \emph{Orbit problem} is defined as follows: Given a matrix $A\in
\Q ^{n\times n}$ and vectors $\x,\y\in \Q ^n$, does there exist a
non-negative integer $i$ such that $A^i\x=\y$. This problem was
shown to be in deterministic polynomial time by Kannan and Lipton in
\cite{KL1986}. In this paper we place ... more >>>

TR13-149 | 28th October 2013
Albert Atserias, Neil Thapen

The Ordering Principle in a Fragment of Approximate Counting

The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk ... more >>>

TR95-013 | 24th February 1995
Oleg Verbitsky

The Parallel Repetition Conjecture for Trees is True

The parallel repetition conjecture (PRC) of Feige and Lovasz says that the
error probability of a two prover one round interactive protocol repeated $n$
times in parallel is exponentially small in $n$.
We show that the PRC is true in the case when
the bipartite graph of dependence between ... more >>>

TR11-071 | 27th April 2011
Serge Gaspers, Stefan Szeider

The Parameterized Complexity of Local Consistency

Revisions: 1

We investigate the parameterized complexity of deciding whether a constraint network is $k$-consistent. We show that, parameterized by $k$, the problem is complete for the complexity class co-W[2]. As secondary parameters we consider the maximum domain size $d$ and the maximum number $\ell$ of constraints in which a variable occurs. ... more >>>

TR07-100 | 25th September 2007
Alexander A. Sherstov

The Pattern Matrix Method for Lower Bounds on Quantum Communication

In a breakthrough result, Razborov (2003) gave optimal
lower bounds on the communication complexity of every function f
of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in
the bounded-error quantum model with and without prior entanglement.
This was proved by the _multidimensional_ discrepancy method. We
give an entirely ... more >>>

TR05-046 | 17th April 2005
Irit Dinur

The PCP theorem by gap amplification

Revisions: 1 , Comments: 3

Let C={c_1,...,c_n} be a set of constraints over a set of
variables. The {\em satisfiability-gap} of C is the smallest
fraction of unsatisfied constraints, ranging over all possible
assignments for the variables.

We prove a new combinatorial amplification lemma that doubles the
satisfiability-gap of a constraint-system, with only a linear ... more >>>

TR09-051 | 2nd July 2009
Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy

The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.
The Kolmogorov measures that have been ... more >>>

TR96-013 | 14th February 1996
Mitsunori Ogihara

The PL Hierarchy Collapses

It is shown that the PL hierarchy defined in terms of the
standard Ruzzo-Simon-Tompa relativization collapses to PL.

more >>>

TR17-169 | 24th October 2017
Mark Bun, Robin Kothari, Justin Thaler

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. The approximate degree of $f$ is known to be a lower bound on the quantum query complexity of $f$ (Beals et al., FOCS 1998 and ... more >>>

TR06-129 | 6th October 2006
Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf

The polynomially bounded perfect matching problem is in NC^2

The perfect matching problem is known to
be in P, in randomized NC, and it is hard for NL.
Whether the perfect matching problem is in NC is one of
the most prominent open questions in complexity
theory regarding parallel computations.

Grigoriev and Karpinski studied the perfect matching problem
more >>>

TR15-147 | 8th September 2015
Alexander A. Sherstov

The Power of Asymmetry in 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)$. Introduced
in the seminal work of Minsky and Papert (1969), this notion is central to
some of the strongest algorithmic and complexity-theoretic results for
more >>>

TR09-036 | 14th April 2009
Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

The Power of Depth 2 Circuits over Algebras

We study the problem of polynomial identity testing (PIT) for depth
2 arithmetic circuits over matrix algebra. We show that identity
testing of depth 3 (Sigma-Pi-Sigma) arithmetic circuits over a field
F is polynomial time equivalent to identity testing of depth 2
(Pi-Sigma) arithmetic circuits over U_2(F), the ... more >>>

TR95-037 | 2nd July 1995
Richard Beigel, Howard Straubing

The Power of Local Self-Reductions

Identify a string x over {0,1} with the positive integer
whose binary representation is 1x. We say that a self-reduction is
k-local if on input x all queries belong to {x-1,...,x-k}. We show
that all k-locally self-reducible sets belong to PSPACE. However, the
power of k-local self-reductions changes drastically between ... more >>>

TR17-023 | 15th February 2017
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

The Power of Natural Properties as Oracles

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP).
We obtain new circuit lower bounds, as well as some hardness results for the relativized version ... more >>>

TR15-008 | 14th January 2015
Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen

The Power of Negations in Cryptography

The study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be ... more >>>

TR10-131 | 9th July 2010
Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki

The Power of Nondeterminism in Self-Assembly

We investigate the role of nondeterminism in Winfree's abstract Tile Assembly Model (aTAM), which was conceived to model artificial molecular self-assembling systems constructed from DNA. Designing tile systems that assemble shapes, due to the algorithmic richness of the aTAM, is a form of sophisticated "molecular programming". Of particular practical importance ... more >>>

TR17-081 | 2nd May 2017
Badih Ghazi, Madhu Sudan

The Power of Shared Randomness in Uncertain Communication

In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function ... more >>>

TR14-064 | 24th April 2014
Arkadev Chattopadhyay, Michael Saks

The Power of Super-logarithmic Number of Players

In the `Number-on-Forehead' (NOF) model of multiparty communication, the input is a $k \times m$ boolean matrix $A$ (where $k$ is the number of players) and Player $i$ sees all bits except those in the $i$-th row, and the players communicate by broadcast in order to evaluate a specified ... more >>>

TR08-051 | 4th April 2008
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The Power of Unentanglement

The class QMA(k), introduced by Kobayashi et al., consists
of all languages that can be verified using k unentangled quantum
proofs. Many of the simplest questions about this class have remained
embarrassingly open: for example, can we give any evidence that k
quantum proofs are more powerful than one? Can ... more >>>

TR05-056 | 25th April 2005
Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis

The Price of Optimum in Stackelberg Games

Consider a system M of parallel machines, each with a strictly increasing and differentiable load dependent latency function. The users of such a system are of infinite number and act selfishly, routing their infinitesimally small portion of the total flow r they control, to machines of currently minimum delay. It ... more >>>

TR10-034 | 7th March 2010
Luca Trevisan

The Program-Enumeration Bottleneck in Average-Case Complexity Theory

Three fundamental results of Levin involve algorithms or reductions
whose running time is exponential in the length of certain programs. We study the
question of whether such dependency can be made polynomial.

(1) Levin's ``optimal search algorithm'' performs at most a constant factor more slowly
than any other fixed ... more >>>

TR11-112 | 10th August 2011
Dana Moshkovitz

The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover

In this paper we put forward a conjecture: an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We refer to this conjecture as the Projection Games Conjecture.

We further suggest the research agenda of establishing new hardness of approximation results based on the ... more >>>

TR98-078 | 1st December 1998
Vikraman Arvind, K.V. Subrahmanyam, Vinodchandran Variyam

The Query Complexity of Program Checking by Constant-Depth Circuits

In this paper we study program checking (in the
sense of Blum and Kannan) using constant-depth circuits as
checkers. Our focus is on the number of queries made by the
checker to the program being checked and we term this as the
query complexity of the checker for the given ... more >>>

TR17-080 | 1st May 2017
Joshua Brakensiek, Venkatesan Guruswami

The Quest for Strong Inapproximability Results with Perfect Completeness

The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect ... more >>>

TR14-082 | 3rd June 2014
Yu Yu, Dawu Gu, Xiangxue Li

The Randomized Iterate Revisited - Almost Linear Seed Length PRGs from A Broader Class of One-way Functions

Revisions: 3

We revisit ``the randomized iterate'' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography ... more >>>

TR01-099 | 1st October 2001
Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis

The Range of Stability for Heterogeneous and FIFO Queueing Networks

In this paper, we investigate and analyze for the first time the
stability properties of heterogeneous networks, which use a
combination of different universally stable queueing policies for
packet routing, in the Adversarial Queueing model. We
interestingly prove that the combination of SIS and LIS policies,
LIS and NTS policies, ... more >>>

TR17-154 | 12th October 2017
Christoph Berkholz

The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs

We relate different approaches for proving the unsatisfiability of a system of real polynomial equations over Boolean variables. On the one hand, there are the static proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, we consider polynomial calculus, ... more >>>

TR03-051 | 20th June 2003
Tsuyoshi Morioka

The Relative Complexity of Local Search Heuristics and the Iteration Principle

Johnson, Papadimitriou and Yannakakis introduce the class $\PLS$
consisting of optimization problems for which efficient local-
search heuristics exist. We formulate a type-2 problem $\iter$
that characterizes $\PLS$ in style of Beame et al., and prove
a criterion for type-2 problems to be nonreducible to $\iter$.
As a corollary, ... more >>>

TR09-105 | 27th October 2009
Vikraman Arvind, Srikanth Srinivasan

The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

Using $\epsilon$-bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an $NC^2$ algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace F_n by G^n for an arbitrary fixed ... more >>>

TR04-012 | 19th December 2003
Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore

The Resolution Complexity of Random Graph $k$-Colorability

We consider the resolution proof complexity of propositional formulas which encode random instances of graph $k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity.
For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any $\epsilon>0$, ... more >>>

TR06-133 | 14th October 2006
Alex Hertel, Alasdair Urquhart

The Resolution Width Problem is EXPTIME-Complete

The importance of {\em width} as a resource in resolution theorem proving
has been emphasized in work of Ben-Sasson and Wigderson. Their results show that lower
bounds on the size of resolution refutations can be proved in a uniform manner by
demonstrating lower bounds on the width ... more >>>

TR05-110 | 3rd October 2005
Saurabh Sanghvi, Salil Vadhan

The Round Complexity of Two-Party Random Selection

We study the round complexity of two-party protocols for
generating a random $n$-bit string such that the output is
guaranteed to have bounded bias (according to some measure) even
if one of the two parties deviates from the protocol (even using
unlimited computational resources). Specifically, we require that
the output's ... more >>>

TR97-060 | 2nd December 1997
Manindra Agrawal, Thomas Thierauf

The Satisfiability Problem for Probabilistic Ordered Branching Programs

We show that the satisfiability problem for
bounded error probabilistic ordered branching programs is NP-complete.
If the error is very small however
(more precisely,
if the error is bounded by the reciprocal of the width of the branching program),
then we have a polynomial-time algorithm for the satisfiability problem.
more >>>

TR99-037 | 27th August 1999
Johan Hastad, Mats Näslund

The Security of all RSA and Discrete Log Bits

We study the security of individual bits in an
RSA encrypted message $E_N(x)$. We show that given $E_N(x)$,
predicting any single bit in $x$ with only a non-negligible
advantage over the trivial guessing strategy, is (through a
polynomial time reduction) as hard as breaking ... more >>>

TR10-169 | 10th November 2010
Siavosh Benabbas, Konstantinos Georgiou, Avner Magen

The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs

Revisions: 2

We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector
chromatic number $2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali-Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to
$O(1/ \epsilon)$ tightenings we show ... more >>>

TR15-118 | 23rd July 2015
Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan

The shifted partial derivative complexity of Elementary Symmetric Polynomials

We continue the study of the shifted partial derivative measure, introduced by Kayal (ECCC 2012), which has been used to prove many strong depth-4 circuit lower bounds starting from the work of Kayal, and that of Gupta et al. (CCC 2013).

We show a strong lower bound on the dimension ... more >>>

TR98-016 | 24th March 1998
Daniele Micciancio

The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.

We show that computing the approximate length of the shortest vector
in a lattice within a factor c is NP-hard for randomized reductions
for any constant c<sqrt(2). We also give a deterministic reduction
based on a number theoretic conjecture.

more >>>

TR97-047 | 20th October 1997
Miklos Ajtai

The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions.

Revisions: 1

We show that the shortest vector problem in lattices
with L_2 norm is NP-hard for randomized reductions. Moreover we
also show that there is a positive absolute constant c, so that to
find a vector which is longer than the shortest non-zero vector by no
more than a factor of ... more >>>

TR08-029 | 7th January 2008
Christian Glaßer, Christian Reitwießner, Victor Selivanov

The Shrinking Property for NP and coNP

We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results.

1. NP ... more >>>

TR08-016 | 26th February 2008
Alexander Razborov, Alexander A. Sherstov

The Sign-Rank of AC^0

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries
is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0
for all i,j. We obtain the first exponential lower bound on the
sign-rank of a function in AC^0. Namely, let
f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}).
We show that the matrix [f(x,y)]_{x,y} has ... more >>>

TR15-083 | 14th May 2015
Omri Weinstein, David Woodruff

The Simultaneous Communication of Disjointness with Applications to Data Streams

We study $k$-party set disjointness in the simultaneous message-passing model, and show that even if each element $i\in[n]$ is guaranteed to either belong to all $k$ parties or to at most $O(1)$ parties in expectation (and to at most $O(\log n)$ parties with high probability), then $\Omega(n \min(\log 1/\delta, \log ... more >>>

TR03-063 | 2nd July 2003
John Hitchcock

The Size of SPP

Derandomization techniques are used to show that at least one of the
following holds regarding the size of the counting complexity class
1. SPP has p-measure 0.
2. PH is contained in SPP.
In other words, SPP is small by being a negligible subset of
exponential time or large ... more >>>

TR14-181 | 19th December 2014
Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee

The space "just above" BQP

We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the ... more >>>

TR14-138 | 29th October 2014
Nicola Galesi, Pavel Pudlak, Neil Thapen

The space complexity of cutting planes refutations

We study the space complexity of the cutting planes proof system, in which the lines in a proof are integral linear inequalities. We measure the space used by a refutation as the number of inequalities that need to be kept on a blackboard while verifying it. We show that any ... more >>>

TR10-071 | 19th April 2010
Rahul Jain, Ashwin Nayak

The space complexity of recognizing well-parenthesized expressions

Revisions: 4

We show an Omega(sqrt(n)/T^3) lower bound for the space required by any
unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well-parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak
(2009) and rigorously establishes the peculiar power of bi-directional streams ... more >>>

TR04-067 | 20th July 2004
hadi salmasian, ravindran kannan, Santosh Vempala

The Spectral Method for Mixture Models

We present an algorithm for learning a mixture of distributions.
The algorithm is based on spectral projection and
is efficient when the components of the mixture are logconcave

more >>>

TR12-174 | 12th December 2012
Anat Ganor, Ilan Komargodski, Ran Raz

The Spectrum of Small DeMorgan Formulas

Revisions: 1

We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size $s$ is concentrated on coefficients of degree up to ... more >>>

TR06-001 | 1st January 2006
Ran Raz, Iddo Tzameret

The Strength of Multilinear Proofs

We introduce an algebraic proof system that manipulates multilinear arithmetic formulas. We show that this proof system is fairly strong, even when restricted to multilinear arithmetic formulas of a very small depth. Specifically, we show the following:

1. Algebraic proofs manipulating depth 2 multilinear arithmetic formulas polynomially simulate Resolution, Polynomial ... more >>>

TR12-162 | 26th October 2012
Hans-Joachim Boeckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock

The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity

Revisions: 1

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an online algorithm. Depending on the input string, the oracle prepares an ... more >>>

TR95-005 | 1st January 1995
Maciej Liskiewicz, Rüdiger Reischuk

The Sublogarithmic Alternating Space World

This paper tries to fully characterize the properties and relationships
of space classes defined by Turing machines that use less than
logarithmic space - may they be deterministic,
nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ... more >>>

TR07-132 | 8th December 2007
Emanuele Viola

The sum of d small-bias generators fools polynomials of degree d

We prove that the sum of $d$ small-bias generators $L
: \F^s \to \F^n$ fools degree-$d$ polynomials in $n$
variables over a prime field $\F$, for any fixed
degree $d$ and field $\F$, including $\F = \F_2 =

Our result improves on both the work by Bogdanov and
Viola ... more >>>

TR07-062 | 15th July 2007
Oded Goldreich, Or Meir

The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable

Revisions: 2

Given two codes R,C, their tensor product $R \otimes C$ consists of all matrices whose rows are codewords of R and whose columns are codewords of C. The product $R \otimes C$ is said to be robust if for every matrix M that is far from $R \otimes C$ it ... more >>>

TR08-028 | 5th December 2007
Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments

In a seminal paper from 1985, Sistla and Clarke showed
that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete
or PSPACE-complete, depending on the set of temporal operators used.
If, in contrast, the set of propositional operators is restricted, the complexity may decrease.
... more >>>

TR13-144 | 8th October 2013
VyasRam Selvam

The two queries assumption and Arthur-Merlin classes

We explore the implications of the two queries assumption, $P^{NP[1]}=P_{||}^{NP[2]}$, with respect to the polynomial hierarchy and the classes $AM$ and $MA$.
We prove the following results:

1. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $AM = MA$
2. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH \subset MA_{/1}$
3. $\exists\;B\;P^{NP[1]^B}=P^{NP[2]^B}$ and $NP^B \not\subseteq coMA^B$.
4. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH ... more >>>

TR16-015 | 4th February 2016
Oded Goldreich

The uniform distribution is complete with respect to testing identity to a fixed distribution

Revisions: 3

Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the ... more >>>

TR14-100 | 4th August 2014
Salman Beigi, Omid Etesami, Amin Gohari

The Value of Help Bits in Randomized and Average-Case Complexity

"Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity.

Amir, Beigel, and Gasarch ... more >>>

TR16-147 | 19th September 2016
Ryan O'Donnell, A. C. Cem Say

The weakness of CTC qubits and the power of approximate counting

Revisions: 1

We present two results in structural complexity theory concerned with the following interrelated
topics: computation with postselection/restarting, closed timelike curves (CTCs), and
approximate counting. The first result is a new characterization of the lesser known complexity
class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of ... more >>>

TR16-103 | 6th July 2016
Jaikumar Radhakrishnan, Swagato Sanyal

The zero-error randomized query complexity of the pointer function.

The pointer function of G{\"{o}}{\"{o}}s, Pitassi and Watson
\cite{DBLP:journals/eccc/GoosP015a} and its variants have recently
been used to prove separation results among various measures of
complexity such as deterministic, randomized and quantum query
complexities, exact and approximate polynomial degrees, etc. In
particular, the widest possible (quadratic) separations between
deterministic and zero-error ... more >>>

TR96-017 | 19th February 1996
Christoph Meinel, Stephan Waack

The ``Log Rank'' Conjecture for Modular Communication Complexity

The ``log rank'' conjecture consists in the question how exact
the deterministic communication complexity of a problem can be
determinied in terms of algebraic invarants of the communication
matrix of this problem. In the following, we answer this question
in the context of modular communication complexity. ... more >>>

TR05-013 | 22nd December 2004
Bin Fu

Theory and Application of Width Bounded Geometric Separator

We introduce the notion of width bounded geometric separator,
develop the techniques for its existence as well as algorithm, and
apply it to obtain a $2^{O(\sqrt{n})}$ time exact algorithm for the
disk covering problem, which seeks to determine the minimal number
of fixed size disks to cover $n$ points on ... more >>>

TR03-039 | 19th May 2003
Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán

Theory Revision with Queries: Horn, Read-once, and Parity Formulas

A theory, in this context, is a Boolean formula; it is
used to classify instances, or truth assignments. Theories
can model real-world phenomena, and can do so more or less
The theory revision, or concept revision, problem is to
correct a given, roughly correct concept.
This problem is ... more >>>

TR11-030 | 9th March 2011
Anna Gal, Andrew Mills

Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length

Locally decodable codes
are error correcting codes with the extra property that, in order
to retrieve the correct value of just one position of the input with
high probability, it is
sufficient to read a small number of
positions of the corresponding,
possibly corrupted ... more >>>

TR01-010 | 25th January 2001
Oded Goldreich, Luca Trevisan

Three Theorems regarding Testing Graph Properties.

Revisions: 1

Property testing is a relaxation of decision problems
in which it is required to distinguish {\sc yes}-instances
(i.e., objects having a predetermined property) from instances
that are far from any {\sc yes}-instance.
We presents three theorems regarding testing graph
properties in the adjacency matrix representation. ... more >>>

TR95-056 | 26th November 1995
Oded Goldreich

Three XOR-Lemmas -- An Exposition

We provide an exposition of three Lemmas which relate
general properties of distributions
with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,
relates the statistical distance of a distribution from uniform
to the maximum bias of the xor of certain bit positions.
more >>>

TR05-139 | 21st November 2005
Constantinos Daskalakis, Christos H. Papadimitriou

Three-Player Games Are Hard

We prove that computing a Nash equilibrium in a 3-player
game is PPAD-complete, solving a problem left open in our recent result on the complexity of Nash equilibria.

more >>>

TR02-040 | 20th June 2002
Lars Engebretsen, Jonas Holmerin

Three-Query PCPs with Perfect Completeness over non-Boolean Domains

We study non-Boolean PCPs that have perfect completeness and read
three positions from the proof. For the case when the proof consists
of values from a domain of size d for some integer constant d
>= 2, we construct a non-adaptive PCP with perfect completeness
more >>>

TR15-034 | 8th March 2015
Xin Li

Three-Source Extractors for Polylogarithmic Min-Entropy

We continue the study of constructing explicit extractors for independent
general weak random sources. The ultimate goal is to give a construction that matches what is given by the probabilistic method --- an extractor for two independent $n$-bit weak random sources with min-entropy as small as $\log n+O(1)$. Previously, the ... more >>>

TR16-131 | 21st August 2016
Andrej Bogdanov, Siyao Guo, Ilan Komargodski

Threshold Secret Sharing Requires a Linear Size Alphabet

We prove that for every $n$ and $1 < t < n$ any $t$-out-of-$n$ threshold secret sharing scheme for one-bit secrets requires share size $\log(t + 1)$. Our bound is tight when $t = n - 1$ and $n$ is a prime power. In 1990 Kilian and Nisan proved ... more >>>

TR11-098 | 11th July 2011
Marek Karpinski, Richard Schmied, Claus Viehmann

Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.

more >>>

TR16-033 | 10th March 2016
Venkatesan Guruswami, Jaikumar Radhakrishnan

Tight bounds for communication assisted agreement distillation

Suppose Alice holds a uniformly random string $X \in \{0,1\}^N$ and Bob holds a noisy version $Y$ of $X$ where each bit of $X$ is flipped independently with probability $\epsilon \in [0,1/2]$. Alice and Bob would like to extract a common random string of min-entropy at least $k$. In this ... more >>>

TR12-185 | 29th December 2012
Siu Man Chan, Aaron Potechin

Tight Bounds for Monotone Switching Networks via Fourier Analysis

We prove tight size bounds on monotone switching networks for the NP-complete problem of
$k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height $h$ for
the P-complete problem of generation. This gives alternative proofs of the separations of m-NC
from m-P and of m-NC$^i$ from ... more >>>

TR11-150 | 4th November 2011
Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code
$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,
using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>

TR10-063 | 12th April 2010
Venkatesan Guruswami, Yuan Zhou

Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}

Revisions: 1

We study the approximability of two natural Boolean constraint satisfaction problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a {\em
near-satisfiable} instance.

\item ... more >>>

TR14-174 | 14th December 2014
Avishay Tal

Tight bounds on The Fourier Spectrum of $AC^0$

Revisions: 2

We show that $AC^0$ circuits of depth $d$ and size $m$ have at most $2^{-\Omega(k/(\log m)^{d-1})}$ of their Fourier mass at level $k$ or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case $k=n$. Our result is tight up ... more >>>

TR11-011 | 1st February 2011
Ming Lam Leung, Yang Li, Shengyu Zhang

Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models

We study the communication complexity of symmetric XOR functions, namely functions $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D: \{0,1,...,n\} \rightarrow \{0,1\}$, where $|x\oplus y|$ is the Hamming weight of the bitwise XOR of $x$ and $y$. We give a public-coin ... more >>>

TR06-132 | 17th October 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut

Revisions: 1

We study linear programming relaxations of Vertex Cover and Max Cut
arising from repeated applications of the ``lift-and-project''
method of Lovasz and Schrijver starting from the standard linear
programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that
the integrality gap remains at least $2-\epsilon$ after
$\Omega_\epsilon(\log n)$ ... more >>>

TR06-152 | 6th December 2006
Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1).

more >>>

TR11-054 | 13th April 2011
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

Tight lower bounds for 2-query LCCs over finite fields

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic
self-correcting algorithm that, with high probability, can correct any coordinate of the
codeword by looking at only a few other coordinates, even if a fraction $\delta$ of the
coordinates are corrupted. LCC's are a stronger form ... more >>>

TR07-090 | 11th September 2007
Shachar Lovett

Tight lower bounds for adaptive linearity tests

Revisions: 1 , Comments: 1

Linearity tests are randomized algorithms which have oracle access to the truth table of some function $f$,
which are supposed to distinguish between linear functions and functions which are far from linear. Linearity tests were first introduced by Blum, Luby and Rubenfeld in \cite{BLR93}, and were later used in the ... more >>>

TR13-090 | 18th June 2013
Elena Grigorescu, Karl Wimmer, Ning Xie

Tight Lower Bounds for Testing Linear Isomorphism

We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. A family of functions $P\subseteq \{\{0,1\}^n \rightarrow \{0,1\}\}$ is linear/affine invariant if for any $f\in P$, it is the case that $f\circ L\in P$ for any linear/affine transformation $L$ of the domain. Motivated by ... more >>>

TR03-035 | 21st May 2003
Eran Halperin, Guy Kortsarz, Robert Krauthgamer

Tight lower bounds for the asymmetric k-center problem

In the {\sc $k$-center} problem, the input is a bound $k$
and $n$ points with the distance between every two of them,
such that the distances obey the triangle inequality.
The goal is to choose a set of $k$ points to serve as centers,
so that the maximum distance ... more >>>

TR16-130 | 11th August 2016
Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

Tight Network Topology Dependent Bounds on Rounds of Communication

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent ... more >>>

TR09-109 | 3rd November 2009
Kai-Min Chung, Feng-Hao Liu

Tight Parallel Repetition Theorems for Public-coin Arguments

Following Hastad, Pass, Pietrzak, and Wikstrom (2008), we study parallel repetition theorems for public-coin interactive arguments and their generalization. We obtain the following results:

1. We show that the reduction of Hastad et al. actually gives a tight direct product theorem for public-coin interactive arguments. That is, $n$-fold parallel repetition ... more >>>

TR15-053 | 7th April 2015
Massimo Lauria, Jakob Nordström

Tight Size-Degree Bounds for Sums-of-Squares Proofs

We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size n^{Omega(d)} for values of d = d(n) from constant all the way up to n^{delta} for some universal constant delta. This shows that ... more >>>

TR17-168 | 5th November 2017
Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri

Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Di erentially Private Sampling

Revisions: 5

In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by ?(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner ... more >>>

TR14-152 | 13th November 2014
Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo

Tighter Relations Between Sensitivity and Other Complexity Measures

Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other major complexity measures. Despite much attention to the problem and major advances ... more >>>

TR05-054 | 19th May 2005
Konstantin Pervyshev

Time Hierarchies for Computations with a Bit of Advice

A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any constants a and b such that 1 < a < b, ZPTime[n^a]/1 \subsetneq ZPTime[n^b]/1.

The technique introduced in this paper is very general and gives the same hierarchy for NTime \cap coNTime, UTime, ... more >>>

TR05-076 | 2nd July 2005
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

Time hierarchies for cryptographic function inversion with advice

We prove a time hierarchy theorem for inverting functions
computable in polynomial time with one bit of advice.
In particular, we prove that if there is a strongly
one-way function, then for any k and for any polynomial p,
there is a function f computable in linear time
with one ... more >>>

TR12-026 | 27th March 2012
Thomas Watson

Time Hierarchies for Sampling Distributions

Revisions: 2

We prove that for every constant $k\ge 2$, every polynomial time bound $t$, and every polynomially small $\epsilon$, there exists a family of distributions on $k$ elements that can be sampled exactly in polynomial time but cannot be sampled within statistical distance $1-1/k-\epsilon$ in time $t$. Our proof involves reducing ... more >>>

TR07-004 | 12th January 2007
Lance Fortnow, Rahul Santhanam

Time Hierarchies: A Survey

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes.

more >>>

TR05-144 | 5th December 2005
Lance Fortnow, Luis Antunes

Time-Bounded Universal Distributions

We show that under a reasonable hardness assumptions, the time-bounded Kolmogorov distribution is a universal samplable distribution. Under the same assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all P-samplable distributions.

more >>>

TR10-147 | 22nd September 2010
Dieter van Melkebeek, Thomas Watson

Time-Space Efficient Simulations of Quantum Computations

Revisions: 1

We give two time- and space-efficient simulations of quantum computations with
intermediate measurements, one by classical randomized computations with
unbounded error and the other by quantum computations that use an arbitrary
fixed universal set of gates. Specifically, our simulations show that every
language solvable by a bounded-error quantum algorithm running ... more >>>

TR16-113 | 22nd July 2016
Gillat Kol, Ran Raz, Avishay Tal

Time-Space Hardness of Learning Sparse Parities

We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ requires either a memory of size super-linear in $n$ or a number of samples super-polynomial in $n$, where $n$ is the length of one sample.

A recent work shows ... more >>>

TR98-053 | 30th August 1998
Paul Beame, Michael Saks, Jayram S. Thathachar

Time-Space Tradeoffs for Branching Programs

Comments: 1

We obtain the first non-trivial time-space tradeoff lower bound for
functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a
Boolean function f that requires exponential size to be computed by any
branching program of length cn, for some constant c>1. We also give the first
separation result between the ... more >>>

TR07-036 | 6th April 2007
Ryan Williams

Time-Space Tradeoffs for Counting NP Solutions Modulo Integers

We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for Sat. Let m be a positive integer, and define MODm-Sat to be the problem of determining if a given Boolean formula has ... more >>>

TR17-120 | 31st July 2017
Paul Beame, Shayan Oveis Gharan, Xin Yang

Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions

Revisions: 1

We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior ... more >>>

TR00-028 | 17th April 2000
Lance Fortnow, Dieter van Melkebeek

Time-Space Tradeoffs for Nondeterministic Computation

We show new tradeoffs for satisfiability and nondeterministic
linear time. Satisfiability cannot be solved on general purpose
random-access Turing machines in time $n^{1.618}$ and space
$n^{o(1)}$. This improves recent results of Lipton and Viglas and

more >>>

TR12-027 | 29th March 2012
Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang

Time-space tradeoffs for width-parameterized SAT:Algorithms and lower bounds

Revisions: 2

A decade has passed since Alekhnovich and Razborov presented an algorithm that solves SAT on instances $\phi$ of size $n$ having tree-width $TW(\phi)$, using time (and space) bounded by $2^{O(TW(\phi))}n^{O(1)}$. Although there have been several papers over the ensuing years building on the work of Alekhnovich and Razborov there has ... more >>>

TR11-149 | 4th November 2011
Paul Beame, Chris Beck, Russell Impagliazzo

Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have Resolution refutations of space and size each roughly $N^{\log_2 N}$ (and like all formulas have Resolution refutations of space $N$) for ... more >>>

TR01-041 | 23rd May 2001
Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V. Vinay

Time-Space Tradeoffs in the Counting Hierarchy

We extend the lower bound techniques of [Fortnow], to the
unbounded-error probabilistic model. A key step in the argument
is a generalization of Nepomnjascii's theorem from the Boolean
setting to the arithmetic setting. This generalization is made
possible, due to the recent discovery of logspace-uniform TC^0
more >>>

TR94-002 | 12th December 1994
Oded Goldreich, Avi Wigderson

Tiny Families of Functions with Random Properties: A Quality--Size Trade--off for Hashing

Revisions: 2

We present three explicit constructions of hash functions,
which exhibit a trade-off between the size of the family
(and hence the number of random bits needed to generate a member of the family),
and the quality (or error parameter) of the pseudo-random property it
achieves. Unlike previous constructions, ... more >>>

TR09-118 | 18th November 2009
Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin

Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

Revisions: 1

We study the computational power of polynomial threshold functions, that is, threshold functions of real polynomials over the boolean cube. We provide two new results bounding the computational power of this model.
Our first result shows that low-degree polynomial threshold functions cannot approximate any function with many influential variables. We ... more >>>

TR16-105 | 13th July 2016
Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

Revisions: 1

The function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $\epsilon$-close to some $k$-junta and reject any function that is $\epsilon'$-far from ... more >>>

TR05-019 | 9th February 2005
Venkatesan Guruswami, Atri Rudra

Tolerant Locally Testable Codes

An error-correcting code is said to be {\em locally testable} if it has an
efficient spot-checking procedure that can distinguish codewords
from strings that are far from every codeword, looking at very few
locations of the input in doing so. Locally testable codes (LTCs) have
generated ... more >>>

TR04-010 | 26th January 2004
Michal Parnas, Dana Ron, Ronitt Rubinfeld

Tolerant Property Testing and Distance Approximation

A standard property testing algorithm is required to determine
with high probability whether a given object has property
P or whether it is \epsilon-far from having P, for any given
distance parameter \epsilon. An object is said to be \epsilon-far
from having ... more >>>

TR04-105 | 19th November 2004
Eldar Fischer, Lance Fortnow

Tolerant Versus Intolerant Testing for Boolean Properties

A property tester with high probability accepts inputs satisfying a given property and rejects
inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron
and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We
construct properties of binary functions ... more >>>

TR04-108 | 24th November 2004
Eric Allender, Samir Datta, Sambuddha Roy

Topology inside NC^1

We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model.
We consider other generalizations of ... more >>>

TR14-074 | 14th May 2014
Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

Topology matters in communication

We provide the first communication lower bounds that are sensitive to the network topology for computing natural and simple functions by point to point message passing protocols for the `Number in Hand' model. All previous lower bounds were either for the broadcast model or assumed full connectivity of the network. ... more >>>

TR14-038 | 24th March 2014
Ilario Bonacina, Nicola Galesi, Neil Thapen

Total space in resolution

Revisions: 1

We show $\Omega(n^2)$ lower bounds on the total space used in resolution refutations of random $k$-CNFs over $n$ variables, and of the graph pigeonhole principle and the bit pigeonhole principle for $n$ holes. This answers the long-standing open problem of whether there are families of $k$-CNF formulas of size $O(n)$ ... more >>>

TR16-057 | 11th April 2016
Ilario Bonacina

Total space in Resolution is at least width squared

Given an unsatisfiable $k$-CNF formula $\phi$ we consider two complexity measures in Resolution: width and total space. The width is the minimal $W$ such that there exists a Resolution refutation of $\phi$ with clauses of at most $W$ literals. The total space is the minimal size $T$ of a memory ... more >>>

TR01-070 | 24th October 2001
Robert Albin Legenstein

Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing

We introduce em total wire length as salient complexity measure
for analyzing the circuit complexity of sensory processing in
biological neural systems and neuromorphic engineering. The new
complexity measure is applied in this paper to two basic
computational problems that arise in translation- and
scale-invariant pattern recognition, and hence appear ... more >>>

TR09-038 | 14th April 2009
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen

Toward a Model for Backtracking and Dynamic Programming

We propose a model called priority branching trees (pBT ) for backtracking and dynamic
programming algorithms. Our model generalizes both the priority model of Borodin, Nielson
and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence
spans a wide spectrum of algorithms. After witnessing the ... 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 >>>

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

TR15-107 | 21st June 2015
Sagnik Mukhopadhyay, Swagato Sanyal

Towards Better Separation between Deterministic and Randomized Query Complexity

We show that there exists a Boolean function $F$ which observes the following separations among deterministic query complexity $(D(F))$, randomized zero error query complexity $(R_0(F))$
and randomized one-sided error query complexity $(R_1(F))$: $R_1(F) = \widetilde{O}(\sqrt{D(F)})$ and $R_0(F)=\widetilde{O}(D(F))^{3/4}$. This refutes the conjecture made by
Saks and Wigderson that for any Boolean ... more >>>

TR15-105 | 21st June 2015
Venkatesan Guruswami, Euiwoong Lee

Towards a Characterization of Approximation Resistance for Symmetric CSPs

A Boolean constraint satisfaction problem (CSP) is called approximation resistant if independently setting variables to $1$ with some probability $\alpha$ achieves the best possible approximation ratio for the fraction of constraints satisfied. We study approximation resistance of a natural subclass of CSPs that we call Symmetric Constraint Satisfaction Problems (SCSPs), ... more >>>

TR16-198 | 14th December 2016
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

Towards a Proof of the 2-to-1 Games Conjecture?

We propose a combinatorial hypothesis regarding a subspace vs. subspace agreement test, and prove that if correct it leads to a proof of the 2-to-1 Games Conjecture, albeit with imperfect completeness.

more >>>

TR12-179 | 13th December 2012
Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman

Towards a Reverse Newman's Theorem in Interactive Information Complexity

Revisions: 2

Newman’s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and ... more >>>

TR17-056 | 7th April 2017
Paul Goldberg, Christos Papadimitriou

Towards a Unified Complexity Theory of Total Functions

The complexity class TFNP is the set of {\em total function} problems that belong to NP: every input has at least one output and outputs are easy to check for validity, but it may be hard to find an output. TFNP is not believed to have complete problems, but it ... more >>>

TR17-009 | 19th January 2017
Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

Towards an algebraic natural proofs barrier via polynomial identity testing

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>

TR11-014 | 3rd February 2011
Antoine Taveneaux

Towards an axiomatic system for Kolmogorov complexity

Revisions: 1

In \cite{shenpapier82}, it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion. In this paper, we try to extend this work, both by looking at alternative axiomatic systems for plain complexity and by considering potential axiomatic systems ... more >>>

TR12-109 | 31st August 2012
Subhash Khot, Muli Safra, Madhur Tulsiani

Towards An Optimal Query Efficient PCP?

We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16.

At a technical level, our ... more >>>

TR08-026 | 28th February 2008
Jakob Nordström, Johan Hastad

Towards an Optimal Separation of Space and Length in Resolution

Most state-of-the-art satisfiability algorithms today are variants of
the DPLL procedure augmented with clause learning. The main bottleneck
for such algorithms, other than the obvious one of time, is the amount
of memory used. In the field of proof complexity, the resources of
time and memory correspond to the length ... more >>>

TR15-097 | 16th June 2015
Marek Karpinski

Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies

We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the ... more >>>

TR10-166 | 5th November 2010
Mark Braverman, Anup Rao

Towards Coding for Maximum Errors in Interactive Communication

We show that it is possible to encode any communication protocol
between two parties so that the protocol succeeds even if a $(1/4 -
\epsilon)$ fraction of all symbols transmitted by the parties are
corrupted adversarially, at a cost of increasing the communication in
the protocol by a constant factor ... more >>>

TR11-064 | 23rd April 2011
Mark Braverman

Towards deterministic tree code constructions

We present a deterministic operator on tree codes -- we call tree code product -- that allows one to deterministically combine two tree codes into a larger tree code. Moreover, if the original tree codes are efficiently encodable and decodable, then so is their product. This allows us to give ... more >>>

TR07-122 | 22nd November 2007
Zeev Dvir, Amir Shpilka

Towards Dimension Expanders Over Finite Fields

In this paper we study the problem of explicitly constructing a
{\em dimension expander} raised by \cite{BISW}: Let $\mathbb{F}^n$
be the $n$ dimensional linear space over the field $\mathbb{F}$.
Find a small (ideally constant) set of linear transformations from
$\F^n$ to itself $\{A_i\}_{i \in I}$ such that for every linear
more >>>

TR96-029 | 16th April 1996
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

Towards efficient constructions of hitting sets that derandomize BPP

The efficient construction of Hitting Sets for non trivial classes
of boolean functions is a fundamental problem in the theory
of derandomization. Our paper presents a new method to efficiently
construct Hitting Sets for the class of systems of boolean linear
functions. Systems of boolean linear functions ... more >>>

TR06-150 | 4th December 2006
Patrick Briest

Towards Hardness of Envy-Free Pricing

We consider the envy-free pricing problem, in which we want to compute revenue maximizing prices for a set of products P assuming that each consumer from a set of consumer samples C will buy the product maximizing her personal utility, i.e., the difference between her respective budget and the product's ... more >>>

TR10-200 | 14th December 2010
Eli Ben-Sasson, Michael Viderman

Towards lower bounds on locally testable codes via density arguments

The main open problem in the area of locally testable codes (LTCs) is whether there exists an asymptotically good family of LTCs and to resolve this question it suffices to consider the case of query complexity $3$. We argue that to refute the existence of such an asymptotically good family ... more >>>

TR15-165 | 14th October 2015
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson

Towards Optimal Deterministic Coding for Interactive Communication

Revisions: 1

We study \emph{efficient, deterministic} interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length.

For channels that flip bits independently with probability~$\epsilon<1/2$, our coding scheme achieves a communication rate of $1 - O(\sqrt{H({\epsilon})})$ and ... more >>>

TR01-009 | 5th January 2001
Ronen Shaltiel

Towards proving strong direct product theorems

A fundamental question of complexity theory is the direct product
question. Namely weather the assumption that a function $f$ is hard on
average for some computational class (meaning that every algorithm from
the class has small advantage over random guessing when computing $f$)
entails that computing $f$ on ... more >>>

TR04-117 | 1st December 2004
Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and SPARSEST CUT).

We prove strong nonapproximability results in this model for well-known problems such ... more >>>

TR03-082 | 22nd November 2003
Andris Ambainis, Ke Yang

Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information

Entanglement is an essential resource for quantum communication and quantum computation, similar to shared random bits in the classical world. Entanglement distillation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity of these protocols is the minimal amount of classical information that needs to be exchanged for the ... more >>>

TR99-031 | 2nd September 1999
Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger

Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem

The investigation of the possibility to efficiently compute
approximations of hard optimization problems is one of the central
and most fruitful areas of current algorithm and complexity theory.
The aim of this paper is twofold. First, we introduce the notion of
stability of approximation algorithms. This notion is shown to ... more >>>

TR00-070 | 14th July 2000
Peter Auer, Manfred K. Warmuth

Tracking the best disjunction

Littlestone developed a simple deterministic on-line learning
algorithm for learning $k$-literal disjunctions. This algorithm
(called Winnow) keeps one weight for each variable and does
multiplicative updates to its weights. We develop a randomized
version of Winnow and prove bounds for an adaptation of the
algorithm ... more >>>

TR05-059 | 9th May 2005
Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien

Tractable Clones of Polynomials over Semigroups

It is well known that coset-generating relations lead to tractable
constraint satisfaction problems. These are precisely the relations closed
under the operation $xy^{-1}z$ where the multiplication is taken in
some finite group. Bulatov et al. have on the other hand shown that
any clone containing the multiplication of some ``block-group'' ... more >>>

TR02-032 | 17th April 2002
Andrei Bulatov

Tractable Constraint Satisfaction Problems on a 3-element set

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity, and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate ... more >>>

TR16-097 | 15th June 2016
Vivek Anand T Kallampally, Raghunath Tewari

Trading Determinism for Time in Space Bounded Computations

Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}(\log^2 n)$ space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open.
... more >>>

TR08-099 | 19th November 2008
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

Trading GRH for algebra: algorithms for factoring polynomials and related structures

In this paper we develop techniques that eliminate the need of the Generalized
Riemann Hypothesis (GRH) from various (almost all) known results about deterministic
polynomial factoring over finite fields. Our main result shows that given a
polynomial f(x) of degree n over a finite field k, we ... more >>>

TR16-190 | 21st November 2016
Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li

Trading information complexity for error

We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of $\epsilon$.
For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order $\Omega(h(\epsilon))$ and $O(h(\sqrt{\epsilon}))$. ... more >>>

TR15-089 | 31st May 2015
Eldar Fischer, Oded Lachish, Yadu Vadusev

Trading query complexity for sample-based testing and multi-testing scalability}

We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than $1$, power of $n$. Since the query ... more >>>

TR06-155 | 15th December 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP

Revisions: 1

We construct the first constant time value approximation schemes (CTASs) for Metric and Quasi-Metric MAX-rCSP problems for any $r \ge 2$ in a preprocessed metric model of computation, improving over the previous results of [FKKV05] proven for the general core-dense MAX-rCSP problems. They entail also the first sublinear approximation schemes ... more >>>

TR09-046 | 9th May 2009
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Transitive-Closure Spanners of the Hypercube and the Hypergrid

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>

TR07-133 | 20th November 2007
Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

Trapdoors for Hard Lattices and New Cryptographic Constructions

We show how to construct a variety of ``trapdoor'' cryptographic tools
assuming the worst-case hardness of standard lattice problems (such as
approximating the shortest nonzero vector to within small factors).
The applications include trapdoor functions with \emph{preimage
sampling}, simple and efficient ``hash-and-sign'' digital signature
schemes, universally composable oblivious transfer, ... more >>>

TR16-027 | 10th February 2016
Sagnik Mukhopadhyay

Tribes Is Hard in the Message Passing Model

Revisions: 1

We consider the point-to-point message passing model of communication in which there are $k$ processors
with individual private inputs, each $n$-bit long. Each processor is located at the node of an underlying
undirected graph and has access to private random coins. An edge of the graph is a private channel ... more >>>

TR16-123 | 11th August 2016
Stasys Jukna

Tropical Complexity, Sidon Sets, and Dynamic Programming

Many dynamic programming algorithms for discrete 0-1 optimization problems are just special (recursively constructed) tropical (min,+) or (max,+) circuits. A problem is homogeneous if all its feasible solutions have the same number of 1s. Jerrum and Snir [JACM 29 (1982), pp. 874-897] proved that tropical circuit complexity of homogeneous problems ... more >>>

TR05-123 | 25th October 2005
Olaf Beyersdorff

Tuples of Disjoint NP-Sets

Disjoint NP-pairs are a well studied complexity theoretic concept with
important applications in cryptography and propositional proof

In this paper we introduce a natural generalization of the notion of
disjoint NP-pairs to disjoint k-tuples of NP-sets for k>1.
We define subclasses of ... more >>>

TR11-047 | 8th April 2011
Oded Goldreich

Two Comments on Targeted Canonical Derandomizers

We revisit the notion of a {\em targeted canonical derandomizer},
introduced in our recent ECCC Report (TR10-135) as a uniform notion of
a pseudorandom generator that suffices for yielding BPP=P.
The original notion was derived (as a variant of the standard notion
of a canonical derandomizer) by providing both ... more >>>

TR08-071 | 6th August 2008
Dana Moshkovitz, Ran Raz

Two Query PCP with Sub-Constant Error

We show that the NP-Complete language 3Sat has a PCP
verifier that makes two queries to a proof of almost-linear size
and achieves sub-constant probability of error $o(1)$. The
verifier performs only projection tests, meaning that the answer
to the first query determines at most one accepting answer to the
more >>>

TR14-023 | 19th February 2014
Gil Cohen, Anat Ganor, Ran Raz

Two Sides of the Coin Problem

Revisions: 1

In the Coin Problem, one is given n independent flips of a coin that has bias $\beta > 0$ towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply ... more >>>

TR13-145 | 20th October 2013
Gil Cohen, Avishay Tal

Two Structural Results for Low Degree Polynomials and Applications

Revisions: 1

In this paper, two structural results concerning low degree polynomials over the field $\mathbb{F}_2$ are given. The first states that for any degree d polynomial f in n variables, there exists a subspace of $\mathbb{F}_2^n$ with dimension $\Omega(n^{1/(d-1)})$ on which f is constant. This result is shown to be tight. ... more >>>

TR10-007 | 12th January 2010
Atri Rudra, steve uurtamo

Two Theorems in List Decoding

We prove the following results concerning the list decoding of error-correcting codes:

We show that for any code with a relative distance of $\delta$
(over a large enough alphabet), the
following result holds for random errors: With high probability,
for a $\rho\le \delta -\eps$ fraction of random errors (for any ... more >>>

TR04-078 | 3rd August 2004
Henning Fernau

Two-Layer Planarization: Improving on Parameterized Algorithmics

A bipartite graph is biplanar if the vertices can be
placed on two parallel lines in the plane such that there are
no edge crossings when edges are drawn as straight-line segments.
We study two variants of biplanarization problems:
- Two-Layer Planarization TLP: can $k$ edges be deleted from
a ... more >>>

TR12-021 | 14th March 2012
Oded Goldreich, Igor Shinkar

Two-Sided Error Proximity Oblivious Testing

Revisions: 4

Loosely speaking, a proximity-oblivious (property) tester is a randomized algorithm that makes a constant number of queries to a tested object and distinguishes objects that have a predetermined property from those that lack it. Specifically, for some threshold probability $c$, objects having the property are accepted with probability at least ... more >>>

TR05-017 | 28th January 2005
Phuong Nguyen

Two-Sorted Theories for L, SL, NL and P

We introduce ``minimal'' two--sorted first--order theories VL, VSL, VNL and VP
that characterize the classes L, SL, NL and P in the same
way that Buss's $S^i_2$ hierarchy characterizes the polynomial time hierarchy.
Our theories arise from natural combinatorial problems, namely the st-Connectivity
Problem and the Circuit Value Problem.
It ... more >>>

TR15-095 | 14th June 2015
Gil Cohen

Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs

In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of $2\log{n}$-Ramsey graphs on $n$ vertices. Matching Erdös' result with a constructive proof is a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in ... more >>>

TR16-114 | 30th July 2016
Gil Cohen

Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols

Revisions: 1

This paper offers the following contributions:

* We construct a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent $n$-bit sources with min-entropy $\widetilde{O}(\log{n})$. Our construction is optimal up to $\mathrm{poly}(\log\log{n})$ factors and improves upon a recent result by Ben-Aroya, Doron, and Ta-Shma (ECCC'16) that can handle ... more >>>

TR11-035 | 4th March 2011
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Typed Monoids -- An Eilenberg-like Theorem for non regular Languages

Based on different concepts to obtain a finer notion of language recognition via finite monoids we develop an algebraic structure called typed monoid.
This leads to an algebraic description of regular and non regular languages.

We obtain for each language a unique minimal recognizing typed monoid, the typed syntactic monoid.
more >>>

TR03-007 | 15th January 2003
Olivier Dubois, Yacine Boufkhad, Jacques Mandler

Typical random 3-SAT formulae and the satisfiability threshold

$k$-SAT is one of the best known among a wide class of random
constraint satisfaction problems believed to exhibit a threshold
phenomenon where the control parameter is the ratio, number of
constraints to number of variables. There has been a large amount of
work towards estimating ... more >>>

ISSN 1433-8092 | Imprint