Under the auspices of the Computational Complexity Foundation (CCF)

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

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

#### Tableau vs. Sequent Calculi for Minimal Entailment

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

TR00-033 | 22nd May 2000
Jan Krajicek

#### Tautologies from pseudo-random generators

Revisions: 1

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

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

#### Teaching and compressing for low VC-dimension

In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. We present relatively efficient constructions of {\em sample compression schemes} and
n\cdot\log\frac{1}{\varepsilon}}{\varepsilon\cdot\Phi^2})$, where$n$is the number of vertices and$m$is the number ... more >>> TR06-053 | 6th April 2006 Eldar Fischer, Orly Yahalom #### Testing Convexity Properties of Tree Colorings A coloring of a graph is {\it convex} if it induces a partition of the vertices into connected subgraphs. Besides being an interesting property from a theoretical point of view, tests for convexity have applications in various areas involving large graphs. Our results concern the important subcase of testing for ... more >>> TR16-086 | 29th May 2016 Noga Alon, Klim Efremenko, Benny Sudakov #### Testing Equality in Communication Graphs Revisions: 1 Let$G=(V,E)$be a connected undirected graph with$k$vertices. Suppose that on each vertex of the graph there is a player having an$n$-bit string. Each player is allowed to communicate with its neighbors according to an agreed communication protocol, and the players must decide, deterministically, if their inputs ... more >>> TR14-003 | 10th January 2014 Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka #### Testing Equivalence of Polynomials under Shifts Revisions: 2 , Comments: 1 Two polynomials$f, g \in F[x_1, \ldots, x_n]$are called shift-equivalent if there exists a vector$(a_1, \ldots, a_n) \in {F}^n$such that the polynomial identity$f(x_1+a_1, \ldots, x_n+a_n) \equiv g(x_1,\ldots,x_n)$holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our ... more >>> TR07-076 | 25th July 2007 Satyen Kale, C. Seshadhri #### Testing Expansion in Bounded Degree Graphs Revisions: 1 We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound$d$, an expansion bound$\alpha$, and a parameter$\epsilon > 0$, accepts the graph with high probability if its expansion is more than$\alpha$, and ... more >>> TR07-077 | 7th August 2007 Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan #### Testing for Concise Representations We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>> TR19-083 | 4th June 2019 Lior Gishboliner, Asaf Shapira #### Testing Graphs against an Unknown Distribution Revisions: 1 The area of graph property testing seeks to understand the relation between the global properties of a graph and its local statistics. In the classical model, the local statistics of a graph is defined relative to a uniform distribution over the graph’s vertex set. A graph property$\mathcal{P}$is said ... more >>> TR00-083 | 18th September 2000 Eldar Fischer #### Testing graphs for colorability properties Revisions: 1 Let$P$be a property of graphs. An$\epsilon$-test for$P$is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph$G$with$n$vertices are adjacent or not, distinguishes, with high probability, between the case of$G$satisfying ... more >>> TR18-171 | 10th October 2018 Oded Goldreich #### Testing Graphs in Vertex-Distribution-Free Models Revisions: 1 Prior studies of testing graph properties presume that the tester can obtain uniformly distributed vertices in the tested graph (in addition to obtaining answers to the some type of graph-queries). Here we envision settings in which it is only feasible to obtain random vertices drawn according to an arbitrary distribution ... more >>> TR07-128 | 10th November 2007 Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio #### Testing Halfspaces This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w &#8901; x - &#952;). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... more >>> TR07-083 | 23rd August 2007 Artur Czumaj, Asaf Shapira, Christian Sohler #### Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs We study property testing in the model of bounded degree graphs. It is well known that in this model many graph properties cannot be tested with a constant number of queries and it seems reasonable to conjecture that only few are testable with o(sqrt{n}) queries. Therefore in this paper ... more >>> TR17-058 | 7th April 2017 Noga Alon, Omri Ben-Eliezer, Eldar Fischer #### Testing hereditary properties of ordered graphs and matrices Revisions: 1 We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries. We also explain how the proof can ... more >>> TR17-006 | 15th December 2016 Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath #### Testing Ising Models Revisions: 2 Given samples from an unknown multivariate distribution$p$, is it possible to distinguish whether$p$is the product of its marginals versus$p$being far from every product distribution? Similarly, is it possible to distinguish whether$p$equals a given distribution$q$versus$p$and$q$being far from each ... more >>> TR19-102 | 10th August 2019 Oded Goldreich #### Testing Isomorphism in the Bounded-Degree Graph Model Revisions: 1 We consider two versions of the problem of testing graph isomorphism in the bounded-degree graph model: A version in which one graph is fixed, and a version in which the input consists of two graphs. We essentially determine the query complexity of these testing problems in the special case of ... more >>> TR16-136 | 31st August 2016 Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer #### Testing k-Monotonicity Revisions: 1 A Boolean$k$-monotone function defined over a finite poset domain${\cal D}$alternates between the values$0$and$1$at most$k$times on any ascending chain in${\cal D}$. Therefore,$k$-monotone functions are natural generalizations of the classical monotone functions, which are the$1$-monotone functions. Motivated by the ... more >>> TR11-005 | 20th January 2011 Madhu Sudan #### Testing Linear Properties: Some general themes Revisions: 1 The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be linear''. In particular, ... more >>> TR08-088 | 13th September 2008 Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie #### Testing Linear-Invariant Non-Linear Properties Revisions: 1 We consider the task of testing properties of Boolean functions that are invariant under linear transformations of the Boolean cube. Previous work in property testing, including the linearity test and the test for Reed-Muller codes, has mostly focused on such tasks for linear properties. The one exception is a test ... more >>> TR10-116 | 21st July 2010 Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie #### Testing linear-invariant non-linear properties: A short report The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied ... more >>> TR18-067 | 9th April 2018 Alessandro Chiesa, Peter Manohar, Igor Shinkar #### Testing Linearity against Non-Signaling Strategies Revisions: 1 Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography. We ... more >>> TR12-076 | 12th June 2012 Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova #### Testing Lipschitz Functions on Hypergrid Domains A function$f(x_1, ... , x_d)$, where each input is an integer from 1 to$n$and output is a real number, is Lipschitz if changing one of the inputs by 1 changes the output by at most 1. In other words, Lipschitz functions are not very sensitive to small ... more >>> TR18-196 | 19th November 2018 Omri Ben-Eliezer #### Testing local properties of arrays We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of$d$-dimensional arrays$f:[n]^d \to \Sigma$is$k$-local if it can be defined by a family of$k \times \ldots \times k$forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and ... more >>> TR12-001 | 1st January 2012 Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett #### Testing Low Complexity Affine-Invariant Properties Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, ... more >>> TR10-027 | 28th February 2010 Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant #### Testing monotonicity of distributions over general partial orders We investigate the number of samples required for testing the monotonicity of a distribution with respect to an arbitrary underlying partially ordered set. Our first result is a nearly linear lower bound for the sample complexity of testing monotonicity with respect to the poset consisting of a directed perfect matching. ... more >>> TR19-124 | 28th August 2019 Roy Gotlib, Tali Kaufman #### Testing Odd Direct Sums Using High Dimensional Expanders In this work, using methods from high dimensional expansion, we show that the property of$k$-direct-sum is testable for odd values of$k$. Previous work of Kaufman and Lubotzky could inherently deal only with the case that$k$is even, using a reduction to linearity testing. Interestingly, our work ... more >>> TR11-075 | 6th May 2011 Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira #### Testing Odd-Cycle-Freeness in Boolean Functions Call a function$f: \mathbb{F}_2^n \to \{0,1\}$odd-cycle-free if there are no$x_1, \dots, x_k \in \mathbb{F}_2^n$with$k$an odd integer such that$f(x_1) = \cdots = f(x_k) = 1$and$x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those$\epsilon$-far ... more >>> TR10-065 | 13th April 2010 Tali Kaufman, Shachar Lovett #### Testing of exponentially large codes, by a new extension to Weil bound for character sums Revisions: 1 In this work we consider linear codes which are locally testable in a sublinear number of queries. We give the first general family of locally testable codes of exponential size. Previous results of this form were known only for codes of quasi-polynomial size (e.g. Reed-Muller codes). We accomplish this by ... more >>> TR05-153 | 9th December 2005 Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur #### Testing Orientation Properties We propose a new model for studying graph related problems that we call the \emph{orientation model}. In this model, an undirected graph$G$is fixed, and the input is any possible edge orientation of$G$. A property is now a property of the directed graph that is obtained by a ... more >>> TR04-092 | 3rd November 2004 Oded Lachish, Ilan Newman #### Testing Periodicity A string$\alpha\in\Sigma^n$is called {\it p-periodic}, if for every$i,j \in \{1,\dots,n\}$, such that$i\equiv j \bmod p$,$\alpha_i = \alpha_{j}$, where$\alpha_i$is the$i$-th place of$\alpha$. A string$\alpha\in\Sigma^n$is said to be$period(\leq g)$, if there exists$p\in \{1,\dots,g\}$such that$\alpha$... more >>> TR12-094 | 19th July 2012 Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva #### Testing Permanent Oracles -- Revisited Suppose we are given an oracle that claims to approximate the permanent for most matrices$X$, where$X$is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task. ... more >>> TR14-021 | 18th February 2014 Clement Canonne, Ronitt Rubinfeld #### Testing probability distributions underlying aggregated data In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution$D$over$[n]$. More precisely, we define both the dual and extended ... more >>> TR12-155 | 15th November 2012 Clement Canonne, Dana Ron, Rocco Servedio #### Testing probability distributions using conditional samples Revisions: 1 We study a new framework for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle. \footnote{Independently from our work, Chakraborty et al. [CFGM13] also considered this framework. We discuss their work in Subsection 1.4.} This is an oracle that takes as ... more >>> TR10-157 | 24th October 2010 Reut Levi, Dana Ron, Ronitt Rubinfeld #### Testing Properties of Collections of Distributions Revisions: 1 We propose a framework for studying property testing of collections of distributions, where the number of distributions in the collection is a parameter of the problem. Previous work on property testing of distributions considered single distributions or pairs of distributions. We suggest two models that differ in the way the ... more >>> TR07-054 | 25th May 2007 Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur #### Testing Properties of Constraint-Graphs We study a model of graph related formulae that we call the \emph{Constraint-Graph model}. A constraint-graph is a labeled multi-graph (a graph where loops and parallel edges are allowed), where each edge$e$is labeled by a distinct Boolean variable and every vertex is associate with a Boolean function over ... more >>> TR12-055 | 4th May 2012 Reut Levi, Dana Ron, Ronitt Rubinfeld #### Testing Similar Means We consider the problem of testing a basic property of collections of distributions: having similar means. Namely, the algorithm should accept collections of distributions in which all distributions have means that do not differ by more than some given parameter, and should reject collections that are relatively far from having ... more >>> TR07-135 | 26th December 2007 Paul Valiant, Paul Valiant #### Testing Symmetric Properties of Distributions We introduce the notion of a Canonical Tester for a class of properties, that is, a tester strong and general enough that a property is testable if and only if the Canonical Tester tests it''. We construct a Canonical Tester for the class of symmetric properties of one or two more >>> TR07-118 | 27th November 2007 Asaf Nachmias, Asaf Shapira #### Testing the Expansion of a Graph We study the problem of testing the expansion of graphs with bounded degree d in sublinear time. A graph is said to be an \alpha-expander if every vertex set U \subset V of size at most |V|/2 has a neighborhood of size at least \alpha|U|. We show that the algorithm ... more >>> TR03-076 | 8th September 2003 Michael Langberg #### Testing the independence number of hypergraphs A$k$-uniform hypergraph$G$of size$n$is said to be$\varepsilon$-far from having an independent set of size$\rho n$if one must remove at least$\varepsilon n^k$edges of$G$in order for the remaining hypergraph to have an independent set of size$\rho n$. In this work, ... more >>> TR11-076 | 7th May 2011 Eric Miles, Emanuele Viola #### The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs Revisions: 1 We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous constructions. In particular, we ... more >>> TR13-040 | 11th March 2013 Michaël Cadilhac, Andreas Krebs, Pierre McKenzie #### The Algebraic Theory of Parikh Automata Revisions: 2 The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theory of typed monoids is used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh ... more >>> TR99-043 | 5th November 1999 Venkatesan Guruswami #### The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses We prove hardness results for approximating set splitting problems and also instances of satisfiability problems which have no mixed'' clauses, i.e all clauses have either all their literals unnegated or all of them negated. Recent results of Hastad imply tight hardness results for set splitting when all sets ... more >>> TR12-169 | 22nd November 2012 Noga Alon, Santosh Vempala #### The Approximate Rank of a Matrix and its Algorithmic Applications Revisions: 2 We introduce and study the \epsilon-rank of a real matrix A, defi ned, for any  \epsilon > 0 as the minimum rank over matrices that approximate every entry of A to within an additive \epsilon. This parameter is connected to other notions of approximate rank and is motivated by ... more >>> TR04-079 | 30th August 2004 John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn #### The Arithmetical Complexity of Dimension and Randomness Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1]. Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong ... more >>> TR15-143 | 31st August 2015 Benjamin Rossman #### The Average Sensitivity of Bounded-Depth Formulas We show that unbounded fan-in boolean formulas of depth$d+1$and size$s$have average sensitivity$O(\frac{1}{d}\log s)^d$. In particular, this gives a tight$2^{\Omega(d(n^{1/d}-1))}$lower bound on the size of depth$d+1$formulas computing the PARITY function. These results strengthen the corresponding$2^{\Omega(n^{1/d})}$and$O(\log s)^d$bounds for circuits ... more >>> TR16-181 | 15th November 2016 Avishay Tal #### The Bipartite Formula Complexity of Inner-Product is Quadratic A bipartite formula on binary variables$x_1, \ldots, x_n$and$y_1, \ldots, y_n$is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves may compute any function of either the$x$or$y$variables. We show that any bipartite formula for the Inner-Product ... more >>> TR07-125 | 11th October 2007 Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka #### The black-box query complexity of polynomial summation For any given Boolean formula$\phi(x_1,\dots,x_n)$, one can efficiently construct (using \emph{arithmetization}) a low-degree polynomial$p(x_1,\dots,x_n)$that agrees with$\phi$over all points in the Boolean cube$\{0,1\}^n$; the constructed polynomial$p$can be interpreted as a polynomial over an arbitrary field$\mathbb{F}$. The problem ... more >>> TR96-032 | 12th March 1996 Manindra Agrawal, Thomas Thierauf #### The Boolean Isomorphism Problem We investigate the computational complexity of the Boolean Isomorphism problem (BI): on input of two Boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. Our main result is a one-round interactive proof ... more >>> TR16-096 | 14th June 2016 Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay #### The Chasm at Depth Four, and Tensor Rank : Old results, new insights Revisions: 2 Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this ... more >>> TR17-148 | 6th October 2017 Or Meir, Avishay Tal #### The Choice and Agreement Problems of a Random Function Revisions: 3 The direct-sum question is a classical question that asks whether performing a task on$m$independent inputs is$m$times harder than performing it on a single input. In order to study this question, Beimel et. al (Computational Complexity 23(1), 2014) introduced the following related problems: * The choice ... more >>> TR15-066 | 20th April 2015 Scott Aaronson, Daniel Grier, Luke Schaeffer #### The Classification of Reversible Bit Operations We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical ... more >>> TR17-090 | 15th May 2017 Chin Ho Lee, Emanuele Viola #### The coin problem for product tests Let$X_{m, \eps}$be the distribution over$m$bits$(X_1, \ldots, X_m)$where the$X_i$are independent and each$X_i$equals$1$with probability$(1+\eps)/2$and$0$with probability$(1-\eps)/2$. We consider the smallest value$\eps^*$of$\eps$such that the distributions$X_{m,\eps}$and$X_{m,0}$can be distinguished with constant more >>> TR18-157 | 10th September 2018 Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh #### The Coin Problem in Constant Depth: Sample Complexity and Parity gates Revisions: 2 The$\delta$-Coin Problem is the computational problem of distinguishing between coins that are heads with probability$(1+\delta)/2$or$(1-\delta)/2,$where$\delta$is a parameter that is going to$0$. We study the complexity of this problem in the model of constant-depth Boolean circuits and prove the following results. 1. Upper ... more >>> TR11-152 | 12th November 2011 Emanuele Viola #### The communication complexity of addition Suppose each of$k \le n^{o(1)}$players holds an$n$-bit number$x_i$in its hand. The players wish to determine if$\sum_{i \le k} x_i = s$. We give a public-coin protocol with error$1\%$and communication$O(k \lg k)$. The communication bound is independent of$n$, and for$k ... more >>>

