Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > C:
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

C
TR98-070 | 7th December 1998
Rüdiger Reischuk

#### Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?

For ordinary circuits with a fixed upper bound on the maximal fanin
of gates it has been shown that logarithmic redundancy is necessary and
sufficient to overcome random hardware faults.
Here, we consider the same question for unbounded fanin circuits that
in the noiseless case can compute ... more >>>

TR16-059 | 14th April 2016
Alon Rosen, Gil Segev, Ido Shahaf

#### Can PPAD Hardness be Based on Standard Cryptographic Assumptions?

Revisions: 1

We consider the question of whether average-case PPAD hardness can be based on standard cryptographic assumptions, such as the existence of one-way functions or public-key encryption. This question is particularly well-motivated in light of new devastating attacks on obfuscation candidates and their underlying building blocks, which are currently the only ... more >>>

TR99-013 | 28th May 1999
Oded Goldreich, Amit Sahai, Salil Vadhan

#### Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK

We extend the study of non-interactive statistical zero-knowledge
proofs. Our main focus is to compare the class NISZK of problems
possessing such non-interactive proofs to the class SZK of problems
possessing interactive statistical zero-knowledge proofs. Along these
lines, we first show that if statistical zero knowledge is non-trivial
then so ... more >>>

TR14-142 | 1st November 2014
Subhash Khot, Dana Moshkovitz

#### Candidate Lasserre Integrality Gap For Unique Games

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.
Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution ... more >>>

TR00-090 | 3rd December 2000
Oded Goldreich

#### Candidate One-Way Functions Based on Expander Graphs

We suggest a candidate one-way function using combinatorial
constructs such as expander graphs. These graphs are used to
determine a sequence of small overlapping subsets of input bits,
to which a hard-wired random predicate is applied.
Thus, the function is extremely easy to evaluate:
all that is needed ... more >>>

TR14-033 | 10th March 2014
Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen

#### Candidate Weak Pseudorandom Functions in $\mathrm{AC}0 \circ \mathrm{MOD}2$

Revisions: 1

Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class $\mathrm{AC}^0( \mathrm{MOD}_2)$. Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications. We study the minimal complexity requirements for ... more >>>

TR04-106 | 19th November 2004
Christian Glaßer, Alan L. Selman, Liyu Zhang

#### Canonical Disjoint NP-Pairs of Propositional Proof Systems

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to
the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is
identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ... more >>>

TR13-118 | 2nd September 2013
Mahdi Cheraghchi, Venkatesan Guruswami

#### Capacity of Non-Malleable Codes

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages $s$ in a manner so that tampering the codeword causes the decoder to either output $s$ or a message that is independent of $s$. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly ... more >>>

TR19-147 | 31st October 2019
Gil Cohen, Shahar Samocha

#### Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

Revisions: 1

We devise a deterministic interactive coding scheme with rate $1-O(\sqrt{\varepsilon\log(1/\varepsilon)})$ against $\varepsilon$-fraction of adversarial errors. The rate we obtain is tight by a result of Kol and Raz (STOC 2013). Prior to this work, deterministic coding schemes for any constant fraction $\varepsilon>0$ of adversarial errors could obtain rate no larger ... more >>>

TR09-054 | 7th June 2009
Emanuele Viola, Emanuele Viola

#### Cell-Probe Lower Bounds for Prefix Sums

We prove that to store n bits x so that each
prefix-sum query Sum(i) := sum_{k < i} x_k can be answered
by non-adaptively probing q cells of log n bits, one needs
memory > n + n/log^{O(q)} n.

Our bound matches a recent upper bound of n +
n/log^{Omega(q)} ... more >>>

TR17-066 | 20th April 2017
Josh Alman, Joshua Wang, Huacheng Yu

#### Cell-Probe Lower Bounds from Online Communication Complexity

Revisions: 1

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players Bob his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result it presents Bob with the next piece. ... more >>>

TR12-153 | 9th November 2012
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

#### Certifying Equality With Limited Interaction

Revisions: 1

The \textsc{equality} problem is usually one's first encounter with
communication complexity and is one of the most fundamental problems in the
field. Although its deterministic and randomized communication complexity
were settled decades ago, we find several new things to say about the
problem by focusing on two subtle aspects. The ... more >>>

TR12-102 | 16th August 2012
Swastik Kopparty, Srikanth Srinivasan

#### Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications

In this paper, we introduce and develop the method of certifying polynomials for proving $\mathrm{AC}^0[\oplus]$ circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by $\mathrm{AC}^0[\oplus]$ circuits of size $n^{1+o(1)}$. This implies a separation between the power of $\mathrm{AC}^0[\oplus]$ circuits of near-linear size and ... more >>>

TR03-030 | 27th February 2003
Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich

#### Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques

Abstract. It is known that random k-SAT formulas with at least
(2^k*ln2)*n random clauses are unsatisfiable with high probability. This
result is simply obtained by bounding the expected number of satisfy-
ing assignments of a random k-SAT instance by an expression tending
to 0 when n, the number of variables ... more >>>

TR13-119 | 2nd September 2013
Emanuele Viola

#### Challenges in computational lower bounds

We draw two incomplete, biased maps of challenges in
computational complexity lower bounds. Our aim is to put
these challenges in perspective, and to present some
connections which do not seem widely known.

more >>>

TR06-040 | 6th March 2006
Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu

#### Channel assignment in wireless networks and classification of minimum graph homomorphism

We study the problem of assigning different communication channels to
acces points in a wireless Local Area Network. Each access point will
be assigned a specific radio frequency channel. Since channels with
similar frequencies interfere, it is desirable to assign far apart
channels (frequencies) to nearby access points. Our goal ... more >>>

TR19-081 | 31st May 2019
Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak

#### Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation

Revisions: 1

Consider a PPT two-party protocol ?=(A,B) in which the parties get no private inputs and obtain outputs O^A,O^B?{0,1}, and let V^A and V^B denote the parties’ individual views. Protocol ? has ?-agreement if Pr[O^A=O^B]=1/2+?. The leakage of ? is the amount of information a party obtains about the event {O^A=O^B}; ... more >>>

TR16-076 | 27th April 2016
Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma

#### Characterization and Lower Bounds for Branching Program Size using Projective Dimension

Revisions: 2

We study projective dimension, a graph parameter (denoted by $pd(G)$ for a graph $G$), introduced by (Pudlak, Rodl 1992), who showed that proving lower bounds for $pd(G_f)$ for bipartite graphs $G_f$ associated with a Boolean function $f$ imply size lower bounds for branching programs computing $f$. Despite several attempts (Pudlak, ... more >>>

TR09-082 | 20th September 2009
T.C. Vijayaraghavan

#### Characterization of ModL using Prime Modulus.

The complexity class ModL was defined by Arvind and Vijayaraghavan in [AV04] (more precisely in Definition 1.4.1, Vij08],[Definition 3.1, AV]). In this paper, under the assumption that NL =UL, we show that for every language $L\in ModL$ there exists a function $f\in \sharpL$ and a function $g\in FL$ such that ... more >>>

TR18-121 | 20th June 2018
Justin Holmgren, Lisa Yang

#### Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem

Non-signaling games are an important object of study in the theory of computation, for their role both in quantum information and in (classical) cryptography. In this work, we study the behavior of these games under parallel repetition.

We show that, unlike the situation both for classical games and for two-player ... more >>>

TR15-134 | 19th August 2015
Fu Li, Iddo Tzameret, Zhengyu Wang

#### Characterizing Propositional Proofs as Non-Commutative Formulas

Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the ... more >>>

TR11-141 | 2nd November 2011

#### Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

Revisions: 3

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there ... more >>>

TR98-057 | 10th September 1998
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

#### Characterizing Small Depth and Small Space Classes by Operators of Higher Types

Motivated by the question of how to define an analog of interactive
proofs in the setting of logarithmic time- and space-bounded
computation, we study complexity classes defined in terms of
operators quantifying over oracles. We obtain new
characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ... more >>>

TR09-081 | 27th August 2009

#### Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes

In this paper we investigate the following two questions:

Q1: Do there exist optimal proof systems for a given language L?
Q2: Do there exist complete problems for a given promise class C?