TR06-151 | 10th December 2006

#### The communication complexity of correlation

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

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

#### The Communication Complexity of Enumeration, Elimination, and Selection

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

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

#### The Communication Complexity of Gap Hamming Distance

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

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

#### The communication complexity of interleaved group products

Revisions: 1

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

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

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

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

TR18-033 | 16th February 2018
Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz

#### The Communication Complexity of Private Simultaneous Messages, Revisited

Revisions: 2

Private Simultaneous Message (PSM) protocols were introduced by Feige, Kilian and Naor (STOC '94) as a minimal non-interactive model for information-theoretic three-party secure computation. While it is known that every function $f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$ admits a PSM protocol with exponential communication of $2^{k/2}$ (Beimel et al., TCC '14), the ... more >>>

TR20-006 | 22nd January 2020
Anup Rao, Amir Yehudayoff

#### The Communication Complexity of the Exact Gap-Hamming Problem

We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.

more >>>

TR19-053 | 5th April 2019
Andrei Krokhin, Jakub Opršal

#### The complexity of 3-colouring $H$-colourable graphs

We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph $H$, the $H$-colouring problem is to decide whether a given graph has a homomorphism to $H$. By a result of Hell and Nešet?il, this problem is NP-hard for any non-bipartite graph $H$. In ... more >>>

TR04-061 | 30th June 2004
Scott Aaronson

#### The Complexity of Agreement

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

TR05-115 | 27th September 2005

#### The complexity of computing a Nash equilibrium

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

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

#### The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

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

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

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

Revisions: 2

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

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

#### The complexity of constraints on intervals and lengths

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

TR04-020 | 8th March 2004
Emanuele Viola

#### The Complexity of Constructing Pseudorandom Generators from Hard Functions

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

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

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

#### The Complexity of Debate Checking

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

TR07-045 | 24th April 2007
Heribert Vollmer

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

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

TR13-124 | 9th September 2013
Thomas Watson

#### The Complexity of Deciding Statistical Properties of Samplable Distributions

Revisions: 2

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

TR06-049 | 9th April 2006
Guy Wolfovitz

#### The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions

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

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

#### The Complexity of DNF of Parities

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

TR12-070 | 26th May 2012
Thomas Watson

#### The Complexity of Estimating Min-Entropy

Revisions: 1

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

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

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

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

... more >>>

TR19-040 | 19th February 2019
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

#### The Complexity of Finding {$S$}-factors in Regular Graphs

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.
The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ... more >>>

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

#### The Complexity of Forecast Testing

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

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

#### The Complexity of Generalized Satisfiability for Linear Temporal Logic

Revisions: 1

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

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

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

#### The Complexity of Geometric Graph Isomorphism

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

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

#### The Complexity of Intersecting Finite Automata Having Few Final States

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

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

#### The complexity of learning SUBSEQ(A)

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

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

#### The Complexity of Local List Decoding

Revisions: 1

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

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

#### The complexity of matrix rank and feasible systems of linear equations

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

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

#### The complexity of mean payoff games on graphs

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

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

#### The Complexity of Minimal Satisfiability Problems

Revisions: 2

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

TR99-001 | 4th January 1999
Detlef Sieling

#### The Complexity of Minimizing FBDDs

Revisions: 1

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

TR18-120 | 21st June 2018
Alexandros Hollender, Paul Goldberg

#### The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard

The complexity class PPAD is usually defined in terms of the END-OF-LINE problem, in which we are given a concise representation of a large directed graph having indegree and outdegree at most 1, and a known source, and we seek some other degree-1 vertex. We show that variants where we ... more >>>

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

#### The Complexity of Online Memory Checking

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

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

#### The Complexity of Problems for Quantified Constraints

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

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

#### The complexity of proving that a graph is Ramsey

Revisions: 1

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

TR17-065 | 20th April 2017
Boaz Barak

#### The Complexity of Public-Key Cryptograph

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

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

TR16-109 | 18th July 2016
Scott Aaronson

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

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

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

#### The Complexity of Rationalizing Matchings

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

... more >>>

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

#### The Complexity of Rationalizing Network Formation

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

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

#### The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

Revisions: 1

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

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

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

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

Some solution notions S ... more >>>

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

#### The Complexity of Somewhat Approximation Resistant Predicates

Revisions: 1

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

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

#### The Complexity of Tensor Calculus

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

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

#### The Complexity of Testing Monomials in Multivariate Polynomials

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

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

#### The complexity of the counting constraint satisfaction problem

Revisions: 1

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

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

#### The Complexity of the Hajos Calculus for Planar Graphs

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

more >>>

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

#### The Complexity of the Minimal Polynomial

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

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

TR13-016 | 17th January 2013
Olaf Beyersdorff

#### The Complexity of Theorem Proving in Autoepistemic Logic

Revisions: 1

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

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

#### The Complexity of Theorem Proving in Circumscription and Minimal Entailment

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

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

#### The Complexity of Two Register and Skew Arithmetic Computation

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

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

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

#### The Complexity of Unions of Disjoint Sets

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

more >>>

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

#### The Computational Benefit of Correlated Instances

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

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

#### The computational complexity of Evolutionarily Stable Strategies

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

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

#### The Computational Complexity of Linear Optics

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

TR05-052 | 5th May 2005

#### The Computational Complexity of Nash Equilibria in Concisely Represented Games

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

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

#### The Computational Complexity of Some Problems of Linear Algebra

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

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

#### The computational hardness of pricing compound options

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

TR96-025 | 22nd March 1996
Berthold Ruf

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

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

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

#### The Computing Power of Programs over Finite Monoids

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

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

#### The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Revisions: 1

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

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

#### The Degree of Threshold Mod 6 and Diophantine Equations

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

TR09-030 | 5th April 2009
Shachar Lovett

#### The density of weights of Generalized Reed-Muller codes

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

TR14-124 | 7th October 2014
Periklis Papakonstantinou

#### The Depth Irreducibility Hypothesis

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

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

#### The Descriptive Complexity Approach to LOGCFL

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

TR06-035 | 19th January 2006
Till Tantau

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

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

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

#### The Deterministic and Randomized Query Complexity of a Simple Guessing Game

Revisions: 1

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

TR18-177 | 1st October 2018
Alexander Knop

#### The Diptych of Communication Complexity Classes in the Best-partition Model and the Fixed-partition Model

Most of the research in communication complexity theory is focused on the
fixed-partition model (in this model the partition of the input between
Alice and Bob is fixed). Nonetheless, the best-partition model (the model
that allows Alice and Bob to choose the partition) has a lot of
more >>>

TR17-128 | 15th August 2017
Or Meir

#### The Direct Sum of Universal Relations

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

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

#### The Directed Planar Reachability Problem

Revisions: 1

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

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

#### The Entropy Influence Conjecture Revisited

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

TR10-128 | 15th August 2010
Scott Aaronson

#### The Equivalence of Sampling and Searching

Revisions: 1

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

TR19-076 | 24th May 2019
Leroy Chew, Judith Clymo

#### The Equivalences of Refutational QRAT

The solving of Quantified Boolean Formulas (QBF) has been advanced considerably in the last two decades. In response to this, several proof systems have been put forward to universally verify QBF solvers.
QRAT by Heule et al. is one such example of this and builds on technology from DRAT, ... more >>>

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

#### The Exact Multiplicative Complexity of the Hamming Weight Function

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

TR19-009 | 16th January 2019
Jiawei Gao, Russell Impagliazzo

#### The Fine-Grained Complexity of Strengthenings of First-Order Logic

Revisions: 1

The class of model checking for first-order formulas on sparse graphs has a complete problem with respect to fine-grained reductions, Orthogonal Vectors (OV) [GIKW17]. This paper studies extensions of this class or more lenient parameterizations. We consider classes obtained by allowing function symbols;
first-order on ordered structures; adding various notions ... more >>>

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

#### The Firefighter Problem: A Structural Analysis

Revisions: 1

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

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

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

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

TR16-025 | 26th February 2016
Shachar Lovett

#### The Fourier structure of low degree polynomials

Revisions: 1

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

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

#### The Freiman-Ruzsa Theorem in Finite Fields

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

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

#### The Frequent Paucity of Trivial Strings

Revisions: 1

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

TR18-182 | 31st October 2018
Henry Corrigan-Gibbs, Dmitry Kogan

#### The Function-Inversion Problem: Barriers and Opportunities

Revisions: 1

We study preprocessing algorithms for the function-inversion problem. In this problem, an algorithm gets oracle access to a function $f\colon[N] \to [N]$ and takes as input $S$ bits of auxiliary information about $f$, along with a point $y \in [N]$. After running for time $T$, the algorithm must output an ... more >>>

TR02-047 | 3rd August 2002
Oded Goldreich

#### The GGM Construction does NOT yield Correlation Intractable Function Ensembles.

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

TR99-034 | 30th August 1999
Wolfgang Merkle

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

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

TR96-054 | 2nd November 1996
Oded Goldreich

#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

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

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

#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

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

TR19-016 | 5th February 2019
Alexander A. Sherstov

#### The hardest halfspace

We study the approximation of halfspaces $h:\{0,1\}^n\to\{0,1\}$ in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the "hardest" halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all ... more >>>

TR18-193 | 14th November 2018
Nicollas Sdroievski, Murilo Silva, André Vignatti

#### The Hidden Subgroup Problem and MKTP

We show that the Hidden Subgroup Problem for black-box groups is in $\mathrm{BPP}^\mathrm{MKTP}$ (where $\mathrm{MKTP}$ is the Minimum $\mathrm{KT}$ Problem) using the techniques of Allender et al (2018). We also show that the problem is in $\mathrm{ZPP}^\mathrm{MKTP}$ provided that there is a \emph{pac overestimator} computable in $\mathrm{ZPP}^\mathrm{MKTP}$ for the logarithm ... more >>>

TR16-020 | 8th February 2016
Zachary Remscrim