For concrete languages L (such as TAUT or SAT and concrete promise classes C (such as NP ... more >>>

TR09-009 | 18th December 2008
T.C. Vijayaraghavan

#### Checking Equality of Matroid Linear Representations and the Cycle Matching Problem

Revisions: 2

Given linear representations M_1 and M_2 of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid. We show that when F=Z_2, ECLR{Z_2} is complete for $\parityL$. Let M_1,M_2\in Q ^{m\times n} be two matroid linear representations given ... more >>>

TR98-062 | 28th October 1998
Oded Goldreich, Dana Ron, Madhu Sudan

#### Chinese Remaindering with Errors

The Chinese Remainder Theorem states that a positive
integer m is uniquely specified by its remainder modulo
k relatively prime integers p_1,...,p_k, provided
m < \prod_{i=1}^k p_i. Thus the residues of m modulo
relatively prime integers p_1 < p_2 < ... < p_n
form a redundant representation of m if ... more >>>

TR18-004 | 3rd January 2018
Aayush Ojha, Raghunath Tewari

#### Circuit Complexity of Bounded Planar Cutwidth Graph Matching

Recently, perfect matching in bounded planar cutwidth bipartite graphs
$BGGM$ was shown to be in ACC$^0$ by Hansen et al.. They also conjectured that
the problem is in AC$^0$.
In this paper, we disprove their conjecture by showing that the problem is
not in AC$^0[p^{\alpha}]$ for every prime $p$. ... more >>>

TR98-056 | 31st August 1998
Anna Bernasconi, Igor E. Shparlinski

#### Circuit Complexity of Testing Square-Free Numbers

In this paper we extend the area of applications of
the Abstract Harmonic Analysis to the field of Boolean function complexity.
In particular, we extend the class of functions to which
a spectral technique developed in a series of works of the first author
can be applied.
This extension ... more >>>

TR14-052 | 14th April 2014
Joshua Grochow, Toniann Pitassi

#### Circuit complexity, proof complexity, and polynomial identity testing

We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>>

TR18-192 | 12th November 2018
Alexander Golovnev, Alexander Kulikov

#### Circuit Depth Reductions

Revisions: 2

The best known circuit lower bounds against unrestricted circuits remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than $5n$. In this work, we suggest a first non-gate-elimination approach for ... more >>>

TR04-004 | 13th January 2004
Ramamohan Paturi, Pavel Pudlak

#### Circuit lower bounds and linear codes

In 1977 Valiant proposed a graph theoretical method for proving lower
bounds on algebraic circuits with gates computing linear functions.
He used this method to reduce the problem of proving
lower bounds on circuits with linear gates to to proving lower bounds
on the rigidity of a matrix, a ... more >>>

TR13-037 | 15th March 2013
Alexander Knop

#### Circuit Lower Bounds for Heuristic MA

Revisions: 2

Santhanam (2007) proved that MA/1 does not have circuits of size $n^k$. We translate his result to the heuristic setting by proving that there is a constant $a$ such that for any $k$, there is a language in HeurMA that cannot be solved by circuits of size $n^k$ on more ... more >>>

TR19-022 | 23rd February 2019
Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

#### Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $\theta$, for a given parameter $\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>>

TR07-005 | 17th January 2007
Rahul Santhanam

#### Circuit Lower Bounds for Merlin-Arthur Classes

We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For ... more >>>

TR17-188 | 22nd December 2017
Cody Murray, Ryan Williams

#### Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP

We prove that if every problem in $NP$ has $n^k$-size circuits for a fixed constant $k$, then for every $NP$-verifier and every yes-instance $x$ of length $n$ for that verifier, the verifier's search space has an $n^{O(k^3)}$-size witness circuit: a witness for $x$ that can be encoded with a circuit ... more >>>

TR13-077 | 14th May 2013
Ján Pich

#### Circuit Lower Bounds in Bounded Arithmetics

We prove that $T_{NC^1}$, the true universal first-order theory in the language containing names for all uniform $NC^1$ algorithms, cannot prove that for sufficiently large $n$, SAT is not computable by circuits of size $n^{2kc}$ where $k\geq 1, c\geq 4$ unless each function $f\in SIZE(n^k)$ can be approximated by formulas ... more >>>

TR09-122 | 23rd November 2009
Vikraman Arvind, Srikanth Srinivasan

#### Circuit Lower Bounds, Help Functions, and the Remote Point Problem

We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced by Alon, Panigrahy, and Yekhanin (RANDOM '09)). More precisely, proving ... more >>>

TR99-045 | 16th November 1999
Valentine Kabanets, Jin-Yi Cai

#### Circuit Minimization Problem

We study the complexity of the circuit minimization problem:
given the truth table of a Boolean function f and a parameter s, decide
whether f can be realized by a Boolean circuit of size at most s. We argue
why this problem is unlikely to be in P (or ... more >>>

TR16-022 | 22nd February 2016
Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki

#### Circuit size lower bounds and #SAT upper bounds through a general framework

Revisions: 2

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the ... more >>>

TR02-066 | 24th October 2002
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay

#### Circuits on Cylinders

We consider the computational power of constant width polynomial
size cylindrical circuits and nondeterministic branching programs.
We show that every function computed by a Pi2 o MOD o AC0 circuit
can also be computed by a constant width polynomial size cylindrical
nondeterministic branching program (or cylindrical circuit) and
that ... more >>>

TR14-020 | 18th February 2014
Pavel Hrubes, Anup Rao

#### Circuits with Medium Fan-In

Revisions: 1

We consider boolean circuits in which every gate may compute an arbitrary boolean function of $k$ other gates, for a parameter $k$. We give an explicit function $f:\bits^n \rightarrow \bits$ that requires at least $\Omega(\log^2 n)$ non-input gates when $k = 2n/3$. When the circuit is restricted to being depth ... more >>>

TR12-145 | 31st October 2012
Cenny Wenner

#### Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four

Håstad established that any predicate $P \subseteq \{0,1\}^m$ containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was addressed by O'Donnell, Wu, and Huang ... more >>>

TR12-023 | 19th March 2012
Sophie Laplante, Virginie Lerays, Jérémie Roland

#### Classical and quantum partition bound and detector inefficiency

In communication complexity, two players each have an input and they wish to compute some function of the joint inputs. This has been the object of much study and a wide variety of lower bound methods have been introduced to address the problem of showing lower bounds on communication. Recently, ... more >>>

TR14-136 | 17th October 2014
Viliam Geffert, Abuzer Yakaryilmaz

#### Classical Automata on Promise Problems

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by ... more >>>

TR07-058 | 9th June 2007
Dmitry Gavinsky

#### Classical Interaction Cannot Replace a Quantum Message

Revisions: 1

We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (two-way) model.

more >>>

TR02-062 | 19th November 2002
Andrew Chi-Chih Yao

#### Classical Physics and the Church-Turing Thesis

Would physical laws permit the construction of computing machines
that are capable of solving some problems much faster than the
standard computational model? Recent evidence suggests that this
might be the case in the quantum world. But the question is of
great interest even in the realm of classical physics. ... more >>>

TR05-016 | 13th January 2005
Tomas Feder, Daniel Ford

#### Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection

Matroid intersection has a known polynomial time algorithm using an
oracle. We generalize this result to delta-matroids that do not have
equality as a restriction, and give a polynomial time algorithm for
delta-matroid intersection on delta-matroids without equality using an
oracle. We note that when equality is present, delta-matroid intersection
more >>>

TR01-082 | 24th September 2001
Tsuyoshi Morioka

#### Classification of Search Problems and Their Definability in Bounded Arithmetic

We present a new framework for the study of search problems and their
definability in bounded arithmetic. We identify two notions of
complexity of search problems: verification complexity and
computational complexity. Notions of exact solvability and exact
reducibility are developed, and exact $\Sigma^b_i$-definability of
search problems in bounded arithmetic ... more >>>

TR05-102 | 13th September 2005
Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

#### Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms

We give a deterministic algorithm for testing satisfiability of formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [Dantsin and Wolpert, SAT 2005]. In comparison with the randomized algorithm in ... more >>>

TR12-039 | 17th April 2012
Stasys Jukna

#### Clique Problem, Cutting Plane Proofs, and Communication Complexity

Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, here we consider the following communication game on a given graph G, known to both players. Let K be the maximal number of vertices in a complete bipartite subgraph of G (which is not ... more >>>

TR08-092 | 26th August 2008
Scott Aaronson, John Watrous

#### Closed Timelike Curves Make Quantum and Classical Computing Equivalent

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the ... more >>>

TR19-037 | 5th March 2019
Chi-Ning Chou, Mrinal Kumar, Noam Solomon

#### Closure of VP under taking factors: a short and simple proof

Revisions: 1

In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree $d$ polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can ... more >>>

TR95-035 | 30th June 1995
Richard Beigel

#### Closure Properties of GapP and #P

We classify the univariate functions that are relativizable
closure properties of GapP, solving a problem posed by Hertrampf,
Vollmer, and Wagner (Structures '95). We also give a simple proof of
their classification of univariate functions that are relativizable
closure properties of #P.

more >>>

TR06-160 | 17th December 2006
Tomas Feder, Phokion G. Kolaitis

#### Closures and dichotomies for quantified constraints

Quantified constraint satisfaction is the generalization of
constraint satisfaction that allows for both universal and existential
of just existential quantifiers.
We study quantified constraint satisfaction problems ${\rm CSP}(Q,S)$, where $Q$ denotes
a pattern of quantifier alternation ending in exists or the set of all possible
more >>>

TR99-035 | 6th July 1999
Leonard Schulman

#### Clustering for Edge-Cost Minimization

We address the problem of partitioning a set of $n$ points into
clusters, so as to minimize the sum, over all intracluster pairs of
points, of the cost associated with each pair. We obtain a randomized
approximation algorithm for this problem, for the cost functions
$\ell_2^2,\ell_1$ and $\ell_2$, as ... more >>>

TR13-031 | 22nd February 2013
Irit Dinur, Elazar Goldenberg

#### Clustering in the Boolean Hypercube in a List Decoding Regime

Revisions: 2

We consider the following clustering with outliers problem: Given a set of points $X \subset \{-1,1\}^n$, such that there is some point $z \in \{-1,1\}^n$ for which at least $\delta$ of the points are $\epsilon$-correlated with $z$, find $z$. We call such a point $z$ a $(\delta,\epsilon)$-center of X.

In ... more >>>

TR08-060 | 10th April 2008

#### Coarse Differentiation and Multi-flows in Planar Graphs

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound by Chakrabarti.et.al for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair.

This also improves the largest known gap for planar graphs ... more >>>

TR10-077 | 26th April 2010

#### Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate

In this paper, we consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently ... more >>>

TR15-106 | 22nd June 2015
Itay Berman, Iftach Haitner, Aris Tentes

#### Coin Flipping of Any Constant Bias Implies One-Way Functions

Revisions: 1

We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., $.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias $\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike ... more >>>

TR19-087 | 10th June 2019
Rohit Agrawal

In this note we compare two measures of the complexity of a class $\mathcal F$ of Boolean functions studied in (unconditional) pseudorandomness: $\mathcal F$'s ability to distinguish between biased and uniform coins (the coin problem), and the norms of the different levels of the Fourier expansion of functions in $\mathcal ... more >>> TR17-160 | 29th October 2017 Eli Ben-Sasson, Eden Saig #### Collaborative Discovery: A study of Guru-follower dynamics Revisions: 1 Gurus are individuals who claim to possess mental powers of insight and prediction that far surpass those of the average person; they compete over followers, offering them insight in return for continued devotion. Followers wish to harness a (true) Guru’s predictive power but (i) have limited attention span and (ii) ... more >>> TR13-131 | 17th September 2013 Nikhil Balaji, Samir Datta #### Collapsing Exact Arithmetic Hierarchies Revisions: 1 We provide a uniform framework for proving the collapse of the hierarchy,$NC^1(\mathcal{C})$for an exact arithmetic class$\mathcal{C}$of polynomial degree. These hierarchies collapses all the way down to the third level of the${AC}^0$-hierarchy,${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes $\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.$ more >>> TR16-178 | 11th November 2016 Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price #### Collision-based Testers are Optimal for Uniformity and Closeness Comments: 1 We study the fundamental problems of (i) uniformity testing of a discrete distribution, and (ii) closeness testing between two discrete distributions with bounded$\ell_2$-norm. These problems have been extensively studied in distribution testing and sample-optimal estimators are known for them~\cite{Paninski:08, CDVV14, VV14, DKN:15}. In this work, we show ... more >>> TR96-042 | 26th July 1996 Oded Goldreich, Shai Halevi #### Collision-Free Hashing from Lattice Problems Recently Ajtai described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same construction can also be used to obtain collision-free hashing. more >>> TR94-009 | 12th December 1994 Noga Alon, Raphael Yuster, Uri Zwick #### Color-coding We describe a novel randomized method, the method of {\em color-coding\/} for finding simple paths and cycles of a specified length$k$, and other small subgraphs, within a given graph$G=(V,E)$. The randomized algorithms obtained using this method can be derandomized using families of {\em perfect hash functions\/}. ... more >>> TR09-093 | 8th October 2009 Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda #### Colored Hypergraph Isomorphism is Fixed Parameter Tractable Revisions: 1 We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time$b!2^{O(b)}N^{O(1)}$, where the parameter$b$is the maximum size of the color classes of the given hypergraphs and$N$is the input size. We also describe fpt algorithms for certain permutation group problems that ... more >>> TR04-070 | 22nd June 2004 Leonid Gurvits #### Combinatorial and algorithmic aspects of hyperbolic polynomials Let$p(x_1,...,x_n) =\sum_{ (r_1,...,r_n) \in I_{n,n} } a_{(r_1,...,r_n) } \prod_{1 \leq i \leq n} x_{i}^{r_{i}}$be homogeneous polynomial of degree$n$in$n$real variables with integer nonnegative coefficients. The support of such polynomial$p(x_1,...,x_n)$is defined as$supp(p) = \{(r_1,...,r_n) \in I_{n,n} : a_{(r_1,...,r_n)} \neq 0 ... more >>>

TR07-115 | 19th November 2007
Or Meir

#### Combinatorial Construction of Locally Testable Codes

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by ... more >>>

TR10-184 | 19th November 2010
Manjish Pal

#### Combinatorial Geometry of Graph Partitioning - I

The {\sc $c$-Balanced Separator} problem is a graph-partitioning problem in which given a graph $G$, one aims to find a cut of minimum size such that both the sides of the cut have at least $cn$ vertices. In this paper, we present new directions of progress in the {\sc $c$-Balanced ... more >>>

TR00-026 | 11th April 2000
Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin

#### Combinatorial Interpretation of Kolmogorov Complexity

The very first Kolmogorov's paper on algorithmic
information theory was entitled Three approaches to the
definition of the quantity of information'. These three
approaches were called combinatorial, probabilistic and
algorithmic. Trying to establish formal connections
between combinatorial and algorithmic approaches, we
prove that any ... more >>>

TR12-017 | 1st March 2012
Venkatesan Guruswami, Srivatsan Narayanan

#### Combinatorial limitations of a strong form of list decoding

Revisions: 1

We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of $O(1/\gamma)$) and lower bound (of $\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to radius $p$ with rate $\gamma$ away from capacity, i.e., $1-h(p)-\gamma$ (here $p\in (0,1/2)$ ... more >>>

TR15-007 | 8th January 2015

#### Combinatorial Optimization Algorithms via Polymorphisms

An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture of [BKJ00]. Roughly speaking, the characterization asserts that a CSP $\Lambda$ is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to ... more >>>

TR11-104 | 3rd August 2011
Or Meir

#### Combinatorial PCPs with efficient verifiers

Revisions: 3

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than ... more >>>

TR13-134 | 25th September 2013
Or Meir

#### Combinatorial PCPs with Short Proofs

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the ... more >>>

TR97-056 | 1st December 1997
Oded Goldreich

#### Combinatorial Property Testing (a survey).

We consider the question of determining whether
a given object has a predetermined property or is far'' from any
object having the property.
Specifically, objects are modeled by functions,
and distance between functions is measured as the fraction
of the domain on which the functions differ.
We ... more >>>

TR98-041 | 27th July 1998
Stasys Jukna

#### Combinatorics of Monotone Computations

We consider a general model of monotone circuits, which
we call d-local. In these circuits we allow as gates:
(i) arbitrary monotone Boolean functions whose minterms or
maxterms (or both) have length at most <i>d</i>, and
(ii) arbitrary real-valued non-decreasing functions on ... more >>>

TR18-059 | 6th April 2018
Joshua Brakensiek, Venkatesan Guruswami

#### Combining LPs and Ring Equations via Structured Polymorphisms

Revisions: 1

Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, ... more >>>

TR09-003 | 6th January 2009
Alex Hertel, Alasdair Urquhart

#### Comments on ECCC Report TR06-133: The Resolution Width Problem is EXPTIME-Complete

We discovered a serious error in one of our previous submissions to ECCC and wish to make sure that this mistake is publicly known.

The main argument of the report TR06-133 is in error. The paper claims to prove the result of the title by reduction from the (Exists,k)-pebble game, ... more >>>

TR13-056 | 30th March 2013
Gábor Braun, Sebastian Pokutta

#### Common information and unique disjointness

Revisions: 5

We provide a new framework for establishing strong lower bounds on the nonnega- tive rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance ... more >>>

TR15-156 | 21st September 2015
Tim Roughgarden

#### Communication Complexity (for Algorithm Designers)

This document collects the lecture notes from my course Communication Complexity (for Algorithm Designers),'' taught at
Stanford in the winter quarter of 2015. The two primary goals of the course are:

1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). ... more >>>

TR01-062 | 9th September 2001
Moni Naor, Kobbi Nissim

#### Communication Complexity and Secure Function Evaluation

A secure function evaluation protocol allows two parties to jointly compute a function $f(x,y)$ of their inputs in a manner not leaking more information than necessary. A major result in this field is: any function $f$ that can be computed using polynomial resources can be computed securely using polynomial resources'' ... more >>>

TR17-061 | 3rd April 2017
Anat Ganor, Karthik C. S.

#### Communication Complexity of Correlated Equilibrium in Two-Player Games

We show a communication complexity lower bound for finding a correlated equilibrium of a two-player game. More precisely, we define a two-player $N \times N$ game called the 2-cycle game and show that the randomized communication complexity of finding a 1/poly($N$)-approximate correlated equilibrium of the 2-cycle game is $\Omega(N)$. For ... more >>>

TR15-087 | 30th May 2015

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of ''permutation-invariant'' functions. A partial function $f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$ is permutation-invariant if for every bijection $\pi:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, it is the case that $f(\mathbf{x}, \mathbf{y}) ... more >>> TR14-055 | 17th April 2014 Mika Göös, Thomas Watson #### Communication Complexity of Set-Disjointness for All Probabilities Revisions: 1 We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions ... more >>> TR16-170 | 3rd November 2016 Thomas Watson #### Communication Complexity of Statistical Distance Revisions: 1 We prove nearly matching upper and lower bounds on the randomized communication complexity of the following problem: Alice and Bob are each given a probability distribution over$n$elements, and they wish to estimate within$\pm\epsilon$the statistical (total variation) distance between their distributions. For some range of parameters, there ... more >>> TR07-072 | 2nd July 2007 Alexander A. Sherstov #### Communication Complexity under Product and Nonproduct Distributions We solve an open problem of Kushilevitz and Nisan (1997) in communication complexity. Let$R_{eps}(f)$and$D^{mu}_{eps}(f)$denote the randomized and$mu$-distributional communication complexities of f, respectively ($eps$a small constant). Yao's well-known Minimax Principle states that R_{eps}(f) = max_{mu} { D^{mu}_{eps}(f) }. Kushilevitz and Nisan (1997) ask whether ... more >>> TR16-148 | 23rd September 2016 Thomas Watson #### Communication Complexity with Small Advantage We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least$\epsilon$greater than one over the codomain size of the function. Previously, Braverman and Moitra (STOC 2013) showed ... more >>> TR13-084 | 8th June 2013 Shachar Lovett #### Communication is bounded by root of rank Revisions: 1 We prove that any total boolean function of rank$r$can be computed by a deterministic communication protocol of complexity$O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank$r$has chromatic number at most$2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on ... more >>> TR13-005 | 2nd January 2013 Alexander A. Sherstov #### Communication Lower Bounds Using Directional Derivatives We prove that the set disjointness problem has randomized communication complexity$\Omega(\sqrt{n}/2^{k}k)$in the number-on-the-forehead model with$k$parties, a quadratic improvement on the previous bound$\Omega(\sqrt{n}/2^{k})^{1/2}$. Our result remains valid for quantum protocols, where it is essentially tight. Proving it was an open problem since 1997, ... more >>> TR08-057 | 14th May 2008 Alexander A. Sherstov #### Communication Lower Bounds Using Dual Polynomials Representations of Boolean functions by real polynomials play an important role in complexity theory. Typically, one is interested in the least degree of a polynomial p(x_1,...,x_n) that approximates or sign-represents a given Boolean function f(x_1,...,x_n). This article surveys a new and growing body of work in communication complexity that centers ... more >>> TR15-064 | 19th April 2015 Ilan Komargodski, Pravesh Kothari, Madhu Sudan #### Communication with Contextual Uncertainty Revisions: 1 We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information$x$and Bob gets$y$, where$(x,y)$is drawn from a known distribution, and Bob ... more >>> TR14-153 | 14th November 2014 Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan #### Communication with Imperfectly Shared Randomness Revisions: 2 The communication complexity of many fundamental problems reduces greatly when the communicating parties share randomness that is independent of the inputs to the communication task. Natural communication processes (say between humans) however often involve large amounts of shared correlations among the communicating players, but rarely allow for perfect sharing of ... more >>> TR18-150 | 27th August 2018 Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan #### Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples$X_1,X_2,\dots$and$Y_1,Y_2,\dots$with the pairs$(X_1,Y_1)$,$(X_2, Y_2)$,$\dots$being drawn independently from some known probability distribution$\mu$. They ... more >>> TR15-035 | 22nd February 2015 Sunil K S, Balagopal Komarath, Jayalal Sarma #### Comparator Circuits over Finite Bounded Posets Revisions: 1 Comparator circuit model was originally introduced by Mayr and Subramanian (1992) to capture problems which are not known to be P-complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem We know ... more >>> TR98-063 | 4th November 1998 Oded Goldreich, Salil Vadhan #### Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK We consider the following (promise) problem, denoted ED (for Entropy Difference): The input is a pairs of circuits, and YES instances (resp., NO instances) are such pairs in which the first (resp., second) circuit generates a distribution with noticeably higher entropy. On one hand we show that any language ... more >>> TR06-039 | 28th February 2006 John Hitchcock, A. Pavan #### Comparing Reductions to NP-Complete Sets Under the assumption that NP does not have p-measure 0, we investigate reductions to NP-complete sets and prove the following: - Adaptive reductions are more powerful than nonadaptive reductions: there is a problem that is Turing-complete for NP but not truth-table-complete. - Strong nondeterministic reductions are more powerful ... more >>> TR14-143 | 3rd November 2014 Ronald de Haan, Stefan Szeider #### Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These parameterized problems are based on problems whose complexity lies at the second level of the Polynomial Hierarchy or higher. The list will be updated as ... more >>> TR11-122 | 14th September 2011 Gillat Kol, Ran Raz #### Competing Provers Protocols for Circuit Evaluation Let$C$be a (fan-in$2$) Boolean circuit of size$s$and depth$d$, and let$x$be an input for$C$. Assume that a verifier that knows$C$but doesn't know$x$can access the low degree extension of$x$at one random point. Two competing provers try to ... more >>> TR17-136 | 10th September 2017 Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo #### Complete Classi fication of Generalized Santha-Vazirani Sources Let$\mathcal{F}$be a finite alphabet and$\mathcal{D}$be a finite set of distributions over$\mathcal{F}$. A Generalized Santha-Vazirani (GSV) source of type$(\mathcal{F}, \mathcal{D})$, introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence$(F_1, \dots, F_n)$in$\mathcal{F}^n$, where$F_i$is a sample from ... more >>> TR16-171 | 3rd November 2016 Daniel Minahan, Ilya Volkovich #### Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas In this paper we study the identity testing problem of \emph{arithmetic read-once formulas} (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the operations are$\set{+,\times}$and such that every input variable labels at most one leaf. We obtain ... more >>> TR06-036 | 7th February 2006 Tobias Riege, Jörg Rothe #### Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems Revisions: 1 This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with ... more >>> TR03-060 | 7th September 2003 Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen #### Completeness in Two-Party Secure Computation - A Computational View A Secure Function Evaluation (SFE) of a two-variable function f(.,.) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns more than is necessary". A rich body of work deals with the study of completeness for secure ... more >>> TR97-057 | 3rd November 1997 Petr Savicky #### Complexity and Probability of some Boolean Formulas For any Boolean function$f$let$L(f)$be its formula size complexity in the basis$\{\land,\oplus,1\}$. For every$n$and every$k\le n/2$, we describe a probabilistic distribution on formulas in the basis$\{\land,\oplus,1\}$in some given set of$n$variables and of the ... more >>> TR16-039 | 15th March 2016 Adam Bouland, Laura Mancinska, Xue Zhang #### Complexity Classification of Two-Qubit Commuting Hamiltonians We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian$H$which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one ... more >>> TR11-093 | 8th June 2011 Pinyan Lu #### Complexity Dichotomies of Counting Problems In order to study the complexity of counting problems, several interesting frameworks have been proposed, such as Constraint Satisfaction Problems (#CSP) and Graph Homomorphisms. Recently, we proposed and explored a novel alternative framework, called Holant Problems. It is a refinement with a more explicit role for constraint functions. Both graph ... more >>> TR97-046 | 3rd October 1997 Alexander Barg #### Complexity Issues in Coding Theory This is a research-expository paper. It deals with complexity issues in the theory of linear block codes. The main emphasis is on the theoretical performance limits of the best known codes. Therefore, the main subject of the paper are families of asymptotically good codes, i.e., codes whose rate and relative ... more >>> TR11-138 | 24th October 2011 Guy Moshkovitz #### Complexity Lower Bounds through Balanced Graph Properties In this paper we present a combinatorial approach for proving complexity lower bounds. We mainly focus on the following instantiation of it. Consider a pair of properties of$m$-edge regular hypergraphs. Suppose they are indistinguishable'' with respect to hypergraphs with$m-t$edges, in the sense that every such hypergraph has ... more >>> TR13-125 | 11th September 2013 Venkatesan Guruswami, Euiwoong Lee #### Complexity of approximating CSP with Balance / Hard Constraints We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>> TR16-031 | 7th March 2016 Titus Dose #### Complexity of Constraint Satisfaction Problems over Finite Substsets of Natural Numbers Revisions: 5 We study the computational complexity of constraint satisfaction problems that are based on integer expressions and algebraic circuits. On input of a finite set of variables and a finite set of constraints the question is whether the variables can be mapped onto finite subsets of natural numbers (resp., finite intervals ... more >>> TR08-044 | 2nd April 2008 Miki Hermann, Reinhard Pichler #### Complexity of Counting the Optimal Solutions Following the approach of Hemaspaandra and Vollmer, we can define counting complexity classes #.C for any complexity class C of decision problems. In particular, the classes #.Pi_{k}P with k >= 1 corresponding to all levels of the polynomial hierarchy have thus been studied. However, for a large variety of counting ... more >>> TR15-174 | 18th October 2015 Dmitry Itsykson, Alexander Knop, Dmitry Sokolov #### Complexity of distributions and average-case hardness We address a natural question in average-case complexity: does there exist a language$L$such that for all easy distributions$D$the distributional problem$(L, D)$is easy on the average while there exists some more hard distribution$D'$such that$(L, D')$is hard on the average? We consider ... more >>> TR04-035 | 10th April 2004 Scott Contini, Ernie Croot, Igor E. Shparlinski #### Complexity of Inverting the Euler Function We present an algorithm to invert the Euler function$\varphi(m)$. The algorithm, for a given integer$n\ge 1$, in polynomial time on average'', finds theset$\Psi(n)$of all solutions$m$to the equation$\varphi(m) =n$. In fact, in the worst case the set$\Psi(n)$is exponentially large and cannot be ... more >>> TR19-002 | 31st December 2018 Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii #### Complexity of Linear Operators Let$A \in \{0,1\}^{n \times n}$be a matrix with$z$zeroes and$u$ones and$x$be an$n$-dimensional vector of formal variables over a semigroup$(S, \circ)$. How many semigroup operations are required to compute the linear operator$Ax$? As we observe in this paper, this problem contains ... more >>> TR15-018 | 31st January 2015 Eric Allender, Ian Mertz #### Complexity of Regular Functions Revisions: 1 We give complexity bounds for various classes of functions computed by cost register automata. more >>> TR01-103 | 14th December 2001 Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik #### Complexity of semi-algebraic proofs Revisions: 3 It is a known approach to translate propositional formulas into systems of polynomial inequalities and to consider proof systems for the latter ones. The well-studied proof systems of this kind are the Cutting Planes proof system (CP) utilizing linear inequalities and the Lovasz-Schrijver calculi (LS) utilizing quadratic ... more >>> TR02-068 | 10th December 2002 Tobias Riege, Jörg Rothe #### Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem Revisions: 2 We prove that the exact versions of the domatic number problem are complete for the levels of the boolean hierarchy over NP. The domatic number problem, which arises in the area of computer networks, is the problem of partitioning a given graph into a maximum number ... more >>> TR18-039 | 23rd February 2018 Md Lutfar Rahman, Thomas Watson #### Complexity of Unordered CNF Games The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study ... more >>> TR94-013 | 12th December 1994 Pavel Pudlak #### Complexity Theory and Genetics We introduce a population genetics model in which the operators are effectively computable -- computable in polynomial time on Probabilistic Turing Machines. We shall show that in this model a population can encode easily large amount of information from enviroment into genetic code. Then it can process the information as ... more >>> TR18-001 | 2nd January 2018 Tim Roughgarden #### Complexity Theory, Game Theory, and Economics Revisions: 1 This document collects the lecture notes from my mini-course "Complexity Theory, Game Theory, and Economics," taught at the Bellairs Research Institute of McGill University, Holetown, Barbados, February 19-23, 2017, as the 29th McGill Invitational Workshop on Computational Complexity. The goal of this mini-course is twofold: (i) to explain how complexity ... more >>> TR16-200 | 18th December 2016 Scott Aaronson, Lijie Chen #### Complexity-Theoretic Foundations of Quantum Supremacy Experiments Revisions: 1 In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis ... more >>> TR17-014 | 23rd January 2017 Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay #### Composition and Simulation Theorems via Pseudo-random Properties We prove a randomized communication-complexity lower bound for a composed OrderedSearch$\circ$IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>> TR09-042 | 5th May 2009 Irit Dinur, Prahladh Harsha #### Composition of low-error 2-query PCPs using decodable PCPs The main result of this paper is a simple, yet generic, composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored ... more >>> TR11-070 | 1st May 2011 Eli Ben-Sasson, Michael Viderman #### Composition of semi-LTCs by two-wise Tensor Products In this paper we obtain a composition theorem that allows us to construct locally testable codes (LTCs) by repeated two-wise tensor products. This is the First composition theorem showing that repeating the two-wise tensor operation any constant number of times still results in a locally testable code, improving upon previous ... more >>> TR03-065 | 19th June 2003 Wee, Hoeteck #### Compressibility Lower Bounds in Oracle Settings A source is compressible if we can efficiently compute short descriptions of strings in the support and efficiently recover the strings from the descriptions. In this paper, we present a technique for proving lower bounds on compressibility in an oracle setting, which yields the following results: - We ... more >>> TR15-092 | 31st May 2015 Yael Tauman Kalai, Ilan Komargodski #### Compressing Communication in Distributed Protocols Revisions: 2 We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of ... more >>> TR16-081 | 20th May 2016 Alexander A. Sherstov #### Compressing interactive communication under product distributions We study the problem of compressing interactive communication to its information content$I$, defined as the amount of information that the participants learn about each other's inputs. We focus on the case when the participants' inputs are distributed independently and show how to compress the communication to$O(I\log^{2}I)$bits, with ... more >>> TR13-024 | 7th February 2013 Valentine Kabanets, Antonina Kolokolova #### Compression of Boolean Functions We consider the problem of compression for easy'' Boolean functions: given the truth table of an$n$-variate Boolean function$f$computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time$\poly(2^n)$a circuit$C$(no restriction on the type of$C$) computing$f$so ... more >>> TR05-012 | 17th January 2005 Luca Trevisan, Salil Vadhan, David Zuckerman #### Compression of Samplable Sources We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n). 1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1). Our next ... more >>> TR08-031 | 14th January 2008 James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers #### Computability and Complexity in Self-Assembly This paper explores the impact of geometry on computability = and complexity in Winfree's model of nanoscale self-assembly. We work in the = two-dimensional tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our = first main theorem says that there is a roughly quadratic function f ... more >>> TR16-146 | 18th September 2016 Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini #### Computability Theory of Closed Timelike Curves We ask, and answer, the question of what's computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid ... more >>> TR03-081 | 10th October 2003 Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini #### Computation of the Lov\'asz Theta Function for Circulant Graphs The Lov\'asz theta function$\theta(G)$of a graph$G$has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique ... more >>> TR06-137 | 13th November 2006 Prashant Joshi, Eduardo D. Sontag #### Computational aspects of feedback in neural circuits It had previously been shown that generic cortical microcircuit models can perform complex real-time computations on continuous input streams, provided that these computations can be carried out with a rapidly fading memory. We investigate in this article the computational capability of such circuits in the ... more >>> TR11-114 | 8th August 2011 Varun Kanade #### Computational Bottlenecks for Evolvability Valiant (2007) proposed a computational model for evolution and suggested that evolvability be studied in the framework of computational learning theory. Feldman (2008) showed that Valiant’s evolution model is equivalent to the correlational statistical query (CSQ) learning model, which is a restricted setting of the statistical query (SQ) model. Evolvability ... more >>> TR94-007 | 12th December 1994 Oded Goldreich, Rafail Ostrovsky, Erez Petrank #### Computational Complexity and Knowledge Complexity We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in${\cal BPP}^{\cal NP}$. Prior to this work, for languages with greater-than-zero knowledge complexity (and specifically, even for knowledge complexity 1) only trivial computational complexity bounds ... more >>> TR06-159 | 3rd October 2006 Predrag Tosic #### Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata We study the computational complexity of counting the fixed point configurations (FPs), the predecessor configurations and the ancestor configurations in certain classes of graph or network automata viewed as discrete dynamical systems. Early results of this investigation are presented in two recent ECCC reports [39, 40]. In particular, it is ... more >>> TR04-111 | 30th November 2004 Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott #### Computational Complexity of Some Restricted Instances of 3SAT We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times. more >>> TR02-014 | 10th December 2001 Klaus Weihrauch #### Computational Complexity on Computable Metric Spaces Revisions: 1 We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko \cite{Ko91} et al. Although this definition of${\rm TIME}$as the maximum of a generally infinite ... more >>> TR12-009 | 28th November 2011 Prabhu Manyem, Julien Ugon #### Computational Complexity, NP Completeness and Optimization Duality: A Survey We survey research that studies the connection between the computational complexity of optimization problems on the one hand, and the duality gap between the primal and dual optimization problems on the other. To our knowledge, this is the first survey that connects the two very important areas. We further look ... more >>> TR96-067 | 20th December 1996 Oded Goldreich, Bernd Meyer #### Computational Indistinguishability -- Algorithms vs. Circuits. We present a simple proof to the existence of a probability ensemble with tiny support which cannot be distinguished from the uniform ensemble by any recursive computation. Since the support is tiny (i.e, sub-polynomial), this ensemble can be distinguish from the uniform ensemble by a (non-uniform) family ... more >>> TR98-017 | 29th March 1998 Oded Goldreich, Madhu Sudan #### Computational Indistinguishability: A Sample Hierarchy. We consider the existence of pairs of probability ensembles which may be efficiently distinguished given$k$samples but cannot be efficiently distinguished given$k'<k$samples. It is well known that in any such pair of ensembles it cannot be that both are efficiently computable (and that such phenomena ... more >>> TR97-028 | 12th July 1997 Scott E. Decatur, Oded Goldreich, Dana Ron #### Computational Sample Complexity In a variety of PAC learning models, a tradeoff between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrictions, more information sometimes seems to be required. In addition, it has long been known that there are concept classes ... more >>> TR18-071 | 15th April 2018 Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak #### Computational Two-Party Correlation Let$\pi$be an efficient two-party protocol that given security parameter$\kappa$, both parties output single bits$X_\kappa$and$Y_\kappa$, respectively. We are interested in how$(X_\kappa,Y_\kappa)$appears'' to an efficient adversary that only views the transcript$T_\kappa$. We make the following contributions: \begin{itemize} \item We develop new tools to ... more >>> TR15-042 | 30th March 2015 Ilya Volkovich #### Computations beyond Exponentiation Gates and Applications In Arithmetic Circuit Complexity the standard operations are$\{+,\times\}$. Yet, in some scenarios exponentiation gates are considered as well (see e.g. \cite{BshoutyBshouty98,ASSS12,Kayal12,KSS14}). In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power. That is, beyond an exponentiation gate. As ... more >>> TR07-067 | 22nd May 2007 Paul Spirakis, haralampos tsaknakis #### Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time. Revisions: 2 In this paper we propose a methodology for determining approximate Nash equilibria of non-cooperative bimatrix games and, based on that, we provide a polynomial time algorithm that computes$\frac{1}{3} + \frac{1}{p(n)} $-approximate equilibria, where$p(n)$is a polynomial controlled by our algorithm and proportional to its running time. The ... more >>> TR12-126 | 23rd September 2012 Shiva Kintali, Sinziana Munteanu #### Computing Bounded Path Decompositions in Logspace We present a logspace algorithm to compute path decompositions of bounded pathwidth graphs, thus settling its complexity. Prior to our work, the best known upper bound to compute such decompositions was linear time. We also show that deciding if the pathwidth of a graph is at most a given constant ... more >>> TR02-052 | 3rd September 2002 Vince Grolmusz #### Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications Revisions: 1 Elementary symmetric polynomials$S_n^k$are used as a benchmark for the bounded-depth arithmetic circuit model of computation. In this work we prove that$S_n^k$modulo composite numbers$m=p_1p_2$can be computed with much fewer multiplications than over any field, if the coefficients of monomials$x_{i_1}x_{i_2}\cdots x_{i_k}$... more >>> TR15-153 | 21st September 2015 Tim Roughgarden #### Computing Equilibria: A Computational Complexity Perspective Computational complexity is the subfield of computer science that rigorously studies the intrinsic difficulty of computational problems. This survey explains how complexity theory defines “hard problems”; applies these concepts to several equilibrium computation problems; and discusses implications for computation, games, and behavior. We assume minimal prior background in computer science. ... more >>> TR16-158 | 9th October 2016 Alexander Kulikov, Vladimir Podolskii #### Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates We study the following computational problem: for which values of$k$, the majority of$n$bits$\text{MAJ}_n$can be computed with a depth two formula whose each gate computes a majority function of at most$k$bits? The corresponding computational model is denoted by$\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>> TR06-023 | 7th February 2006 Xi Chen, Xiaotie Deng, Shang-Hua Teng #### Computing Nash Equilibria: Approximation and Smoothed Complexity By proving that the problem of computing a$1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in$n$and$1/\epsilon$can compute an$\epsilon$-approximate Nash equilibrium of an$n\times ... more >>>

TR14-106 | 9th August 2014
Craig Gentry

#### Computing on the edge of chaos: Structure and randomness in encrypted computation

This survey, aimed mainly at mathematicians rather than practitioners, covers recent developments in homomorphic encryption (computing on encrypted data) and program obfuscation (generating encrypted but functional programs). Current schemes for encrypted computation all use essentially the same "noisy" approach: they encrypt via a noisy encoding of the message, they decrypt ... more >>>

TR11-094 | 20th June 2011
Shachar Lovett

#### Computing polynomials with few multiplications

A folklore result in arithmetic complexity shows that the number of multiplications required to compute some $n$-variate polynomial of degree $d$ is $\sqrt{{n+d \choose n}}$. We complement this by an almost matching upper bound, showing that any $n$-variate polynomial of degree $d$ over any field can be computed with only ... more >>>

TR16-179 | 15th November 2016
Avishay Tal

#### Computing Requires Larger Formulas than Approximating

A de Morgan formula over Boolean variables $x_1, \ldots, x_n$ is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that ... more >>>

TR96-027 | 20th February 1996
Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

#### Computing Solutions Uniquely Collapses the Polynomial Hierarchy

Is there an NP function that, when given a satisfiable formula
as input, outputs one satisfying assignment uniquely? That is, can a
nondeterministic function cull just one satisfying assignment from a
possibly exponentially large collection of assignments? We show that if
there is such a nondeterministic function, then the polynomial ... more >>>

TR94-025 | 12th December 1994
David P. Dobkin, Dimitrios Gunopulos

#### Computing the Maximum Bichromatic Discrepancy with applications to Computer Graphics and Machine Learning

Computing the maximum bichromatic discrepancy is an interesting
theoretical problem with important applications in computational
learning theory, computational geometry and computer graphics.
In this paper we give algorithms to compute the maximum
bichromatic discrepancy for simple geometric ranges, including
rectangles and halfspaces.
In addition, we give ... more >>>

TR18-020 | 30th January 2018
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

#### Computing the maximum using $(\min, +)$ formulas

We study computation by formulas over $(min, +)$. We consider the computation of $\max\{x_1,\ldots,x_n\}$
over $\mathbb{N}$ as a difference of $(\min, +)$ formulas, and show that size $n + n \log n$ is sufficient and necessary. Our proof also shows that any $(\min, +)$ formula computing the minimum of all ... more >>>

TR14-053 | 15th April 2014
Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman

#### Computing with a full memory: Catalytic space

Revisions: 1

We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state ... more >>>

TR08-054 | 13th May 2008
Venkatesan Guruswami, Atri Rudra

#### Concatenated codes can achieve list-decoding capacity

We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any $0 < \rho < 1/2$ and $\epsilon > 0$, there exist concatenated codes of ... more >>>

TR07-002 | 8th November 2006
Moti Yung, Yunlei Zhao

#### Concurrent Knowledge-Extraction in the Public-Key Model

Knowledge extraction is a fundamental notion, modeling knowledge possession in a computational complexity sense. The notion provides a tool for cryptographic protocol design and analysis, enabling one to argue about the internal state of protocol players. We define and
investigate the relative power of the notion of concurrent knowledge-extraction'' ... more >>>

TR06-095 | 25th July 2006
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

#### Concurrent Non-Malleable Witness Indistinguishability and its Applications

Revisions: 1

One of the central questions in Cryptography today is proving security of the protocols on the Internet'', i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called man-in-the-middle'' attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, ... more >>>

TR05-093 | 24th August 2005
Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

#### Concurrent Zero Knowledge without Complexity Assumptions

We provide <i>unconditional</i> constructions of <i>concurrent</i>
statistical zero-knowledge proofs for a variety of non-trivial
problems (not known to have probabilistic polynomial-time
algorithms). The problems include Graph Isomorphism, Graph
restricted version of Statistical Difference, and approximate
versions of the (<b>coNP</b> forms of the) Shortest Vector ... more >>>

TR01-091 | 27th November 2001
Oded Goldreich

#### Concurrent Zero-Knowledge With Timing, Revisited

Following Dwork, Naor, and Sahai (30th STOC, 1998),
we consider concurrent execution of protocols in a
semi-synchronized network. Specifically, we assume that each party
holds a local clock such that a constant bound on the relative rates
of these clocks is a-priori known, and consider protocols that
employ ... more >>>

TR17-189 | 25th December 2017
Benny Applebaum, Barak Arkis

#### Conditional Disclosure of Secrets and $d$-Uniform Secret Sharing with Constant Information Rate

Revisions: 1

Consider the following secret-sharing problem. Your goal is to distribute a long file $s$ between $n$ servers such that $(d-1)$-subsets cannot recover the file, $(d+1)$-subsets can recover the file, and $d$-subsets should be able to recover $s$ if and only if they appear in some predefined list $L$. How small ... more >>>

TR17-038 | 23rd February 2017
Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan

#### Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations

Revisions: 1

In the \emph{conditional disclosure of secrets} problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold inputs $x$ and $y$ respectively, wish to release a common secret $s$ to Carol (who knows both $x$ and $y$) if only if the input $(x,y)$ satisfies some predefined predicate ... more >>>

TR05-039 | 13th April 2005
Irit Dinur, Elchanan Mossel, Oded Regev

#### Conditional Hardness for Approximate Coloring

We study the approximate-coloring(q,Q) problem: Given a graph G, decide
whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional
hardness for this problem for any constant 3\le q < Q. For q \ge
4, our result is based on Khot's 2-to-1 conjecture [Khot'02].
For q=3, we base our hardness ... more >>>

TR09-125 | 24th November 2009
David Steurer, Nisheeth Vishnoi

#### Connections Between Unique Games and Multicut

In this paper we demonstrate a close connection between UniqueGames and
MultiCut.
%
In MultiCut, one is given a network graph'' and a `demand
graph'' on the same vertex set and the goal is to remove as few
edges from the network graph as ... more >>>

TR19-077 | 30th May 2019
Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajicek

#### Consistency of circuit lower bounds with bounded theories

Proving that there are problems in $P^{NP}$ that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are known for larger complexity classes, existing results only show that the corresponding problems are hard on infinitely many input lengths. For instance, proving almost-everywhere ... more >>>

TR16-197 | 7th December 2016
Igor Carboni Oliveira, Rahul Santhanam

#### Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness

We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness. Let C be any typical class of Boolean circuits, and C[s(n)] denote n-variable C-circuits of size at most s(n). We show:

Learning Speedups: If C[$n^{O(1)}$] admits a randomized weak learning algorithm under the uniform ... more >>>

TR13-085 | 13th June 2013
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

#### Constant rate PCPs for circuit-SAT with sublinear query complexity

The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up ... more >>>

TR03-025 | 14th April 2003
Kristoffer Arnsfelt Hansen

#### Constant width planar computation characterizes ACC0

We obtain a characterization of ACC0 in terms of a natural class of
constant width circuits, namely in terms of constant width polynomial
size planar circuits. This is shown via a characterization of the
class of acyclic digraphs which can be embedded on a cylinder surface
in such a way ... more >>>

TR05-087 | 9th August 2005
Alexander Healy, Emanuele Viola

#### Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

We study the complexity of arithmetic in finite fields of characteristic two, $\F_{2^n}$.
We concentrate on the following two problems:

Iterated Multiplication: Given $\alpha_1, \alpha_2,..., \alpha_t \in \F_{2^n}$, compute $\alpha_1 \cdot \alpha_2 \cdots \alpha_t \in \F_{2^n}$.

Exponentiation: Given $\alpha \in \F_{2^n}$ and a $t$-bit integer $k$, compute $\alpha^k \in \F_{2^n}$.

... more >>>

TR18-133 | 26th July 2018
Emanuele Viola

#### Constant-error pseudorandomness proofs from hardness require majority

Revisions: 1

Research in the 80's and 90's showed how to construct a pseudorandom
generator from a function that is hard to compute on more than $99\%$
of the inputs. A more recent line of works showed however that if
the generator has small error, then the proof of correctness cannot
be ... more >>>

TR15-197 | 7th December 2015
Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

#### Constant-rate coding for multiparty interactive communication is impossible

We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability $\epsilon$. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise.

Our ... more >>>

TR17-095 | 26th May 2017
Ran Gelles, Yael Tauman Kalai

#### Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks

Multiparty interactive coding allows a network of $n$ parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC '94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of $O(\log(\Delta+1))$ for networks whose topology has a maximal degree ... more >>>

TR05-048 | 11th April 2005
Moti Yung, Yunlei Zhao

#### Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model

Revisions: 3

We present constant-round concurrently secure (sound) resettable
zero-knowledge (rZK-CS) arguments in the bare public-key (BPK)
model. Our constructions deal with general NP ZK-arguments as well
as with highly efficient ZK-arguments for number-theoretic
languages, most relevant to identification scenarios. These are the
first constant-round protocols of ... more >>>

TR18-069 | 14th April 2018
Oded Goldreich, Guy Rothblum

#### Constant-round interactive proof systems for AC0[2] and NC1

Revisions: 1

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.
Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than
the work of Reingold, Rothblum, and Rothblum (STOC, 2016).
Our proof system for AC0[2] supports a more ... more >>>

TR16-061 | 17th April 2016
Omer Reingold, Ron Rothblum, Guy Rothblum

#### Constant-Round Interactive Proofs for Delegating Computation

Revisions: 1

The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an ... more >>>

TR11-003 | 10th January 2011
Yehuda Lindell

#### Constant-Round Zero-Knowledge Proofs of Knowledge

Revisions: 1

In this note, we show the existence of \emph{constant-round} computational zero-knowledge \emph{proofs of knowledge} for all $\cal NP$. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge \emph{arguments} of knowledge was proven by Feige and Shamir (CRYPTO ... more >>>

TR05-005 | 20th December 2004
Tomas Feder

#### Constraint Satisfaction on Finite Groups with Near Subgroups

Constraint satisfaction on finite groups, with subgroups and their cosets
described by generators, has a polynomial time algorithm. For any given
group, a single additional constraint type that is not a coset of a near
subgroup makes the problem NP-complete. We consider constraint satisfaction on
groups with subgroups, near subgroups, ... more >>>

TR08-008 | 8th February 2008

#### Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

Revisions: 1

We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>>

TR07-055 | 22nd May 2007
Oliver Kullmann

#### Constraint satisfaction problems in clausal form: Autarkies and minimal unsatisfiability

Revisions: 1

We consider the next step from boolean conjunctive normal forms to
arbitrary constraint satisfaction problems (with arbitrary constraints), namely "generalised clause-sets" (or "sets of no-goods"), which allow negative literals "v <> e" for variables v and values e --- this level of generality appears to be the right level for ... more >>>

TR06-021 | 10th February 2006
Tomas Feder

#### Constraint satisfaction: a personal perspective

Attempts at classifying computational problems as polynomial time
solvable, NP-complete, or belonging to a higher level in the polynomial
hierarchy, face the difficulty of undecidability. These classes, including
NP, admit a logic formulation. By suitably restricting the formulation, one
finds the logic class MMSNP, or monotone monadic strict NP without
more >>>

TR96-064 | 11th December 1996
Sanjeev Khanna, Madhu Sudan, Luca Trevisan

#### Constraint satisfaction: The approximability of minimization problems.

This paper continues the work initiated by Creignou [Cre95] and
Khanna, Sudan and Williamson [KSW96] who classify maximization
problems derived from boolean constraint satisfaction. Here we
study the approximability of {\em minimization} problems derived
thence. A problem in this framework is characterized by a
collection F ... more >>>

TR12-114 | 15th July 2012
Mikhail Anokhin

#### Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption

Revisions: 5

We construct a provably pseudo-free family of finite computational groups under the general integer factoring intractability assumption. Moreover, this family has exponential size. But each element of a group in our pseudo-free family is represented by many bit strings.

more >>>

TR14-140 | 31st October 2014
Hong Van Le

#### Constructing elusive functions with help of evaluation mappings

We develop a method to construct elusive functions using techniques of commutative algebra and algebraic geometry. The key notions of this method are elusive subsets and evaluation mappings. We also develop the effective elimination theory combined with algebraic number field theory in order to construct concrete points outside the image ... more >>>

TR18-212 | 26th December 2018

#### Constructing Faithful Homomorphisms over Fields of Finite Characteristic

We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena (Information and Computing, 2013), and exploited by them, and Agrawal, Saha, Saptharishi and Saxena (Journal of Computing, 2016) to design algebraic independence based identity tests ... more >>>

TR13-129 | 17th September 2013
Adam Klivans, Pravesh Kothari, Igor Oliveira

#### Constructing Hard Functions from Learning Algorithms

Revisions: 1

Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class $\mathcal{C} \subseteq P/poly$ of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then $EXP^{NP} \not \subseteq \mathcal{C}$ (the class $EXP^{NP}$ was subsequently improved to $P$ by Hitchcock and ... more >>>

TR15-019 | 3rd February 2015
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

#### Constructing Near Spanning Trees with Few Local Inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let $G$ be a connected bounded-degree graph. Given an edge $e$ in $G$ we would like ... more >>>

TR05-143 | 29th November 2005
Parikshit Gopalan

#### Constructing Ramsey Graphs from Boolean Function Representations

Explicit construction of Ramsey graphs or graphs with no large clique or independent set has remained a challenging open problem for a long time. While Erdos's probabilistic argument shows the existence of graphs on 2^n vertices with no clique or independent set of size 2n, the best known explicit constructions ... more >>>

TR01-002 | 6th December 2000
Venkatesan Guruswami

#### Constructions of Codes from Number Fields

We define number-theoretic error-correcting codes based on algebraic
number fields, thereby providing a generalization of Chinese Remainder
Codes akin to the generalization of Reed-Solomon codes to
Algebraic-geometric codes. Our construction is very similar to
(and in fact less general than) the one given by (Lenstra 1986), but
the ... more >>>

TR05-155 | 10th December 2005
Amir Shpilka

#### Constructions of low-degree and error-correcting epsilon-biased sets

In this work we give two new constructions of $\epsilon$-biased
generators. Our first construction answers an open question of
Dodis and Smith, and our second construction
significantly extends a result of Mossel et al.
In particular we obtain the following results:

1. We construct a family of asymptotically good binary ... more >>>

TR98-055 | 4th September 1998
Luca Trevisan

#### Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

We introduce a new approach to construct extractors -- combinatorial
objects akin to expander graphs that have several applications.
Our approach is based on error correcting codes and on the Nisan-Wigderson
pseudorandom generator. An application of our approach yields a
construction that is simple to ... more >>>

TR10-072 | 19th April 2010
Russell Impagliazzo, Valentine Kabanets

#### Constructive Proofs of Concentration Bounds

We give a simple combinatorial proof of the Chernoff-Hoeffding concentration bound~\cite{Chernoff, Hof63}, which says that the sum of independent $\{0,1\}$-valued random variables is highly concentrated around the expected value. Unlike the standard proofs,
our proof does not use the method of higher moments, but rather uses a simple ... more >>>

TR08-047 | 17th March 2008
Vijay V. Vazirani, Wang Lei

#### Continuity Properties of Equilibria in Some Fisher and Arrow-Debreu Market Models

Following up on the work of Megiddo and Vazirani \cite{MV.2007}, who
determined continuity properties of equilibrium prices and
allocations for perhaps the simplest market model, Fisher's linear
case, we do the same for:
\begin{itemize}
\item
Fisher's model with piecewise-linear, concave utilities
\item
Fisher's model with spending constraint utilities
\item
Arrow-Debreu's ... more >>>

TR09-136 | 9th December 2009
Michael Burr, Felix Krahmer, Chee Yap

#### Continuous Amortization: A Non-Probabilistic Adaptive Analysis Technique

Let $f$ be a univariate polynomial with real coefficients, $f\in\RR[X]$. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the roots of $f$ in a given interval. In this paper, we consider subdivision algorithms based on purely numerical primitives such as function evaluation.
more >>>

TR18-170 | 4th October 2018
Nicola Galesi, Navid Talebanfard, Jacobo Toran

#### Cops-Robber games and the resolution of Tseitin formulas

We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed ... more >>>

TR12-172 | 8th December 2012
Mahdi Cheraghchi, Anna Gal, Andrew Mills

#### Correctness and Corruption of Locally Decodable Codes

Locally decodable codes (LDCs) are error correcting codes with the extra property that it is sufficient to read just a small number of positions of a possibly corrupted codeword in order to recover any one position of the input. To achieve this, it is necessary to use randomness in the ... more >>>

TR14-184 | 29th December 2014
Ruiwen Chen, Valentine Kabanets

#### Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits

We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic #SAT algorithms for small linear-size circuits. In particular, we prove that, for boolean circuits of size $3n - n^{0.51}$, the correlation with Parity is at most $2^{-n^{\Omega(1)}}$, and there ... more >>>

TR15-122 | 29th July 2015
Shiteng Chen, Periklis Papakonstantinou

#### Correlation lower bounds from correlation upper bounds

We show that for any coprime $m,r$ there is a circuit of the form $\text{MOD}_m\circ \text{AND}_{d(n)}$ whose correlation with $\text{MOD}_r$ is at least $2^{-O\left( \frac{n}{d(n)} \right) }$. This is the first correlation lower bound for arbitrary $m,r$, whereas previously lower bounds were known for prime $m$. Our motivation is the ... more >>>

TR11-029 | 6th March 2011
Hamed Hatami, Shachar Lovett

Revisions: 1

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function $f:\mathbb{F}_p^n \rightarrow \mathbb{F}_p$ with polynomials of degree at most $d \le ... more >>> TR18-134 | 24th July 2018 Tali Kaufman, David Mass #### Cosystolic Expanders over any Abelian Group In this work we show a general reduction from high dimensional complexes to their links based on the spectral properties of the links. We use this reduction to show that if a certain property is testable in the links, then it is also testable in the complex. In particular, we ... more >>> TR18-046 | 9th March 2018 Oded Goldreich, Guy Rothblum #### Counting$t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems Revisions: 2 We present two main results regarding the complexity of counting the number of$t$-cliques in a graph. \begin{enumerate} \item{\em A worst-case to average-case reduction}: We reduce counting$t$-cliques in any$n$-vertex graph to counting$t$-cliques in typical$n$-vertex graphs that are drawn from a simple distribution of min-entropy${\widetilde\Omega}(n^2)$. For ... more >>> TR19-033 | 20th February 2019 Ashish Dwivedi, Rajat Mittal, Nitin Saxena #### Counting basic-irreducible factors mod$p^k$in deterministic poly-time and$p$-adic applications Finding an irreducible factor, of a polynomial$f(x)$modulo a prime$p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of$f\bmod p$. We can ask the same question modulo prime-powers$p^k$. The irreducible ... more >>> TR10-101 | 25th June 2010 Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer #### Counting Classes and the Fine Structure between NC$^1$and L. The class NC$^1$of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$and L based on counting functions or, ... more >>> TR05-091 | 11th August 2005 Predrag Tosic #### Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs Revisions: 1 We study counting various types of con gurations in certain classes of graph automata viewed as discrete dynamical systems. The graph automata models of our interest are Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively). These models have been proposed as a mathematical foun- dation for a theory of ... more >>> TR97-034 | 3rd September 1997 Jui-Lin Lee #### Counting in uniform$TC^0$In this paper we first give a uniform$AC^0$algorithm which uses partial sums to compute multiple addition. Then we use it to show that multiple addition is computable in uniform$TC^0$by using$count$only once sequentially. By constructing bit matrix for multiple addition, ... more >>> TR10-103 | 28th June 2010 Andreas Krebs, Nutan Limaye, Meena Mahajan #### Counting paths in VPA is complete for \#NC$^1$We give a \#NC$^1$upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran (BCGR: SICOMP 21(4), 1992). We also show that the problem is \#NC$^1$hard. Our ... more >>> TR09-083 | 24th September 2009 Dana Ron, Mira Gonen, Yuval Shavitt #### Counting Stars and Other Small Subgraphs in Sublinear Time Detecting and counting the number of copies of certain subgraphs (also known as {\em network motifs\/} or {\em graphlets\/}), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of ... more >>> TR14-079 | 11th June 2014 Simon Straub, Thomas Thierauf, Fabian Wagner #### Counting the Number of Perfect Matchings in$K_5$-free Graphs Counting the number of perfect matchings in arbitrary graphs is a$\#$P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for$K_{3,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>> TR04-011 | 16th January 2004 Christian Glaßer #### Counting with Counterfree Automata We study the power of balanced regular leaf-languages. First, we investigate (i) regular languages that are polylog-time reducible to languages in dot-depth 1/2 and (ii) regular languages that are polylog-time decidable. For both classes we provide - forbidden-pattern characterizations, and - characterizations in terms of regular expressions. Both ... more >>> TR19-180 | 6th December 2019 Andreas Lenz, Cyrus Rashtchian, Paul Siegel, Eitan Yaakobi #### Covering Codes for Insertions and Deletions A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the ... more >>> TR12-088 | 7th July 2012 Irit Dinur, Gillat Kol #### Covering CSPs We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance C, denoted$\nu(C)$, is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. This covering notion describes situations in which we ... more >>> TR17-047 | 10th March 2017 Kasper Green Larsen, Omri Weinstein, Huacheng Yu #### Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a$\tilde{\Omega}(\log^{1.5} ... more >>>

TR04-101 | 28th September 2004
Miroslav Chlebik, Janka Chlebíková

#### Crown reductions for the Minimum Weighted Vertex Cover problem

TR09-123 | 23rd November 2009
Hemanta Maji, Manoj Prabhakaran, Mike Rosulek

#### Cryptographic Complexity Classes and Computational Intractability Assumptions

Which computational intractability assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question.
We first aim to understand the “cryptographic complexity” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi- party computation functionalities. We consider ... more >>>

TR08-050 | 12th March 2008
Manoj Prabhakaran, Mike Rosulek

#### Cryptographic Complexity of Multi-party Computation Problems: Classifications and Separations

We develop new tools to study the relative complexities of secure
multi-party computation tasks (functionalities) in the Universal
Composition framework. When one task can be securely realized using
another task as a black-box, we interpret this as a
qualitative, complexity-theoretic reduction between the two tasks.
Virtually all previous characterizations of ... more >>>

TR02-017 | 12th March 2002
Aggelos Kiayias, Moti Yung

#### Cryptographic Hardness based on the Decoding of Reed-Solomon Codes with Applications

We investigate the decoding problem of Reed-Solomon Codes (aka: the Polynomial Reconstruction Problem -- PR) from a cryptographic hardness perspective. First, following the standard methodology for constructing cryptographically strong primitives, we formulate a decisional intractability assumption related to the PR problem. Then, based on this assumption we show: (i) hardness ... more >>>

TR15-027 | 25th February 2015
Benny Applebaum

#### Cryptographic Hardness of Random Local Functions -- Survey

Revisions: 1

Constant parallel-time cryptography allows to perform complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use \emph{random local functions} in which each ... more >>>

TR06-057 | 19th April 2006

#### Cryptographic Hardness Results for Learning Intersections of Halfspaces

We give the first representation-independent hardness results for
PAC learning intersections of halfspaces, a central concept class
in computational learning theory. Our hardness results are derived
from two public-key cryptosystems due to Regev, which are based on the
worst-case hardness of well-studied lattice problems. Specifically, we
prove that a polynomial-time ... more >>>

TR08-104 | 23rd November 2008

#### CSP Gaps and Reductions in the Lasserre Hierarchy

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck recently showed the first integrality gaps for these
problems, showing that for MAX k-XOR, the ratio of the SDP optimum to the integer optimum may be as large as ... more >>>

TR19-013 | 31st January 2019
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

#### CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, ... more >>>

TR16-205 | 22nd December 2016
Amey Bhangale, Irit Dinur, Inbal Livni Navon

#### Cube vs. Cube Low Degree Test

We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension $3$) that intersect on a ... more >>>

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

#### Cubic Formula Size Lower Bounds Based on Compositions with Majority

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

TR08-037 | 29th February 2008
Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

#### Curves That Must Be Retraced

Revisions: 1

We exhibit a polynomial time computable plane curve GAMMA that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f ... more >>>

ISSN 1433-8092 | Imprint