#### The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

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

TR07-095 | 13th July 2007

#### The Ideal Membership Problem and Polynomial Identity Testing

Revisions: 2

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

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

#### The Importance of Being Biased

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

more >>>

TR94-014 | 12th December 1994
Miklos Ajtai

#### The Independence of the modulo p Counting Principles

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

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

#### The influence lower bound via query elimination

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

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

#### The Informational Content of Canonical Disjoint NP-Pairs

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

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

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

#### The intersection of two halfspaces has high threshold degree

Revisions: 1

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

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

#### The Inverse Shapley Value Problem

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

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

#### The Isomorphism Problem for k-Trees is Complete for Logspace

Revisions: 1

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

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

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

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

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

TR96-040 | 21st May 1996
Thomas Thierauf

#### The Isomorphismproblem for One-Time-Only Branching Programs

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

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

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

#### The Journey from NP to TFNP Hardness

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

TR06-070 | 23rd May 2006
Ludwig Staiger

#### The Kolmogorov complexity of infinite words

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

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

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

#### The Landscape of Communication Complexity Classes

Revisions: 1

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

TR18-143 | 16th August 2018
Mark Bun, Justin Thaler

#### The Large-Error Approximate Degree of AC$^0$

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight $\tilde{\Omega}(n^{1/2})$ lower bound on the threshold degree of the Surjectivity function on $n$ variables. This matches the best known threshold degree bound for any AC$^0$ ... more >>>

TR06-106 | 18th August 2006
Scott Aaronson

#### The Learnability of Quantum States

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

TR19-182 | 9th December 2019
Zachary Remscrim

\Q ^{n\times n}$and vectors$\x,\y\in \Q ^n$, does there exist a non-negative integer$i$such that$A^i\x=\y$. This problem was shown to be in deterministic polynomial time by Kannan and Lipton in \cite{KL1986}. In this paper we place ... more >>> TR13-149 | 28th October 2013 Albert Atserias, Neil Thapen #### The Ordering Principle in a Fragment of Approximate Counting The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over$\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk ... more >>> TR95-013 | 24th February 1995 Oleg Verbitsky #### The Parallel Repetition Conjecture for Trees is True The parallel repetition conjecture (PRC) of Feige and Lovasz says that the error probability of a two prover one round interactive protocol repeated$n$times in parallel is exponentially small in$n$. We show that the PRC is true in the case when the bipartite graph of dependence between ... more >>> TR11-071 | 27th April 2011 Serge Gaspers, Stefan Szeider #### The Parameterized Complexity of Local Consistency Revisions: 1 We investigate the parameterized complexity of deciding whether a constraint network is$k$-consistent. We show that, parameterized by$k$, the problem is complete for the complexity class co-W[2]. As secondary parameters we consider the maximum domain size$d$and the maximum number$\ell$of constraints in which a variable occurs. ... more >>> TR07-100 | 25th September 2007 Alexander A. Sherstov #### The Pattern Matrix Method for Lower Bounds on Quantum Communication In a breakthrough result, Razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in the bounded-error quantum model with and without prior entanglement. This was proved by the _multidimensional_ discrepancy method. We give an entirely ... more >>> TR05-046 | 17th April 2005 Irit Dinur #### The PCP theorem by gap amplification Revisions: 1 , Comments: 3 Let C={c_1,...,c_n} be a set of constraints over a set of variables. The {\em satisfiability-gap} of C is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the variables. We prove a new combinatorial amplification lemma that doubles the satisfiability-gap of a constraint-system, with only a linear ... more >>> TR09-051 | 2nd July 2009 Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy #### The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity. The Kolmogorov measures that have been ... more >>> TR96-013 | 14th February 1996 Mitsunori Ogihara #### The PL Hierarchy Collapses It is shown that the PL hierarchy defined in terms of the standard Ruzzo-Simon-Tompa relativization collapses to PL. more >>> TR17-169 | 24th October 2017 Mark Bun, Robin Kothari, Justin Thaler #### The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials The approximate degree of a Boolean function$f$is the least degree of a real polynomial that approximates$f$pointwise to error at most$1/3$. The approximate degree of$f$is known to be a lower bound on the quantum query complexity of$f$(Beals et al., FOCS 1998 and ... more >>> TR06-129 | 6th October 2006 Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf #### The polynomially bounded perfect matching problem is in NC^2 The perfect matching problem is known to be in P, in randomized NC, and it is hard for NL. Whether the perfect matching problem is in NC is one of the most prominent open questions in complexity theory regarding parallel computations. Grigoriev and Karpinski studied the perfect matching problem more >>> TR19-107 | 29th July 2019 Zachary Remscrim #### The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups The two-way quantum/classical finite automaton (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with one-sided bounded-error, the language$L_{eq}=\{a^m b^m |m \in \mathbb{N}\}$in ... more >>> TR15-147 | 8th September 2015 Alexander A. Sherstov #### The Power of Asymmetry in Constant-Depth Circuits The threshold degree of a Boolean function$f$is the minimum degree of a real polynomial$p$that represents$f$in sign:$f(x)\equiv\mathrm{sgn}\; p(x)$. Introduced in the seminal work of Minsky and Papert (1969), this notion is central to some of the strongest algorithmic and complexity-theoretic results for more >>> TR09-036 | 14th April 2009 Chandan Saha, Ramprasad Saptharishi, Nitin Saxena #### The Power of Depth 2 Circuits over Algebras We study the problem of polynomial identity testing (PIT) for depth 2 arithmetic circuits over matrix algebra. We show that identity testing of depth 3 (Sigma-Pi-Sigma) arithmetic circuits over a field F is polynomial time equivalent to identity testing of depth 2 (Pi-Sigma) arithmetic circuits over U_2(F), the ... more >>> TR18-213 | 28th December 2018 Moni Naor, Merav Parter, Eylon Yogev #### The Power of Distributed Verifiers in Interactive Proofs Revisions: 1 We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of$n$nodes and a graph$G$that defines their communication pattern. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the ... more >>> TR95-037 | 2nd July 1995 Richard Beigel, Howard Straubing #### The Power of Local Self-Reductions Identify a string x over {0,1} with the positive integer whose binary representation is 1x. We say that a self-reduction is k-local if on input x all queries belong to {x-1,...,x-k}. We show that all k-locally self-reducible sets belong to PSPACE. However, the power of k-local self-reductions changes drastically between ... more >>> TR17-023 | 15th February 2017 Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich #### The Power of Natural Properties as Oracles We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We obtain new circuit lower bounds, as well as some hardness results for the relativized version ... more >>> TR15-008 | 14th January 2015 Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen #### The Power of Negations in Cryptography Revisions: 1 The study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be ... more >>> TR10-131 | 9th July 2010 Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki #### The Power of Nondeterminism in Self-Assembly We investigate the role of nondeterminism in Winfree's abstract Tile Assembly Model (aTAM), which was conceived to model artificial molecular self-assembling systems constructed from DNA. Designing tile systems that assemble shapes, due to the algorithmic richness of the aTAM, is a form of sophisticated "molecular programming". Of particular practical importance ... more >>> TR17-081 | 2nd May 2017 Badih Ghazi, Madhu Sudan #### The Power of Shared Randomness in Uncertain Communication In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function ... more >>> TR14-064 | 24th April 2014 Arkadev Chattopadhyay, Michael Saks #### The Power of Super-logarithmic Number of Players In the Number-on-Forehead' (NOF) model of multiparty communication, the input is a$k \times m$boolean matrix$A$(where$k$is the number of players) and Player$i$sees all bits except those in the$i$-th row, and the players communicate by broadcast in order to evaluate a specified ... more >>> TR20-004 | 17th January 2020 Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny #### The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>> TR08-051 | 4th April 2008 Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor #### The Power of Unentanglement The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Can ... more >>> TR05-056 | 25th April 2005 Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis #### The Price of Optimum in Stackelberg Games Consider a system M of parallel machines, each with a strictly increasing and differentiable load dependent latency function. The users of such a system are of infinite number and act selfishly, routing their infinitesimally small portion of the total flow r they control, to machines of currently minimum delay. It ... more >>> TR10-034 | 7th March 2010 Luca Trevisan #### The Program-Enumeration Bottleneck in Average-Case Complexity Theory Three fundamental results of Levin involve algorithms or reductions whose running time is exponential in the length of certain programs. We study the question of whether such dependency can be made polynomial. (1) Levin's optimal search algorithm'' performs at most a constant factor more slowly than any other fixed ... more >>> TR11-112 | 10th August 2011 Dana Moshkovitz #### The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover In this paper we put forward a conjecture: an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We refer to this conjecture as the Projection Games Conjecture. We further suggest the research agenda of establishing new hardness of approximation results based on the ... more >>> TR98-078 | 1st December 1998 Vikraman Arvind, K.V. Subrahmanyam, Vinodchandran Variyam #### The Query Complexity of Program Checking by Constant-Depth Circuits In this paper we study program checking (in the sense of Blum and Kannan) using constant-depth circuits as checkers. Our focus is on the number of queries made by the checker to the program being checked and we term this as the query complexity of the checker for the given ... more >>> TR17-080 | 1st May 2017 Joshua Brakensiek, Venkatesan Guruswami #### The Quest for Strong Inapproximability Results with Perfect Completeness The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect ... more >>> TR19-162 | 15th November 2019 Ran Raz, Wei Zhan #### The Random-Query Model and the Memory-Bounded Coupon Collector We study a new model of space-bounded computation, the {\it random-query} model. The model is based on a branching-program over input variables$x_1,\ldots,x_n$. In each time step, the branching program gets as an input a random index$i \in \{1,\ldots,n\}$, together with the input variable$x_i$(rather than querying an ... more >>> TR14-082 | 3rd June 2014 Yu Yu, Dawu Gu, Xiangxue Li #### The Randomized Iterate Revisited - Almost Linear Seed Length PRGs from A Broader Class of One-way Functions Revisions: 3 We revisit the randomized iterate'' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography ... more >>> TR01-099 | 1st October 2001 Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis #### The Range of Stability for Heterogeneous and FIFO Queueing Networks In this paper, we investigate and analyze for the first time the stability properties of heterogeneous networks, which use a combination of different universally stable queueing policies for packet routing, in the Adversarial Queueing model. We interestingly prove that the combination of SIS and LIS policies, LIS and NTS policies, ... more >>> TR17-154 | 12th October 2017 Christoph Berkholz #### The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs We relate different approaches for proving the unsatisfiability of a system of real polynomial equations over Boolean variables. On the one hand, there are the static proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, we consider polynomial calculus, ... more >>> TR03-051 | 20th June 2003 Tsuyoshi Morioka #### The Relative Complexity of Local Search Heuristics and the Iteration Principle Johnson, Papadimitriou and Yannakakis introduce the class$\PLS$consisting of optimization problems for which efficient local- search heuristics exist. We formulate a type-2 problem$\iter$that characterizes$\PLS$in style of Beame et al., and prove a criterion for type-2 problems to be nonreducible to$\iter$. As a corollary, ... more >>> TR09-105 | 27th October 2009 Vikraman Arvind, Srikanth Srinivasan #### The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets Using$\epsilon$-bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an$NC^2$algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace F_n by G^n for an arbitrary fixed ... more >>> TR04-012 | 19th December 2003 Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore #### The Resolution Complexity of Random Graph$k$-Colorability We consider the resolution proof complexity of propositional formulas which encode random instances of graph$k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity. For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any$\epsilon>0$, ... more >>> TR06-133 | 14th October 2006 Alex Hertel, Alasdair Urquhart #### The Resolution Width Problem is EXPTIME-Complete The importance of {\em width} as a resource in resolution theorem proving has been emphasized in work of Ben-Sasson and Wigderson. Their results show that lower bounds on the size of resolution refutations can be proved in a uniform manner by demonstrating lower bounds on the width ... more >>> TR18-024 | 1st February 2018 Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin #### The Riis Complexity Gap for QBF Resolution We give an analogue of the Riis Complexity Gap Theorem for Quanti fied Boolean Formulas (QBFs). Every fi rst-order sentence$\phi$without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like Q-Resolution are either of polynomial size (if$\phi$has no models) or at least ... more >>> TR05-110 | 3rd October 2005 Saurabh Sanghvi, Salil Vadhan #### The Round Complexity of Two-Party Random Selection We study the round complexity of two-party protocols for generating a random$n$-bit string such that the output is guaranteed to have bounded bias (according to some measure) even if one of the two parties deviates from the protocol (even using unlimited computational resources). Specifically, we require that the output's ... more >>> TR97-060 | 2nd December 1997 Manindra Agrawal, Thomas Thierauf #### The Satisfiability Problem for Probabilistic Ordered Branching Programs We show that the satisfiability problem for bounded error probabilistic ordered branching programs is NP-complete. If the error is very small however (more precisely, if the error is bounded by the reciprocal of the width of the branching program), then we have a polynomial-time algorithm for the satisfiability problem. more >>> TR99-037 | 27th August 1999 Johan Hastad, Mats Näslund #### The Security of all RSA and Discrete Log Bits We study the security of individual bits in an RSA encrypted message$E_N(x)$. We show that given$E_N(x)$, predicting any single bit in$x$with only a non-negligible advantage over the trivial guessing strategy, is (through a polynomial time reduction) as hard as breaking ... more >>> TR10-169 | 10th November 2010 Siavosh Benabbas, Konstantinos Georgiou, Avner Magen #### The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs Revisions: 2 We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector chromatic number$2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali-Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to$O(1/ \epsilon)$tightenings we show ... more >>> TR15-118 | 23rd July 2015 Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan #### The shifted partial derivative complexity of Elementary Symmetric Polynomials We continue the study of the shifted partial derivative measure, introduced by Kayal (ECCC 2012), which has been used to prove many strong depth-4 circuit lower bounds starting from the work of Kayal, and that of Gupta et al. (CCC 2013). We show a strong lower bound on the dimension ... more >>> TR98-016 | 24th March 1998 Daniele Micciancio #### The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant. We show that computing the approximate length of the shortest vector in a lattice within a factor c is NP-hard for randomized reductions for any constant c<sqrt(2). We also give a deterministic reduction based on a number theoretic conjecture. more >>> TR97-047 | 20th October 1997 Miklos Ajtai #### The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions. Revisions: 1 We show that the shortest vector problem in lattices with L_2 norm is NP-hard for randomized reductions. Moreover we also show that there is a positive absolute constant c, so that to find a vector which is longer than the shortest non-zero vector by no more than a factor of ... more >>> TR08-029 | 7th January 2008 Christian Glaßer, Christian Reitwießner, Victor Selivanov #### The Shrinking Property for NP and coNP We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results. 1. NP ... more >>> TR08-016 | 26th February 2008 Alexander Razborov, Alexander A. Sherstov #### The Sign-Rank of AC^0 The sign-rank of a matrix A=[A_{ij}] with +/-1 entries is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0 for all i,j. We obtain the first exponential lower bound on the sign-rank of a function in AC^0. Namely, let f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}). We show that the matrix [f(x,y)]_{x,y} has ... more >>> TR15-083 | 14th May 2015 Omri Weinstein, David Woodruff #### The Simultaneous Communication of Disjointness with Applications to Data Streams We study$k$-party set disjointness in the simultaneous message-passing model, and show that even if each element$i\in[n]$is guaranteed to either belong to all$k$parties or to at most$O(1)$parties in expectation (and to at most$O(\log n)$parties with high probability), then$\Omega(n \min(\log 1/\delta, \log ... more >>>

TR03-063 | 2nd July 2003
John Hitchcock

#### The Size of SPP

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

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

#### The space "just above" BQP

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

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

#### The space complexity of cutting planes refutations

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

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

#### The space complexity of recognizing well-parenthesized expressions

Revisions: 4

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

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

#### The Spectral Method for Mixture Models

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

more >>>

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

#### The Spectrum of Small DeMorgan Formulas

Revisions: 1

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

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

#### The Strength of Multilinear Proofs

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

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

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

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

Revisions: 1

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

TR18-045 | 6th March 2018
Oded Goldreich, Dana Ron

#### The Subgraph Testing Model

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.
The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.
The tester is ... more >>>

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

#### The Sublogarithmic Alternating Space World

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

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

TR07-132 | 8th December 2007
Emanuele Viola

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

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

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

TR19-024 | 20th February 2019
Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

#### The Surprising Power of Constant Depth Algebraic Proofs

Revisions: 2

A major open problem in proof complexity is to prove super-polynomial lower bounds for AC^0[p]-Frege proofs. This system is the analog of AC^0[p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years (Razborov, '86 and Smolensky, '87), ... more >>>

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

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

Revisions: 2

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

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

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

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

TR13-144 | 8th October 2013
VyasRam Selvam

#### The two queries assumption and Arthur-Merlin classes

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

1. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $AM = MA$
2. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH \subset MA_{/1}$
3. $\exists\;B\;P^{NP[1]^B}=P^{NP[2]^B}$ and $NP^B \not\subseteq coMA^B$.
4. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH ... more >>> TR16-015 | 4th February 2016 Oded Goldreich #### The uniform distribution is complete with respect to testing identity to a fixed distribution Revisions: 3 Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over$[n]$equals a fixed distribution to this very problem when the fixed distribution is uniform over$[n]$. Our reduction preserves the parameters of the problem, which are$n$and the ... more >>> TR14-100 | 4th August 2014 Salman Beigi, Omid Etesami, Amin Gohari #### The Value of Help Bits in Randomized and Average-Case Complexity "Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity. Amir, Beigel, and Gasarch ... more >>> TR16-147 | 19th September 2016 Ryan O'Donnell, A. C. Cem Say #### The weakness of CTC qubits and the power of approximate counting Revisions: 1 We present two results in structural complexity theory concerned with the following interrelated topics: computation with postselection/restarting, closed timelike curves (CTCs), and approximate counting. The first result is a new characterization of the lesser known complexity class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of ... more >>> TR16-103 | 6th July 2016 Jaikumar Radhakrishnan, Swagato Sanyal #### The zero-error randomized query complexity of the pointer function. The pointer function of G{\"{o}}{\"{o}}s, Pitassi and Watson \cite{DBLP:journals/eccc/GoosP015a} and its variants have recently been used to prove separation results among various measures of complexity such as deterministic, randomized and quantum query complexities, exact and approximate polynomial degrees, etc. In particular, the widest possible (quadratic) separations between deterministic and zero-error ... more >>> TR96-017 | 19th February 1996 Christoph Meinel, Stephan Waack #### The Log Rank'' Conjecture for Modular Communication Complexity The log rank'' conjecture consists in the question how exact the deterministic communication complexity of a problem can be determinied in terms of algebraic invarants of the communication matrix of this problem. In the following, we answer this question in the context of modular communication complexity. ... more >>> TR05-013 | 22nd December 2004 Bin Fu #### Theory and Application of Width Bounded Geometric Separator We introduce the notion of width bounded geometric separator, develop the techniques for its existence as well as algorithm, and apply it to obtain a$2^{O(\sqrt{n})}$time exact algorithm for the disk covering problem, which seeks to determine the minimal number of fixed size disks to cover$n$points on ... more >>> TR03-039 | 19th May 2003 Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán #### Theory Revision with Queries: Horn, Read-once, and Parity Formulas A theory, in this context, is a Boolean formula; it is used to classify instances, or truth assignments. Theories can model real-world phenomena, and can do so more or less correctly. The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is ... more >>> TR11-030 | 9th March 2011 Anna Gal, Andrew Mills #### Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length Locally decodable codes are error correcting codes with the extra property that, in order to retrieve the correct value of just one position of the input with high probability, it is sufficient to read a small number of positions of the corresponding, possibly corrupted ... more >>> TR01-010 | 25th January 2001 Oded Goldreich, Luca Trevisan #### Three Theorems regarding Testing Graph Properties. Revisions: 1 Property testing is a relaxation of decision problems in which it is required to distinguish {\sc yes}-instances (i.e., objects having a predetermined property) from instances that are far from any {\sc yes}-instance. We presents three theorems regarding testing graph properties in the adjacency matrix representation. ... more >>> TR95-056 | 26th November 1995 Oded Goldreich #### Three XOR-Lemmas -- An Exposition We provide an exposition of three Lemmas which relate general properties of distributions with the exclusive-or of certain bit locations. The first XOR-Lemma, commonly attributed to U.V. Vazirani, relates the statistical distance of a distribution from uniform to the maximum bias of the xor of certain bit positions. more >>> TR05-139 | 21st November 2005 Constantinos Daskalakis, Christos H. Papadimitriou #### Three-Player Games Are Hard We prove that computing a Nash equilibrium in a 3-player game is PPAD-complete, solving a problem left open in our recent result on the complexity of Nash equilibria. more >>> TR02-040 | 20th June 2002 Lars Engebretsen, Jonas Holmerin #### Three-Query PCPs with Perfect Completeness over non-Boolean Domains We study non-Boolean PCPs that have perfect completeness and read three positions from the proof. For the case when the proof consists of values from a domain of size d for some integer constant d >= 2, we construct a non-adaptive PCP with perfect completeness more >>> TR15-034 | 8th March 2015 Xin Li #### Three-Source Extractors for Polylogarithmic Min-Entropy We continue the study of constructing explicit extractors for independent general weak random sources. The ultimate goal is to give a construction that matches what is given by the probabilistic method --- an extractor for two independent$n$-bit weak random sources with min-entropy as small as$\log n+O(1)$. Previously, the ... more >>> TR16-131 | 21st August 2016 Andrej Bogdanov, Siyao Guo, Ilan Komargodski #### Threshold Secret Sharing Requires a Linear Size Alphabet We prove that for every$n$and$1 < t < n$any$t$-out-of-$n$threshold secret sharing scheme for one-bit secrets requires share size$\log(t + 1)$. Our bound is tight when$t = n - 1$and$n$is a prime power. In 1990 Kilian and Nisan proved ... more >>> TR11-098 | 11th July 2011 Marek Karpinski, Richard Schmied, Claus Viehmann #### Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs. more >>> TR16-033 | 10th March 2016 Venkatesan Guruswami, Jaikumar Radhakrishnan #### Tight bounds for communication assisted agreement distillation Suppose Alice holds a uniformly random string$X \in \{0,1\}^N$and Bob holds a noisy version$Y$of$X$where each bit of$X$is flipped independently with probability$\epsilon \in [0,1/2]$. Alice and Bob would like to extract a common random string of min-entropy at least$k$. In this ... more >>> TR12-185 | 29th December 2012 Siu Man Chan, Aaron Potechin #### Tight Bounds for Monotone Switching Networks via Fourier Analysis We prove tight size bounds on monotone switching networks for the NP-complete problem of$k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height$h$for the P-complete problem of generation. This gives alternative proofs of the separations of m-NC from m-P and of m-NC$^i$from ... more >>> TR11-150 | 4th November 2011 Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola #### Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates We bound the minimum number$w$of wires needed to compute any (asymptotically good) error-correcting code$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$with minimum distance$\Omega(n)$, using unbounded fan-in circuits of depth$d$with arbitrary gates. Our main results are: (1) If$d=2$then$w = \Theta(n ({\log n/ \log \log n})^2)$. (2) ... more >>> TR10-063 | 12th April 2010 Venkatesan Guruswami, Yuan Zhou #### Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set} Revisions: 1 We study the approximability of two natural Boolean constraint satisfaction problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a {\em near-satisfiable} instance. \begin{enumerate} \item ... more >>> TR14-174 | 14th December 2014 Avishay Tal #### Tight bounds on The Fourier Spectrum of$AC^0$Revisions: 2 We show that$AC^0$circuits of depth$d$and size$m$have at most$2^{-\Omega(k/(\log m)^{d-1})}$of their Fourier mass at level$k$or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case$k=n$. Our result is tight up ... more >>> TR11-011 | 1st February 2011 Ming Lam Leung, Yang Li, Shengyu Zhang #### Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models We study the communication complexity of symmetric XOR functions, namely functions$f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$that can be formulated as$f(x,y)=D(|x\oplus y|)$for some predicate$D: \{0,1,...,n\} \rightarrow \{0,1\}$, where$|x\oplus y|$is the Hamming weight of the bitwise XOR of$x$and$y$. We give a public-coin ... more >>> TR18-038 | 21st February 2018 Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann #### Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees This paper studies lower bounds for arithmetic circuits computing (non-commutative) polynomials. Our conceptual contribution is an exact correspondence between circuits and weighted automata: algebraic branching programs are captured by weighted automata over words, and circuits with unique parse trees by weighted automata over trees. The key notion for understanding the ... more >>> TR06-132 | 17th October 2006 Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani #### Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut Revisions: 1 We study linear programming relaxations of Vertex Cover and Max Cut arising from repeated applications of the lift-and-project'' method of Lovasz and Schrijver starting from the standard linear programming relaxation. For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that the integrality gap remains at least$2-\epsilon$after$\Omega_\epsilon(\log n)$... more >>> TR06-152 | 6th December 2006 Konstantinos Georgiou, Avner Magen, Iannis Tourlakis #### Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1). more >>> TR11-054 | 13th April 2011 Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka #### Tight lower bounds for 2-query LCCs over finite fields A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic self-correcting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction$\delta$of the coordinates are corrupted. LCC's are a stronger form ... more >>> TR07-090 | 11th September 2007 Shachar Lovett #### Tight lower bounds for adaptive linearity tests Revisions: 1 , Comments: 1 Linearity tests are randomized algorithms which have oracle access to the truth table of some function$f$, which are supposed to distinguish between linear functions and functions which are far from linear. Linearity tests were first introduced by Blum, Luby and Rubenfeld in \cite{BLR93}, and were later used in the ... more >>> TR13-090 | 18th June 2013 Elena Grigorescu, Karl Wimmer, Ning Xie #### Tight Lower Bounds for Testing Linear Isomorphism We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. A family of functions$P\subseteq \{\{0,1\}^n \rightarrow \{0,1\}\}$is linear/affine invariant if for any$f\in P$, it is the case that$f\circ L\in P$for any linear/affine transformation$L$of the domain. Motivated by ... more >>> TR03-035 | 21st May 2003 Eran Halperin, Guy Kortsarz, Robert Krauthgamer #### Tight lower bounds for the asymmetric k-center problem In the {\sc$k$-center} problem, the input is a bound$k$and$n$points with the distance between every two of them, such that the distances obey the triangle inequality. The goal is to choose a set of$k$points to serve as centers, so that the maximum distance ... more >>> TR16-130 | 11th August 2016 Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra #### Tight Network Topology Dependent Bounds on Rounds of Communication We prove tight network topology dependent bounds on the round complexity of computing well studied$k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent ... more >>> TR09-109 | 3rd November 2009 Kai-Min Chung, Feng-Hao Liu #### Tight Parallel Repetition Theorems for Public-coin Arguments Following Hastad, Pass, Pietrzak, and Wikstrom (2008), we study parallel repetition theorems for public-coin interactive arguments and their generalization. We obtain the following results: 1. We show that the reduction of Hastad et al. actually gives a tight direct product theorem for public-coin interactive arguments. That is,$n$-fold parallel repetition ... more >>> TR15-053 | 7th April 2015 Massimo Lauria, Jakob Nordström #### Tight Size-Degree Bounds for Sums-of-Squares Proofs We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size n^{Omega(d)} for values of d = d(n) from constant all the way up to n^{delta} for some universal constant delta. This shows that ... more >>> TR20-003 | 15th January 2020 Giuseppe Persiano, Kevin Yeo #### Tight Static Lower Bounds for Non-Adaptive Data Structures In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of$n$points from a universe consisting of$m=n^{1+\Omega(1)}$points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend ... more >>> TR17-168 | 5th November 2017 Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri #### Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Di erentially Private Sampling Revisions: 6 In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by ?(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner ... more >>> TR14-152 | 13th November 2014 Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo #### Tighter Relations Between Sensitivity and Other Complexity Measures Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other major complexity measures. Despite much attention to the problem and major advances ... more >>> TR05-054 | 19th May 2005 Konstantin Pervyshev #### Time Hierarchies for Computations with a Bit of Advice A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any constants a and b such that 1 < a < b, ZPTime[n^a]/1 \subsetneq ZPTime[n^b]/1. The technique introduced in this paper is very general and gives the same hierarchy for NTime \cap coNTime, UTime, ... more >>> TR05-076 | 2nd July 2005 Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev #### Time hierarchies for cryptographic function inversion with advice We prove a time hierarchy theorem for inverting functions computable in polynomial time with one bit of advice. In particular, we prove that if there is a strongly one-way function, then for any k and for any polynomial p, there is a function f computable in linear time with one ... more >>> TR12-026 | 27th March 2012 Thomas Watson #### Time Hierarchies for Sampling Distributions Revisions: 2 We prove that for every constant$k\ge 2$, every polynomial time bound$t$, and every polynomially small$\epsilon$, there exists a family of distributions on$k$elements that can be sampled exactly in polynomial time but cannot be sampled within statistical distance$1-1/k-\epsilon$in time$t$. Our proof involves reducing ... more >>> TR07-004 | 12th January 2007 Lance Fortnow, Rahul Santhanam #### Time Hierarchies: A Survey We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes. more >>> TR05-144 | 5th December 2005 Lance Fortnow, Luis Antunes #### Time-Bounded Universal Distributions We show that under a reasonable hardness assumptions, the time-bounded Kolmogorov distribution is a universal samplable distribution. Under the same assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all P-samplable distributions. more >>> TR10-147 | 22nd September 2010 Dieter van Melkebeek, Thomas Watson #### Time-Space Efficient Simulations of Quantum Computations Revisions: 1 We give two time- and space-efficient simulations of quantum computations with intermediate measurements, one by classical randomized computations with unbounded error and the other by quantum computations that use an arbitrary fixed universal set of gates. Specifically, our simulations show that every language solvable by a bounded-error quantum algorithm running ... more >>> TR16-113 | 22nd July 2016 Gillat Kol, Ran Raz, Avishay Tal #### Time-Space Hardness of Learning Sparse Parities We define a concept class${\cal F}$to be time-space hard (or memory-samples hard) if any learning algorithm for${\cal F}$requires either a memory of size super-linear in$n$or a number of samples super-polynomial in$n$, where$n$is the length of one sample. A recent work shows ... more >>> TR19-071 | 14th May 2019 Sumegha Garg, Ran Raz, Avishay Tal #### Time-Space Lower Bounds for Two-Pass Learning A line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [Raz16,KRT17,Raz17,MM18,BOGY18,GRT18]. For example, any algorithm for learning parities of size$n$requires either a memory of size$\Omega(n^{2})$or an exponential number ... more >>> TR98-053 | 30th August 1998 Paul Beame, Michael Saks, Jayram S. Thathachar #### Time-Space Tradeoffs for Branching Programs Comments: 1 We obtain the first non-trivial time-space tradeoff lower bound for functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a Boolean function f that requires exponential size to be computed by any branching program of length cn, for some constant c>1. We also give the first separation result between the ... more >>> TR07-036 | 6th April 2007 Ryan Williams #### Time-Space Tradeoffs for Counting NP Solutions Modulo Integers We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for Sat. Let m be a positive integer, and define MODm-Sat to be the problem of determining if a given Boolean formula has ... more >>> TR18-114 | 6th June 2018 Paul Beame, Shayan Oveis Gharan, Xin Yang #### Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials We develop an extension of recent analytic methods for obtaining time-space tradeoff lower bounds for problems of learning from uniformly random labelled examples. With our methods we can obtain bounds for learning concept classes of finite functions from random evaluations even when the sample space of random inputs can be ... more >>> TR17-120 | 31st July 2017 Paul Beame, Shayan Oveis Gharan, Xin Yang #### Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions Revisions: 1 We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior ... more >>> TR00-028 | 17th April 2000 Lance Fortnow, Dieter van Melkebeek #### Time-Space Tradeoffs for Nondeterministic Computation We show new tradeoffs for satisfiability and nondeterministic linear time. Satisfiability cannot be solved on general purpose random-access Turing machines in time$n^{1.618}$and space$n^{o(1)}$. This improves recent results of Lipton and Viglas and Fortnow. more >>> TR12-027 | 29th March 2012 Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang #### Time-space tradeoffs for width-parameterized SAT:Algorithms and lower bounds Revisions: 2 A decade has passed since Alekhnovich and Razborov presented an algorithm that solves SAT on instances$\phi$of size$n$having tree-width$TW(\phi)$, using time (and space) bounded by$2^{O(TW(\phi))}n^{O(1)}$. Although there have been several papers over the ensuing years building on the work of Alekhnovich and Razborov there has ... more >>> TR11-149 | 4th November 2011 Paul Beame, Chris Beck, Russell Impagliazzo #### Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size$N$that have Resolution refutations of space and size each roughly$N^{\log_2 N}$(and like all formulas have Resolution refutations of space$N$) for ... more >>> TR01-041 | 23rd May 2001 Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay #### Time-Space Tradeoffs in the Counting Hierarchy We extend the lower bound techniques of [Fortnow], to the unbounded-error probabilistic model. A key step in the argument is a generalization of Nepomnjascii's theorem from the Boolean setting to the arithmetic setting. This generalization is made possible, due to the recent discovery of logspace-uniform TC^0 more >>> TR94-002 | 12th December 1994 Oded Goldreich, Avi Wigderson #### Tiny Families of Functions with Random Properties: A Quality--Size Trade--off for Hashing Revisions: 2 We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family), and the quality (or error parameter) of the pseudo-random property it achieves. Unlike previous constructions, ... more >>> TR09-118 | 18th November 2009 Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin #### Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness Revisions: 1 We study the computational power of polynomial threshold functions, that is, threshold functions of real polynomials over the boolean cube. We provide two new results bounding the computational power of this model. Our first result shows that low-degree polynomial threshold functions cannot approximate any function with many influential variables. We ... more >>> TR16-105 | 13th July 2016 Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron #### Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism Revisions: 1 The function$f\colon \{-1,1\}^n \to \{-1,1\}$is a$k$-junta if it depends on at most$k$of its variables. We consider the problem of tolerant testing of$k$-juntas, where the testing algorithm must accept any function that is$\epsilon$-close to some$k$-junta and reject any function that is$\epsilon'$-far from ... more >>> TR05-019 | 9th February 2005 Venkatesan Guruswami, Atri Rudra #### Tolerant Locally Testable Codes An error-correcting code is said to be {\em locally testable} if it has an efficient spot-checking procedure that can distinguish codewords from strings that are far from every codeword, looking at very few locations of the input in doing so. Locally testable codes (LTCs) have generated ... more >>> TR04-010 | 26th January 2004 Michal Parnas, Dana Ron, Ronitt Rubinfeld #### Tolerant Property Testing and Distance Approximation A standard property testing algorithm is required to determine with high probability whether a given object has property P or whether it is \epsilon-far from having P, for any given distance parameter \epsilon. An object is said to be \epsilon-far from having ... more >>> TR04-105 | 19th November 2004 Eldar Fischer, Lance Fortnow #### Tolerant Versus Intolerant Testing for Boolean Properties A property tester with high probability accepts inputs satisfying a given property and rejects inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We construct properties of binary functions ... more >>> TR19-166 | 20th November 2019 Guy Blanc, Jane Lange, Li-Yang Tan #### Top-down induction of decision trees: rigorous guarantees and inherent limitations Consider the following heuristic for building a decision tree for a function$f : \{0,1\}^n \to \{\pm 1\}$. Place the most influential variable$x_i$of$f$at the root, and recurse on the subfunctions$f_{x_i=0}$and$f_{x_i=1}$on the left and right subtrees respectively; terminate once the tree is an ... more >>> TR04-108 | 24th November 2004 Eric Allender, Samir Datta, Sambuddha Roy #### Topology inside NC^1 We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of ... more >>> TR14-074 | 14th May 2014 Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra #### Topology matters in communication We provide the first communication lower bounds that are sensitive to the network topology for computing natural and simple functions by point to point message passing protocols for the Number in Hand' model. All previous lower bounds were either for the broadcast model or assumed full connectivity of the network. ... more >>> TR18-076 | 22nd April 2018 Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao #### Torus polynomials: an algebraic approach to ACC lower bounds Revisions: 2 We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, ... more >>> TR14-038 | 24th March 2014 Ilario Bonacina, Nicola Galesi, Neil Thapen #### Total space in resolution Revisions: 1 We show$\Omega(n^2)$lower bounds on the total space used in resolution refutations of random$k$-CNFs over$n$variables, and of the graph pigeonhole principle and the bit pigeonhole principle for$n$holes. This answers the long-standing open problem of whether there are families of$k$-CNF formulas of size$O(n)$... more >>> TR16-057 | 11th April 2016 Ilario Bonacina #### Total space in Resolution is at least width squared Given an unsatisfiable$k$-CNF formula$\phi$we consider two complexity measures in Resolution: width and total space. The width is the minimal$W$such that there exists a Resolution refutation of$\phi$with clauses of at most$W$literals. The total space is the minimal size$T$of a memory ... more >>> TR01-070 | 24th October 2001 Robert Albin Legenstein #### Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing We introduce em total wire length as salient complexity measure for analyzing the circuit complexity of sensory processing in biological neural systems and neuromorphic engineering. The new complexity measure is applied in this paper to two basic computational problems that arise in translation- and scale-invariant pattern recognition, and hence appear ... more >>> TR09-038 | 14th April 2009 Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen #### Toward a Model for Backtracking and Dynamic Programming We propose a model called priority branching trees (pBT ) for backtracking and dynamic programming algorithms. Our model generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence spans a wide spectrum of algorithms. After witnessing the ... more >>> TR19-120 | 11th September 2019 Or Meir #### Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e.,$\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions$f ... more >>>

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

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

Revisions: 11

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

TR16-035 | 11th March 2016
Irit Dinur, Or Meir

#### Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

Revisions: 2

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected'' with respect to the composition of functions $f\circ g$. They showed that this conjecture, ... more >>>

TR15-107 | 21st June 2015

#### Towards Better Separation between Deterministic and Randomized Query Complexity

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

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

#### Towards a Characterization of Approximation Resistance for Symmetric CSPs

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

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

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

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

more >>>

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

#### Towards a Reverse Newman's Theorem in Interactive Information Complexity

Revisions: 2

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

TR17-056 | 7th April 2017

#### Towards a Unified Complexity Theory of Total Functions

Revisions: 1

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

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

#### Towards an algebraic natural proofs barrier via polynomial identity testing

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

TR11-014 | 3rd February 2011
Antoine Taveneaux

#### Towards an axiomatic system for Kolmogorov complexity

Revisions: 1

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

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

#### Towards An Optimal Query Efficient PCP?

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

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

TR08-026 | 28th February 2008

#### Towards an Optimal Separation of Space and Length in Resolution

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

TR15-097 | 16th June 2015
Marek Karpinski

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

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

TR18-036 | 21st February 2018
Michael Forbes, Sumanta Ghosh, Nitin Saxena

#### Towards blackbox identity testing of log-variate circuits

Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few ... more >>>

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

#### Towards Coding for Maximum Errors in Interactive Communication

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

TR11-064 | 23rd April 2011
Mark Braverman

#### Towards deterministic tree code constructions

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

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

#### Towards Dimension Expanders Over Finite Fields

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

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

#### Towards efficient constructions of hitting sets that derandomize BPP

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

TR06-150 | 4th December 2006
Patrick Briest

#### Towards Hardness of Envy-Free Pricing

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

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

#### Towards lower bounds on locally testable codes via density arguments

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

TR19-019 | 19th February 2019
Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi

#### Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathop{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($\Sigma\Pi\Sigma\Pi$) circuit of size at most $\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree $d = \omega(n/\log n)$, this improves upon the upper bound of $\exp\left({O(\sqrt{d}\log n)}\right)$ obtained by Tavenas (MFCS ... more >>>

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

#### Towards Optimal Deterministic Coding for Interactive Communication

Revisions: 1

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

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

TR19-179 | 7th December 2019
Avishay Tal

#### Towards Optimal Separations between Quantum and Randomized Query Complexities

Revisions: 1

The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of $O(1)$ vs. ... more >>>

TR01-009 | 5th January 2001
Ronen Shaltiel

#### Towards proving strong direct product theorems

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

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

#### Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

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

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

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

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

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

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

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

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

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

#### Tracking the best disjunction

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

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

#### Tractable Clones of Polynomials over Semigroups

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

TR02-032 | 17th April 2002
Andrei Bulatov

#### Tractable Constraint Satisfaction Problems on a 3-element set

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

TR19-160 | 10th November 2019
Md Lutfar Rahman, Thomas Watson

#### Tractable Unordered 3-CNF Games

The classic TQBF problem can be viewed as a game in which two players alternate turns assigning truth values to a CNF formula's variables in a prescribed order, and the winner is determined by whether the CNF gets satisfied. The complexity of deciding which player has a winning strategy in ... more >>>

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

#### Trading Determinism for Time in Space Bounded Computations

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

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

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

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

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

#### Trading information complexity for error

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

TR15-089 | 31st May 2015

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

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

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

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

Revisions: 1

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

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

#### Transitive-Closure Spanners of the Hypercube and the Hypergrid

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

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

#### Trapdoors for Hard Lattices and New Cryptographic Constructions

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

TR16-027 | 10th February 2016

#### Tribes Is Hard in the Message Passing Model

Revisions: 1

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

TR16-123 | 11th August 2016
Stasys Jukna

#### Tropical Complexity, Sidon Sets, and Dynamic Programming

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

TR05-123 | 25th October 2005
Olaf Beyersdorff

#### Tuples of Disjoint NP-Sets

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

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

TR11-047 | 8th April 2011
Oded Goldreich

#### Two Comments on Targeted Canonical Derandomizers

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

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

#### Two Query PCP with Sub-Constant Error

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

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

#### Two Sides of the Coin Problem

Revisions: 1

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

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

#### Two Structural Results for Low Degree Polynomials and Applications

Revisions: 1

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

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

#### Two Theorems in List Decoding

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

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

TR04-078 | 3rd August 2004
Henning Fernau

#### Two-Layer Planarization: Improving on Parameterized Algorithmics

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

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

#### Two-Sided Error Proximity Oblivious Testing

Revisions: 4

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

TR05-017 | 28th January 2005
Phong Nguyen

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

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

TR18-066 | 8th April 2018
Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma

In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error $\varepsilon$ for $n$-bit sources having min-entropy $poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is $poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a $poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any $k ... more >>> TR15-095 | 14th June 2015 Gil Cohen #### Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of$2\log{n}$-Ramsey graphs on$n$vertices. Matching Erdös' result with a constructive proof is a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in ... more >>> TR16-114 | 30th July 2016 Gil Cohen #### Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols Revisions: 1 This paper offers the following contributions: * We construct a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent$n$-bit sources with min-entropy$\widetilde{O}(\log{n})$. Our construction is optimal up to$\mathrm{poly}(\log\log{n})$factors and improves upon a recent result by Ben-Aroya, Doron, and Ta-Shma (ECCC'16) that can handle ... more >>> TR11-035 | 4th March 2011 Christoph Behle, Andreas Krebs, Stephanie Reifferscheid #### Typed Monoids -- An Eilenberg-like Theorem for non regular Languages Based on different concepts to obtain a finer notion of language recognition via finite monoids we develop an algebraic structure called typed monoid. This leads to an algebraic description of regular and non regular languages. We obtain for each language a unique minimal recognizing typed monoid, the typed syntactic monoid. more >>> TR03-007 | 15th January 2003 Olivier Dubois, Yacine Boufkhad, Jacques Mandler #### Typical random 3-SAT formulae and the satisfiability threshold$k\$-SAT is one of the best known among a wide class of random
constraint satisfaction problems believed to exhibit a threshold
phenomenon where the control parameter is the ratio, number of
constraints to number of variables. There has been a large amount of
work towards estimating ... more >>>

ISSN 1433-8092 | Imprint