Under the auspices of the Computational Complexity Foundation (CCF)

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

A
TR11-028 | 24th February 2011
Richard Beigel, Bin Fu

#### A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing

The bin packing problem is to find the minimum
number of bins of size one to pack a list of items with sizes
$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects
a random element from the input list each time, we develop a
N)$deterministic lower bound fails ... more >>> TR94-027 | 12th December 1994 Stasys Jukna #### A Note on Read-k Times Branching Programs A syntactic read-k times branching program has the restriction that no variable occurs more than k times on any path (whether or not consistent). We exhibit an explicit Boolean function f which cannot be computed by nondeterministic syntactic read-k times branching programs of size less than exp(\sqrt{n}}k^{-2k}), ... more >>> TR95-009 | 2nd February 1995 Matthias Krause #### A note on realizing iterated multiplication by small depth threshold circuits It is shown that decomposition via Chinise Remainder does not yield polynomial size depth 3 threshold circuits for iterated multiplication of n-bit numbers. This result is achieved by proving that, in contrast to multiplication of two n-bit numbers, powering, division, and other related problems, the ... more >>> TR13-128 | 16th September 2013 Pavel Hrubes #### A note on semantic cutting planes We show that the semantic cutting planes proof system has feasible interpolation via monotone real circuits. This gives an exponential lower bound on proof length in the system. We also pose the following problem: can every multivariate non-decreasing function be expressed as a composition of non-decreasing functions in two ... more >>> TR07-105 | 21st September 2007 Jelani Nelson #### A Note on Set Cover Inapproximability Independent of Universe Size Revisions: 1 In the set cover problem we are given a collection of$m$sets whose union covers$[n] = \{1,\ldots,n\}$and must find a minimum-sized subcollection whose union still covers$[n]$. We investigate the approximability of set cover by an approximation ratio that depends only on$m$and observe that, for ... more >>> TR01-029 | 27th March 2001 Denis Xavier Charles #### A Note on Subgroup Membership Problem for PSL(2,p). Comments: 1 We show that there are infinitely many primes$p$, such that the subgroup membership problem for PSL(2,p) belongs to$\NP \cap \coNP$. more >>> TR12-095 | 23rd July 2012 Avraham Ben-Aroya, Igor Shinkar #### A Note on Subspace Evasive Sets A subspace-evasive set over a field${\mathbb F}$is a subset of${\mathbb F}^n$that has small intersection with any low-dimensional affine subspace of${\mathbb F}^n$. Interest in subspace evasive sets began in the work of Pudlák and Rödl (Quaderni di Matematica 2004). More recently, Guruswami (CCC 2011) showed that ... more >>> TR16-065 | 18th April 2016 Xi Chen, Yu Cheng, Bo Tang #### A Note on Teaching for VC Classes Revisions: 1 In this note, we study the recursive teaching dimension(RTD) of concept classes of low VC-dimension. Recall that the VC-dimension of$C \subseteq \{0,1\}^n$, denoted by$VCD(C)$, is the maximum size of a shattered subset of$[n]$, where$Y\subseteq [n]$is shattered if for every binary string$\vec{b}$of length$|Y|$, ... more >>> TR05-130 | 31st October 2005 Ahuva Mu'alem #### A Note on Testing Truthfulness This work initiates the study of algorithms for the testing of monotonicity of mechanisms. Such testing algorithms are useful for searching dominant strategy mechanisms. An$\e$-tester for monotonicity is given a query access to a mechanism, accepts if monotonicity is satisfied, and rejects with high probability if more than$\e$-fraction more >>> TR04-056 | 1st July 2004 Vinodchandran Variyam #### A note on the circuit complexity of PP In this short note we show that for any integer k, there are languages in the complexity class PP that do not have Boolean circuits of size$n^k$. more >>> TR13-069 | 1st May 2013 Kousha Etessami, Alistair Stewart, Mihalis Yannakakis #### A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in product-of-exponentials notation, or equivalently, via arithmetic circuits using only multiplication and division gates, and integer inputs: Input instance: four lists of positive integers:$a_1, \ldots , a_n; \ b_1, \ldots ,b_n; \ ... more >>>

TR01-092 | 2nd October 2001
Till Tantau

#### A Note on the Complexity of the Reachability Problem for Tournaments

Deciding whether a vertex in a graph is reachable from another
vertex has been studied intensively in complexity theory and is
well understood. For common types of graphs like directed graphs,
undirected graphs, dags or trees it takes a (possibly
nondeterministic) logspace machine to decide the reachability
problem, and ... more >>>

TR06-076 | 4th May 2006
Noam Nisan

#### A Note on the computational hardness of evolutionary stable strategies

We present a very simple reduction that when given a graph G and an integer k produces a game that has an evolutionary stable strategy if and only if the maximum clique size of G is not exactly k. Formally this shows that existence of evolutionary stable strategies is hard ... more >>>

TR08-012 | 20th November 2007
Arnab Bhattacharyya

#### A Note on the Distance to Monotonicity of Boolean Functions

Given a boolean function, let epsilon_M(f) denote the smallest distance between f and a monotone function on {0,1}^n. Let delta_M(f) denote the fraction of hypercube edges where f violates monotonicity. We give an alternative proof of the tight bound: delta_M(f) >= 2/n eps_M(f) for any boolean function f. This was ... more >>>

TR00-088 | 28th November 2000
Meena Mahajan, V Vinay

#### A note on the hardness of the characteristic polynomial

In this note, we consider the problem of computing the
coefficients of the characteristic polynomial of a given
matrix, and the related problem of verifying the
coefficents.

Santha and Tan [CC98] show that verifying the determinant
(the constant term in the characteristic polynomial) is
complete for the class C=L, ... more >>>

TR12-092 | 6th July 2012
Pavol Duris

#### A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata.

In this paper we deal with one-way multi-head data-independent finite automata. A $k$-head finite automaton $A$ is data-independent, if the position of every head $i$ after step $t$ in the computation on an input $w$ is a function that depends only on the length of the input $w$, on $i$ ... more >>>

TR17-187 | 3rd December 2017
Roei Tell

#### A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization

The quantified derandomization problem of a circuit class $\mathcal{C}$ with a function $B:\mathbb{N}\rightarrow\mathbb{N}$ is the following: Given an input circuit $C\in\mathcal{C}$ over $n$ bits, deterministically distinguish between the case that $C$ accepts all but $B(n)$ of its inputs and the case that $C$ rejects all but $B(n)$ of its inputs. ... more >>>

TR01-058 | 28th August 2001
Stasys Jukna

#### A Note on the Minimum Number of Negations Leading to Superpolynomial Savings

In 1957 Markov proved that every circuit in $n$ variables
can be simulated by a circuit with at most $\log(n+1)$ negations.
In 1974 Fischer has shown that this can be done with only
polynomial increase in size.

In this note we observe that some explicit monotone functions ... more >>>

TR04-062 | 28th July 2004
Stasys Jukna

#### A note on the P versus NP intersected with co-NP question in communication complexity

We consider the P versus NP\cap coNP question for the classical two-party communication protocols: if both a boolean function and its negation have small nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and ... more >>>

TR02-004 | 2nd November 2001
Till Tantau

#### A Note on the Power of Extra Queries to Membership Comparable Sets

A language is called k-membership comparable if there exists a
polynomial-time algorithm that excludes for any k words one of
the 2^k possibilities for their characteristic string.
It is known that all membership comparable languages can be
reduced to some P-selective language with polynomially many
adaptive queries. We show however ... more >>>

TR12-121 | 25th September 2012
Pavel Hrubes

#### A note on the real $\tau$-conjecture and the distribution of roots

Revisions: 2

Koiran's real $\tau$-conjecture asserts that if a non-zero real polynomial can be written as $f=\sum_{i=1}^{p}\prod_{j=1}^{q}f_{ij},$
where each $f_{ij}$ contains at most $k$ monomials, then the number of distinct real roots of $f$ is polynomial in $pqk$. We show that the conjecture implies quite a strong property of the ... more >>>

TR19-105 | 16th August 2019
Ragesh Jaiswal

#### A note on the relation between XOR and Selective XOR Lemmas

Given an unpredictable Boolean function $f: \{0, 1\}^n \rightarrow \{0, 1\}$, the standard Yao's XOR lemma is a statement about the unpredictability of computing $\oplus_{i \in [k]}f(x_i)$ given $x_1, ..., x_k \in \{0, 1\}^n$, whereas the Selective XOR lemma is a statement about the unpredictability of computing $\oplus_{i \in S}f(x_i)$ ... more >>>

TR98-042 | 27th July 1998
Pavel Pudlak

#### A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits

We consider computations of linear forms over {\bf R} by
circuits with linear gates where the absolute values
coefficients are bounded by a constant. Also we consider a
related concept of restricted rigidity of a matrix. We prove
some lower bounds on the size of such circuits and the
more >>>

TR16-032 | 10th March 2016
Roei Tell

#### A Note on Tolerant Testing with One-Sided Error

A tolerant tester with one-sided error for a property is a tester that accepts every input that is close to the property, with probability 1, and rejects every input that is far from the property, with positive probability. In this note we show that such testers require a linear number ... more >>>

TR04-118 | 21st December 2004
Marek Karpinski, Yakov Nekrich

#### A Note on Traversing Skew Merkle Trees

We consider the problem of traversing skew (unbalanced) Merkle
trees and design an algorithm for traversing a skew Merkle tree
in time O(log n/log t) and space O(log n (t/log t)), for any choice
of parameter t\geq 2.
This algorithm can be of special interest in situations when
more >>>

TR96-023 | 21st March 1996
Eric Allender

#### A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

A very recent paper by Caussinus, McKenzie, Therien, and Vollmer
[CMTV] shows that ACC^0 is properly contained in ModPH, and TC^0
is properly contained in the counting hierarchy. Thus, [CMTV] shows
that there are problems in ModPH that require superpolynomial-size
uniform ACC^0 ... more >>>

TR07-016 | 13th February 2007

#### A Note on Yekhanin's Locally Decodable Codes

Revisions: 1

Locally Decodable codes(LDC) support decoding of any particular symbol of the input message by reading constant number of symbols of the codeword, even in presence of constant fraction of errors.

In a recent breakthrough, Yekhanin designed $3$-query LDCs that hugely improve over earlier constructions. Specifically, for a Mersenne prime $p ... more >>> TR16-060 | 15th April 2016 Henry Yuen #### A parallel repetition theorem for all entangled games The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Raz's classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known. ... more >>> TR09-027 | 2nd April 2009 Iftach Haitner #### A Parallel Repetition Theorem for Any Interactive Argument Revisions: 1 The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, ... more >>> TR10-019 | 19th February 2010 Andrew Drucker #### A PCP Characterization of AM We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class$\mathsf{AM}$. This gives a PCP characterization' of$\mathsf{AM}$analogous to the PCP Theorem for$\mathsf{NP}$. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, ... more >>> TR14-084 | 12th June 2014 Luke Schaeffer #### A Physically Universal Cellular Automaton Several cellular automata (CA) are known to be universal in the sense that one can simulate arbitrary computations (e.g., circuits or Turing machines) by carefully encoding the computational device and its input into the cells of the CA. In this paper, we consider a different kind of universality proposed by ... more >>> TR17-026 | 17th February 2017 Valentine Kabanets, Daniel Kane, Zhenjian Lu #### A Polynomial Restriction Lemma with Applications A polynomial threshold function (PTF) of degree$d$is a boolean function of the form$f=\mathrm{sgn}(p)$, where$p$is a degree-$d$polynomial, and$\mathrm{sgn}$is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is ... more >>> TR00-064 | 29th August 2000 Klaus Jansen, Marek Karpinski, Andrzej Lingas #### A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs The Max-Bisection and Min-Bisection are the problems of finding partitions of the vertices of a given graph into two equal size subsets so as to maximize or minimize, respectively, the number of edges with exactly one endpoint in each subset. In this paper we design the first ... more >>> TR02-041 | 2nd July 2002 Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon #### A Polynomial Time Approximation Scheme for Metric MIN-BISECTION We design a polynomial time approximation scheme (PTAS) for the problem of Metric MIN-BISECTION of dividing a given finite metric space into two halves so as to minimize the sum of distances across that partition. The method of solution depends on a new metric placement partitioning ... more >>> TR02-044 | 16th July 2002 Wenceslas Fernandez de la Vega, Marek Karpinski #### A Polynomial Time Approximation Scheme for Subdense MAX-CUT We prove that the subdense instances of MAX-CUT of average degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS). We extend this result also to show that the instances of general 2-ary maximum constraint satisfaction problems (MAX-CSP) of the same average density have PTASs. Our results ... more >>> TR10-088 | 17th May 2010 Jiri Sima, Stanislav Zak #### A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3 Revisions: 2 , Comments: 3 The relationship between deterministic and probabilistic computations is one of the central issues in complexity theory. This problem can be tackled by constructing polynomial time hitting set generators which, however, belongs to the hardest problems in computer science even for severely restricted computational models. In our work, we consider read-once ... more >>> TR04-038 | 27th April 2004 John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann #### A Polynomial Time Learner for a Subclass of Regular Patterns Presented is an algorithm (for learning a subclass of erasing regular pattern languages) which can be made to run with arbitrarily high probability of success on extended regular languages generated by patterns$\pi$of the form$x_0 \alpha_1 x_1 ... \alpha_m x_m$for unknown$m$but known$c$, more >>> TR00-079 | 12th September 2000 Mark Jerrum, Eric Vigoda #### A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries We present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries. more >>> TR09-078 | 16th September 2009 Falk Unger #### A Probabilistic Inequality with Applications to Threshold Direct-product Theorems We prove a simple concentration inequality, which is an extension of the Chernoff bound and Hoeffding's inequality for binary random variables. Instead of assuming independence of the variables we use a slightly weaker condition, namely bounds on the co-moments. This inequality allows us to simplify and strengthen several known ... more >>> TR98-051 | 20th July 1998 Petr Savicky #### A probabilistic nonequivalence test for syntactic (1,+k)-branching programs Branching programs are a model for representing Boolean functions. For general branching programs, the satisfiability and nonequivalence tests are NP-complete. For read-once branching programs, which can test each variable at most once in each computation, the satisfiability test is trivial and there is also a probabilistic polynomial time test ... more >>> TR05-103 | 17th August 2005 Leonid Gurvits #### A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification Consider a homogeneous polynomial$p(z_1,...,z_n)$of degree$n$in$n$complex variables . Assume that this polynomial satisfies the property : \\$|p(z_1,...,z_n)| \geq \prod_{1 \leq i \leq n} Re(z_i)$on the domain$\{(z_1,...,z_n) : Re(z_i) \geq 0 , 1 \leq i \leq n \}$. \\ We prove that ... more >>> TR18-047 | 7th March 2018 Shachar Lovett #### A proof of the GM-MDS conjecture Revisions: 1 The GM-MDS conjecture of Dau et al. (ISIT 2014) speculates that the MDS condition, which guarantees the existence of MDS matrices with a prescribed set of zeros over large fields, is in fact sufficient for existence of such matrices over small fields. We prove this conjecture. more >>> TR04-063 | 23rd July 2004 Yehuda Lindell, Benny Pinkas #### A Proof of Yao's Protocol for Secure Two-Party Computation Revisions: 1 In the mid 1980's, Yao presented a constant-round protocol for securely computing any two-party functionality in the presence of semi-honest adversaries (FOCS 1986). In this paper, we provide a complete description of Yao's protocol, along with a rigorous proof of security. Despite the importance of Yao's protocol to the field ... more >>> TR17-163 | 2nd November 2017 Michael Forbes, Amir Shpilka #### A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits In this paper we study the complexity of constructing a hitting set for$\overline{VP}$, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given ... more >>> TR96-065 | 13th December 1996 Miklos Ajtai, Cynthia Dwork #### A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence Revisions: 1 , Comments: 1 We present a probabilistic public key cryptosystem which is secure unless the following worst-case lattice problem can be solved in polynomial time: "Find the shortest nonzero vector in an n dimensional lattice L where the shortest vector v is unique in the sense that any other vector whose ... more >>> TR19-170 | 27th November 2019 Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk #### A Quadratic Lower Bound for Algebraic Branching Programs We show that any Algebraic Branching Program (ABP) computing the polynomial$\sum_{i = 1}^n x_i^n$has at least$\Omega(n^2)$vertices. This improves upon the lower bound of$\Omega(n\log n)$, which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results by Kumar [Kum19], which showed ... more >>> TR17-028 | 17th February 2017 Mrinal Kumar #### A quadratic lower bound for homogeneous algebraic branching programs Revisions: 1 An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex$s$, and end vertex$t$and each edge having a weight which is an affine form in$\F[x_1, x_2, \ldots, x_n]$. An ABP computes a polynomial in a natural way, as the sum of weights of ... more >>> TR03-086 | 1st December 2003 Amos Beimel, Tal Malkin #### A Quantitative Approach to Reductions in Secure Computation Secure computation is one of the most fundamental cryptographic tasks. It is known that all functions can be computed securely in the information theoretic setting, given access to a black box for some complete function such as AND. However, without such a black box, not all functions can be securely ... more >>> TR19-061 | 16th April 2019 Scott Aaronson, Daniel Grier, Luke Schaeffer #### A Quantum Query Complexity Trichotomy for Regular Languages We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity$\Theta(1)$,$\tilde{\Theta}(\sqrt n)$, or$\Theta(n)$. The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we ... more >>> TR08-017 | 16th December 2007 Thomas Watson, Dieter van Melkebeek #### A Quantum Time-Space Lower Bound for the Counting Hierarchy We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy, respectively. We prove that for every real$d$and every positive real$\epsilon$... more >>> TR18-128 | 11th July 2018 Ewin Tang #### A quantum-inspired classical algorithm for recommendation systems Revisions: 3 A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an$m\times n$matrix of small rank$k$. We give the first classical algorithm to produce a recommendation in$O(\text{poly}(k)\text{polylog}(m,n))$time, which is an exponential improvement on previous ... more >>> TR09-074 | 10th September 2009 Suguru Tamaki, Yuichi Yoshida #### A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness Long Code testing is a fundamental problem in the area of property testing and hardness of approximation. Long Code is a function of the form$f(x)=x_i$for some index$i$. In the Long Code testing, the problem is, given oracle access to a collection of Boolean functions, to decide whether ... more >>> TR05-156 | 13th December 2005 Jonathan A. Kelner, Daniel A. Spielman #### A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version) We present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input. We begin by reducing the input linear program to a special form in which we ... more >>> TR05-107 | 28th September 2005 Avi Wigderson, David Xiao #### A Randomness-Efficient Sampler for Matrix-valued Functions and Applications Revisions: 1 In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter, in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is ... more >>> TR12-124 | 29th September 2012 Massimo Lauria #### A rank lower bound for cutting planes proofs of Ramsey Theorem Ramsey Theorem is a cornerstone of combinatorics and logic. In its simplest formulation it says that there is a function$r$such that any simple graph with$r(k,s)$vertices contains either a clique of size$k$or an independent set of size$s$. We study the complexity of proving upper ... more >>> TR05-035 | 24th March 2005 Christian Glaßer, Stephen Travers, Klaus W. Wagner #### A Reducibility that Corresponds to Unbalanced Leaf-Language Classes We introduce the polynomial-time tree reducibility (ptt-reducibility). Our main result states that for languages$B$and$C$it holds that$B$ptt-reduces to$C$if and only if the unbalanced leaf-language class of$B$is robustly contained in the unbalanced leaf-language class of$C$. ... more >>> TR17-027 | 16th February 2017 Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma #### A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate Revisions: 1 We show a reduction from the existence of explicit t-non-malleable extractors with a small seed length, to the construction of explicit two-source extractors with small error for sources with arbitrarily small constant rate. Previously, such a reduction was known either when one source had entropy rate above half [Raz05] or ... more >>> TR13-156 | 15th November 2013 Jan Krajicek #### A reduction of proof complexity to computational complexity for$AC^0[p]$Frege systems Revisions: 2 We give a general reduction of lengths-of-proofs lower bounds for constant depth Frege systems in DeMorgan language augmented by a connective counting modulo a prime$p$(the so called$AC^0[p]$Frege systems) to computational complexity lower bounds for search tasks involving search trees branching upon values of linear maps on ... more >>> TR04-006 | 6th January 2004 Günter Hotz #### A remark on nondecidabilities of the initial value problem of ODEs We prove that it is not decidable on R-machines if for a fixed finite intervall [a,b) the solution of the initial value problems of systems of ordinary differetial equations have solutions over this interval. This result holds independly from assumptions about differentiability of the right sides of the ODEs. Futhermore ... more >>> TR12-005 | 13th January 2012 Periklis Papakonstantinou, Guang Yang #### A remark on one-wayness versus pseudorandomness Every pseudorandom generator is in particular a one-way function. If we only consider part of the output of the pseudorandom generator is this still one-way? Here is a general setting formalizing this question. Suppose$G:\{0,1\}^n\rightarrow \{0,1\}^{\ell(n)}$is a pseudorandom generator with stretch$\ell(n)> n$. Let$M_R\in\{0,1\}^{m(n)\times \ell(n)}$be a linear ... more >>> TR97-020 | 15th May 1997 Oded Goldreich #### A Sample of Samplers -- A Computational Perspective on Sampling (survey). We consider the problem of estimating the average of a huge set of values. That is, given oracle access to an arbitrary function$f:\{0,1\}^n\mapsto[0,1]$, we need to estimate$2^{-n} \sum_{x\in\{0,1\}^n} f(x)$upto an additive error of$\epsilon$. We are allowed to employ a randomized algorithm which may ... more >>> TR17-166 | 3rd November 2017 Emanuele Viola #### A sampling lower bound for permutations A map$f:[n]^{\ell}\to[n]^{n}$has locality$d$if each output symbol in$[n]=\{1,2,\ldots,n\}$depends only on$d$of the$\ell$input symbols in$[n]$. We show that the output distribution of a$d$-local map has statistical distance at least$1-2\cdot\exp(-n/\log^{c^{d}}n)$from a uniform permutation of$[n]$. This seems to be the ... more >>> TR12-071 | 29th May 2012 Kazuhisa Seto, Suguru Tamaki #### A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis. For formulas of size at most$cn$, our algorithm runs in time$2^{(1-\mu_c)n}$for some constant$\mu_c>0$. As a byproduct of the running time analysis of our algorithm, we get strong ... more >>> TR16-100 | 27th June 2016 Suguru Tamaki #### A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates We consider depth 2 unbounded fan-in circuits with symmetric and linear threshold gates. We present a deterministic algorithm that, given such a circuit with$n$variables and$m$gates, counts the number of satisfying assignments in time$2^{n-\Omega\left(\left(\frac{n}{\sqrt{m} \cdot \poly(\log n)}\right)^a\right)}$for some constant$a>0$. Our algorithm runs in time ... more >>> TR15-136 | 28th July 2015 Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama #### A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom In this paper, we present a moderately exponential time algorithm for the circuit satisfiability problem of depth-2 unbounded-fan-in circuits with an arbitrary symmetric gate at the top and AND gates at the bottom. As a special case, we obtain an algorithm for the maximum satisfiability problem that runs in ... more >>> TR01-024 | 1st March 2001 Stephen Cook, Antonina Kolokolova #### A second-order system for polynomial-time reasoning based on Graedel's theorem We introduce a second-order system V_1-Horn of bounded arithmetic formalizing polynomial-time reasoning, based on Graedel's second-order Horn characterization of P. Our system has comprehension over P predicates (defined by Graedel's second-order Horn formulas), and only finitely many function symbols. Other systems of polynomial-time reasoning either ... more >>> TR16-149 | 23rd September 2016 Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev #### A security analysis of Probabilistically Checkable Proofs Comments: 1 Probabilistically Checkable Proofs (PCPs) [Babai et al. FOCS 90; Arora et al. JACM 98] can be used to construct asymptotically efficient cryptographic zero knowledge arguments of membership in any language in NEXP, with minimal communication complexity and computational effort on behalf of both prover and verifier [Babai et al. STOC ... more >>> TR00-027 | 11th April 2000 Pavol Duris, Juraj Hromkovic, Katsushi Inoue #### A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition The investigation of the computational power of randomized computations is one of the central tasks of current complexity and algorithm theory. In this paper for the first time a "strong" separation between the power of determinism, Las Vegas randomization, and nondeterminism for a compu- ting model is proved. The computing ... more >>> TR10-060 | 5th April 2010 Dmitry Gavinsky, Alexander A. Sherstov #### A Separation of NP and coNP in Multiparty Communication Complexity We prove that NP$\ne$coNP and coNP$\nsubseteq$MA in the number-on-forehead model of multiparty communication complexity for up to$k=(1-\epsilon)\log n$players, where$\epsilon>0$is any constant. Specifically, we construct a function$F:(\zoon)^k\to\zoo$with co-nondeterministic complexity$O(\log n)$and Merlin-Arthur complexity$n^{\Omega(1)}$. The problem was open for$k\geq3$. more >>> TR98-045 | 17th July 1998 Detlef Sieling #### A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs For (1,+k)-branching programs and read-k-times branching programs syntactic and nonsyntactic variants can be distinguished. The nonsyntactic variants correspond in a natural way to sequential computations with restrictions on reading the input while lower bound proofs are easier or only known for the syntactic variants. In this paper it is shown ... more >>> TR19-181 | 9th December 2019 Michal Koucky, Vojtech Rodl, Navid Talebanfard #### A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm We show that for every$r \ge 2$there exists$\epsilon_r > 0$such that any$r$-uniform hypergraph on$m$edges with bounded vertex degree has a set of at most$(\frac{1}{2} - \epsilon_r)m$edges the removal of which breaks the hypergraph into connected components with at most$m/2$edges. ... more >>> TR13-017 | 23rd January 2013 Pratik Worah #### A Short Excursion into Semi-Algebraic Hierarchies This brief survey gives a (roughly) self-contained overview of some complexity theoretic results about semi-algebraic proof systems and related hierarchies and the strong connections between them. The article is not intended to be a detailed survey on "Lift and Project" type optimization hierarchies (cf. Chlamtac and Tulsiani) or related proof ... more >>> TR13-176 | 8th December 2013 Daniel Kane, Osamu Watanabe #### A Short Implicant of CNFs with Relatively Many Satisfying Assignments Revisions: 1 , Comments: 1 Consider any Boolean function$F(X_1,\ldots,X_N)$that has more than$2^{-N^{d}}$satisfying assignments and that can be expressed by a CNF formula with at most$N^{1+e}$clauses for some$d>0$and$e>0$such that$d+e$is less than$1$(*). Then how many variables do we need to fix in order ... more >>> TR13-012 | 16th January 2013 Hasan Abasi, Nader Bshouty #### A Simple Algorithm for Undirected Hamiltonicity We develop a new algebraic technique that gives a simple randomized algorithm for the simple$k$-path problem with the same complexity$O^*(1.657^k)$as in [A. Bj\"orklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010, pp. 173--182, (2010). A. Bj\"orklund, T. Husfeldt, P. Kaski, M. Koivisto. Narrow sieves for parameterized paths and ... more >>> TR08-093 | 1st October 2008 Cristopher Moore, Alexander Russell #### A simple constant-probability RP reduction from NP to Parity P The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in$\P^\numP$relies on the fact that, under mild technical conditions on the complexity class$\mathcal{C}$, we have$\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... more >>> TR00-030 | 31st May 2000 #### A Simple Model for Neural Computation with Firing Rates and Firing Correlations A simple extension of standard neural network models is introduced that provides a model for neural computations that involve both firing rates and firing correlations. Such extension appears to be useful since it has been shown that firing correlations play a significant computational role in many biological neural systems. Standard ... more >>> TR08-081 | 11th September 2008 Alexander Razborov #### A simple proof of Bazzi's theorem In 1990, Linial and Nisan asked if any polylog-wise independent distribution fools any function in AC^0. In a recent remarkable development, Bazzi solved this problem for the case of DNF formulas. The aim of this note is to present a simplified version of his proof. more >>> TR15-080 | 7th May 2015 Noam Ta-Shma #### A simple proof of the Isolation Lemma We give a new simple proof for the Isolation Lemma, with slightly better parameters, that also gives non-trivial results even when the weight domain$m$is smaller than the number of variables$n$. more >>> TR19-131 | 11th September 2019 Lieuwe Vinkhuijzen, André Deutz #### A Simple Proof of Vyalyi's Theorem and some Generalizations In quantum computational complexity theory, the class QMA models the set of problems efficiently verifiable by a quantum computer the same way that NP models this for classical computation. Vyalyi proved that if$\text{QMA}=\text{PP}$then$\text{PH}\subseteq \text{QMA}$. In this note, we give a simple, self-contained proof of the theorem, using ... more >>> TR14-075 | 16th May 2014 Holger Dell #### A simple proof that AND-compression of NP-complete problems is hard Revisions: 3 Drucker (2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP is in NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a simple proof of this result. An AND-compression is ... more >>> TR07-114 | 28th September 2007 Jakob Nordström #### A Simplified Way of Proving Trade-off Results for Resolution We present a greatly simplified proof of the length-space trade-off result for resolution in Hertel and Pitassi (2007), and also prove a couple of other theorems in the same vein. We point out two important ingredients needed for our proofs to work, and discuss possible conclusions to be drawn regarding ... more >>> TR12-053 | 30th April 2012 Ankur Moitra #### A Singly-Exponential Time Algorithm for Computing Nonnegative Rank Here, we give an algorithm for deciding if the nonnegative rank of a matrix$M$of dimension$m \times n$is at most$r$which runs in time$(nm)^{O(r^2)}$. This is the first exact algorithm that runs in time singly-exponential in$r$. This algorithm (and earlier algorithms) are built on ... more >>> TR09-047 | 20th April 2009 Eli Ben-Sasson, Jakob Nordström #### A Space Hierarchy for k-DNF Resolution Comments: 1 The k-DNF resolution proof systems are a family of systems indexed by the integer k, where the kth member is restricted to operating with formulas in disjunctive normal form with all terms of bounded arity k (k-DNF formulas). This family was introduced in [Krajicek 2001] as an extension of the ... more >>> TR18-202 | 1st December 2018 Xinyu Wu #### A stochastic calculus approach to the oracle separation of BQP and PH After presentations of the oracle separation of BQP and PH result by Raz and Tal [ECCC TR18-107], several people (e.g. Ryan O’Donnell, James Lee, Avishay Tal) suggested that the proof may be simplified by stochastic calculus. In this short note, we describe such a simplification. more >>> TR18-088 | 24th April 2018 Ilya Volkovich #### A story of AM and Unique-SAT In the seminal work of \cite{Babai85}, Babai have introduced \emph{Arthur-Merlin Protocols} and in particular the complexity classes$MA$and$AM$as randomized extensions of the class$NP$. While it is easy to see that$NP \subseteq MA \subseteq AM$, it has been a long standing open question whether these classes ... more >>> TR10-150 | 19th September 2010 Bjørn Kjos-Hanssen #### A strong law of computationally weak subsets We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event$\mathcal A$such that if$X\in\mathcal A$then$X$has an infinite ... more >>> TR10-141 | 18th September 2010 (removed) Ran Raz #### A Strong Parallel Repetition Theorem for Projection Games on Expanders Reason: This paper has been remove on the author's behalf. Please note that TR10-142 is the corrected version. TR10-142 | 18th September 2010 Ran Raz, Ricky Rosen #### A Strong Parallel Repetition Theorem for Projection Games on Expanders The parallel repetition theorem states that for any Two Prover Game with value at most$1-\epsilon$(for$\epsilon<1/2$), the value of the game repeated$n$times in parallel is at most$(1-\epsilon^3)^{\Omega(n/s)}$, where$s$is the length of the answers of the two provers. For Projection Games, the bound on ... more >>> TR13-133 | 23rd September 2013 Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland #### A Structured View on Weighted Counting with Relations to Quantum Computation and Applications Revisions: 2 Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path and the goal is to compute the sum of the weights of all paths (instead of computing the number of accepting paths). We present a structured view on weighted counting by ... more >>> TR95-060 | 21st November 1995 Nader Bshouty #### A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries We present a$2^{\tilde O(\sqrt{n})}$time exact learning algorithm for polynomial size DNF using equivalence queries only. In particular, DNF is PAC-learnable in subexponential time under any distribution. This is the first subexponential time PAC-learning algorithm for DNF under any distribution. more >>> TR97-050 | 27th October 1997 Stanislav Zak #### A subexponential lower bound for branching programs restricted with regard to some semantic aspects Branching programs (b.p.s) or binary decision diagrams are a general graph-based model of sequential computation. The b.p.s of polynomial size are a nonuniform counterpart of LOG. Lower bounds for different kinds of restricted b.p.s are intensively investigated. The restrictions based on the number of tests of more >>> TR19-091 | 7th July 2019 Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, Vinodchandran Variyam, Osamu Watanabe #### A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses$O(n^{1/2+\epsilon})$space. A critical ingredient of their algorithm is a polynomial-time,$\tldO(\sqrt{n})$-space algorithm to compute a separator of a planar graph. The conference version provided a sketch ... more >>> TR15-108 | 30th June 2015 Shalev Ben-David #### A Super-Grover Separation Between Randomized and Quantum Query Complexities We construct a total Boolean function$f$satisfying$R(f)=\tilde{\Omega}(Q(f)^{5/2})$, refuting the long-standing conjecture that$R(f)=O(Q(f)^2)$for all total Boolean functions. Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions, we improve this to$R(f)=\tilde{\Omega}(Q(f)^3)$. Our construction is motivated by the Göös-Pitassi-Watson function but does not ... more >>> TR13-091 | 17th June 2013 Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi #### A super-polynomial lower bound for regular arithmetic formulas. We consider arithmetic formulas consisting of alternating layers of addition$(+)$and multiplication$(\times)$gates such that the fanin of all the gates in any fixed layer is the same. Such a formula$\Phi$which additionally has the property that its formal/syntactic degree is at most twice the (total) degree ... more >>> TR17-001 | 6th January 2017 Stephen Cook, Bruce Kapron #### A Survey of Classes of Primitive Recursive Functions This paper is a transcription of mimeographed course notes titled A Survey of Classes of Primitive Recursive Functions", by S.A. Cook, for the University of California Berkeley course Math 290, Sect. 14, January 1967. The notes present a survey of subrecursive function classes (and classes of relations based on these ... more >>> TR07-099 | 30th September 2007 Dieter van Melkebeek #### A Survey of Lower Bounds for Satisfiability and Related Problems Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time, logarithmic-space algorithm for satisfiability was not ruled out. In 1997 Fortnow, building on earlier work by ... more >>> TR15-063 | 15th April 2015 Clement Canonne #### A Survey on Distribution Testing: Your Data is Big. But is it Blue? Revisions: 1 The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offspring, distribution testing. This subfield, at the junction of property testing and Statistics, ... more >>> TR12-051 | 25th April 2012 Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan #### A Tail Bound for Read-k Families of Functions We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables$Y_1,\ldots,Y_r$are arbitrary Boolean functions of independent random variables$X_1,\ldots,X_m$, modulo a restriction that every$X_i$influences at most$k$of the variables$Y_1,\ldots,Y_r$. more >>> TR10-145 | 21st September 2010 Ron Rothblum #### A Taxonomy of Enhanced Trapdoor Permutations Trapdoor permutations (TDPs) are among the most widely studied building blocks of cryptography. Despite the extensive body of work that has been dedicated to their study, in many setting and applications (enhanced) trapdoor permutations behave unexpectedly. In particular, a TDP may become easy to invert when the inverter is given ... more >>> TR09-075 | 17th September 2009 Oded Goldreich, Brendan Juba, Madhu Sudan #### A Theory of Goal-Oriented Communication Revisions: 1 , Comments: 1 We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this ... more >>> TR98-034 | 23rd June 1998 Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan #### A tight characterization of NP with 3 query PCPs It is known that there exists a PCP characterization of NP where the verifier makes 3 queries and has a {\em one-sided} error that is bounded away from 1; and also that 2 queries do not suffice for such a characterization. Thus PCPs with 3 ... more >>> TR18-119 | 21st June 2018 YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang #### A Tight Lower Bound for Entropy Flattening Revisions: 1 We study \emph{entropy flattening}: Given a circuit$\mathcal{C}_X$implicitly describing an$n$-bit source$X$(namely,$X$is the output of$\mathcal{C}_X$on a uniform random input), construct another circuit$\mathcal{C}_Y$describing a source$Y$such that (1) source$Y$is nearly \emph{flat} (uniform on its support), and (2) the Shannon ... more >>> TR14-027 | 21st February 2014 Andris Ambainis, Krisjanis Prusis #### A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity Revisions: 1 Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy, is whether sensitivity and block sensitivity are polynomially related. Motivated by the constructions of functions which achieve the largest known separations, we study the relation between 1-certificate complexity ... more >>> TR19-049 | 2nd April 2019 Itay Berman, Iftach Haitner, Eliad Tsfadia #### A Tight Parallel-Repetition Theorem for Random-Terminating Interactive Arguments Revisions: 1 Parallel repetition is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols and public-coin protocols. However, it does not do so in the general case. Haitner [FOCS '09, SiCOMP '13] presented a simple method for transforming any interactive argument$\pi$into a slightly modified ... more >>> TR11-086 | 2nd June 2011 Masaki Yamamoto #### A tighter lower bound on the circuit size of the hardest Boolean functions In [IPL2005], Frandsen and Miltersen improved bounds on the circuit size$L(n)$of the hardest Boolean function on$n$input bits: for some constant$c>0$: $\left(1+\frac{\log n}{n}-\frac{c}{n}\right) \frac{2^n}{n} \leq L(n) \leq \left(1+3\frac{\log n}{n}+\frac{c}{n}\right) \frac{2^n}{n}.$ In this note, we announce a modest ... more >>> TR17-020 | 12th February 2017 Ran Raz #### A Time-Space Lower Bound for a Large Class of Learning Problems We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples. Our result is stated in terms of the norm ... more >>> TR04-073 | 9th July 2004 Henning Fernau #### A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set In this paper, we show how to systematically improve on parameterized algorithms and their analysis, focusing on search-tree based algorithms for d-Hitting Set, especially for d=3. We concentrate on algorithms which are easy to implement, in contrast with the highly sophisticated algorithms which have been elsewhere designed to ... more >>> TR14-137 | 24th October 2014 Neil Thapen #### A trade-off between length and width in resolution We describe a family of CNF formulas in$n$variables, with small initial width, which have polynomial length resolution refutations. By a result of Ben-Sasson and Wigderson it follows that they must also have narrow resolution refutations, of width$O(\sqrt {n \log n})$. We show that, for our formulas, this ... more >>> TR03-075 | 7th September 2003 Agostino Capponi #### A tutorial on the Deterministic two-party Communication Complexity Communication complexity is concerned with the question: how much information do the participants of a communication system need to exchange in order to perform certain tasks? The minimum number of bits that must be communicated is the deterministic communication complexity of$f$. This complexity measure was introduced by Yao \cite{1} ... more >>> TR01-016 | 22nd December 2000 Ran Canetti #### A unified framework for analyzing security of protocols Revisions: 6 Building on known definitions, we present a unified general framework for defining and analyzing security of cryptographic protocols. The framework allows specifying the security requirements of a large number of cryptographic tasks, such as signature, encryption, authentication, key exchange, commitment, oblivious transfer, zero-knowledge, secret sharing, general function evaluation, and ... more >>> TR10-161 | 25th October 2010 Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira #### A Unified Framework for Testing Linear-Invariant Properties The study of the interplay between the testability of properties of Boolean functions and the invariances acting on their domain which preserve the property was initiated by Kaufman and Sudan (STOC 2008). Invariance with respect to F_2-linear transformations is arguably the most common symmetry exhibited by natural properties of Boolean ... more >>> TR16-186 | 19th November 2016 Jayadev Acharya, Hirakendu Das, Alon Orlitsky, Ananda Theertha Suresh #### A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation The advent of data science has spurred interest in estimating properties of discrete distributions over large alphabets. Fundamental symmetric properties such as support size, support coverage, entropy, and proximity to uniformity, received most attention, with each property estimated using a different technique and often intricate analysis tools. Motivated by the ... more >>> TR17-019 | 8th February 2017 Andreas Krebs, Nutan Limaye, Michael Ludwig #### A Unified Method for Placing Problems in Polylogarithmic Depth Revisions: 2 In this work we consider the term evaluation problem which involves, given a term over some algebra and a valid input to the term, computing the value of the term on that input. This is a classical problem studied under many names such as formula evaluation problem, formula value problem ... more >>> TR13-101 | 12th July 2013 Colin Jia Zheng, Salil Vadhan #### A Uniform Min-Max Theorem with Applications in Cryptography Revisions: 2 We present a new, more constructive proof of von Neumann's Min-Max Theorem for two-player zero-sum game --- specifically, an algorithm that builds a near-optimal mixed strategy for the second player from several best-responses of the second player to mixed strategies of the first player. The algorithm extends previous work of ... more >>> TR14-103 | 8th August 2014 Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Lucier Brendan, Vasilis Syrgkanis #### A Unifying Hierarchy of Valuations with Complements and Substitutes We introduce a new hierarchy over monotone set functions, that we refer to as$MPH$(Maximum over Positive Hypergraphs). Levels of the hierarchy correspond to the degree of complementarity in a given function. The highest level of the hierarchy,$MPH$-$m$(where$m$is the total number of items) captures all ... more >>> TR05-078 | 25th May 2005 Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz #### A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme Revisions: 1 In this paper, firstly we propose two new concepts concerning the notion of key escrow encryption schemes: provable partiality and independency. Roughly speaking we say that a scheme has provable partiality if existing polynomial time algorithm for recovering the secret knowing escrowed information implies a polynomial time algorithm that can ... more >>> TR02-033 | 11th June 2002 Beate Bollig #### A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. A very simple function$f$in$n^2$variables is exhibited such that both the function$f$and its negation$\neg f$can be computed by$\Sigma^3_p$-circuits, the ... more >>> TR17-057 | 7th April 2017 Alessandro Chiesa, Michael Forbes, Nicholas Spooner #### A Zero Knowledge Sumcheck and its Applications Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure. In this work, we develop algebraic techniques for ... more >>> TR17-139 | 18th September 2017 Thomas Watson #### A ZPP^NP[1] Lifting Theorem The complexity class ZPP^NP[1] (corresponding to zero-error randomized algorithms with access to one NP oracle query) is known to have a number of curious properties. We further explore this class in the settings of time complexity, query complexity, and communication complexity. For starters, we provide a new characterization: ZPP^NP[1] equals ... more >>> TR13-029 | 19th February 2013 C. Seshadhri, Deeparnab Chakrabarty #### A {\huge${o(n)}$} monotonicity tester for Boolean functions over the hypercube Revisions: 1 Given oracle access to a Boolean function$f:\{0,1\}^n \mapsto \{0,1\}$, we design a randomized tester that takes as input a parameter$\eps>0$, and outputs {\sf Yes} if the function is monotone, and outputs {\sf No} with probability$>2/3$, if the function is$\eps$-far from monotone. That is,$f$needs to ... more >>> TR13-030 | 20th February 2013 Elad Haramaty, Noga Ron-Zewi, Madhu Sudan #### Absolutely Sound Testing of Lifted Codes In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of "affine-invariant'' codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes ... more >>> TR18-209 | 8th December 2018 Emanuele Viola #### AC0 unpredictability We prove that for every distribution$D$on$n$bits with Shannon entropy$\ge n-a$at most$O(2^{d}a\log^{d+1}g)/\gamma{}^{5}$of the bits$D_{i}$can be predicted with advantage$\gamma$by an AC$^{0}$circuit of size$g$and depth$d$that is a function of all the bits of$D$except$D_{i}$. ... more >>> TR19-018 | 18th February 2019 Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal #### AC0[p] Lower Bounds against MCSP via the Coin Problem Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an$n$-variate boolean function has circuit complexity less than a given parameter$s$. We prove that MCSP is hard for constant-depth circuits with mod$p$gates, for any prime$p\geq 2$(the circuit class$AC^0[p])$. Namely, ... more >>> TR11-050 | 11th April 2011 Claus-Peter Schnorr #### Accelerated Slide- and LLL-Reduction Revisions: 7 Given an LLL-basis$B$of dimension$n= hk$we accelerate slide-reduction with blocksize$k$to run under a reasonable assjmption in \$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $\ local SVP-computations in dimension$k$, where$\alpha \ge \frac 43$measures the quality of the ... more >>> TR17-085 | 4th May 2017 Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang #### Active classification with comparison queries We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a ... more >>> TR07-088 | 7th September 2007 Elad Hazan, C. Seshadhri #### Adaptive Algorithms for Online Decision Problems Revisions: 1 We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions, and ... more >>> TR18-005 | 9th January 2018 C. Seshadhri, Deeparnab Chakrabarty #### Adaptive Boolean Monotonicity Testing in Total Influence Time The problem of testing monotonicity of a Boolean function$f:\{0,1\}^n \to \{0,1\}$has received much attention recently. Denoting the proximity parameter by$\varepsilon$, the best tester is the non-adaptive$\widetilde{O}(\sqrt{n}/\varepsilon^2)$tester of Khot-Minzer-Safra (FOCS 2015). Let$I(f)$denote the total influence of$f$. We give an adaptive tester whose running ... more >>> TR06-042 | 16th March 2006 Amit Deshpande, Santosh Vempala #### Adaptive Sampling and Fast Low-Rank Matrix Approximation We prove that any real matrix$A$contains a subset of at most$4k/\eps + 2k \log(k+1)$rows whose span contains" a matrix of rank at most$k$with error only$(1+\eps)$times the error of the best rank-$k$approximation of$A$. This leads to an algorithm to find such ... more >>> TR96-051 | 1st October 1996 Richard Beigel, William Gasarch, Ming Li, Louxin Zhang #### Addition in$\log_2{n}$+ O(1)$ Steps on Average: A Simple Analysis

We demonstrate the use of Kolmogorov complexity in average case
analysis of algorithms through a classical example: adding two $n$-bit
numbers in $\ceiling{\log_2{n}}+2$ steps on average. We simplify the
analysis of Burks, Goldstine, and von Neumann in 1946 and
(in more complete forms) of Briley and of Schay.

more >>>

TR15-123 | 31st July 2015
Xi Chen, Igor Carboni Oliveira, Rocco Servedio

#### Addition is exponentially harder than counting for shallow monotone circuits

Let $U_{k,N}$ denote the Boolean function which takes as input $k$ strings of $N$ bits each, representing $k$ numbers $a^{(1)},\dots,a^{(k)}$ in $\{0,1,\dots,2^{N}-1\}$, and outputs 1 if and only if $a^{(1)} + \cdots + a^{(k)} \geq 2^N.$ Let THR$_{t,n}$ denote a monotone unweighted threshold gate, i.e., the Boolean function which takes ... more >>>

TR14-044 | 2nd April 2014
Daniel Dewey

We give evidence for a stronger version of the extended Church-Turing thesis: among the set of physically possible computers, there are computers that can simulate any other realizable computer with only additive constant overhead in space, time, and other natural resources. Complexity-theoretic results that hold for these computers can therefore ... more >>>

TR18-163 | 18th September 2018
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

#### Adventures in Monotone Complexity and TFNP

$\mathbf{Separations:}$ We introduce a monotone variant of XOR-SAT and show it has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite ... more >>>

TR11-008 | 27th January 2011
Scott Aaronson, Andrew Drucker

#### Advice Coins for Classical and Quantum Computation

We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states ... more >>>

TR11-120 | 6th September 2011
Thomas Watson

#### Advice Lower Bounds for the Dense Model Theorem

Revisions: 1

We prove a lower bound on the amount of nonuniform advice needed by black-box reductions for the Dense Model Theorem of Green, Tao, and Ziegler, and of Reingold, Trevisan, Tulsiani, and Vadhan. The latter theorem roughly says that for every distribution $D$ that is $\delta$-dense in a distribution that is ... more >>>

TR10-044 | 12th March 2010
Eli Ben-Sasson, Swastik Kopparty

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>> TR14-010 | 23rd January 2014 Jean Bourgain, Zeev Dvir, Ethan Leeman #### Affine extractors over large fields with exponential error We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions. more >>> TR11-061 | 18th April 2011 Neeraj Kayal #### Affine projections of polynomials Revisions: 1 An$m$-variate polynomial$f$is said to be an affine projection of some$n$-variate polynomial$g$if there exists an$n \times m$matrix$A$and an$n$-dimensional vector$b$such that$f(x) = g(A x + b)$. In other words, if$f$can be obtained by replacing each variable ... more >>> TR01-035 | 15th April 2001 Amir Shpilka #### Affine Projections of Symmetric Polynomials In this paper we introduce a new model for computing=20 polynomials - a depth 2 circuit with a symmetric gate at the top=20 and plus gates at the bottom, i.e the circuit computes a=20 symmetric function in linear functions -$S_{m}^{d}(\ell_1,\ell_2,...,\ell_m)$($S_{m}^{d}$is the$d$'th=20 elementary symmetric polynomial in$m$... more >>> TR16-040 | 16th March 2016 Baris Aydinlioglu, Eric Bach #### Affine Relativization: Unifying the Algebrization and Relativization Barriers Revisions: 3 We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure ... more >>> TR15-179 | 10th November 2015 Divesh Aggarwal, Kaave Hosseini, Shachar Lovett #### Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a weak" random source$X$with min-entropy$k$and a uniformly random seed$Y$of length$d$, and outputs a string of length close ... more >>> TR15-009 | 16th January 2015 Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan #### Aggregate Pseudorandom Functions and Connections to Learning Revisions: 1 In the first part of this work, we introduce a new type of pseudo-random function for which aggregate queries'' over exponential-sized sets can be efficiently answered. An example of an aggregate query may be the product of all function values belonging to an exponential-sized interval, or the sum of all ... more >>> TR04-028 | 19th March 2004 Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker #### Aggregates with Component Size One Characterize Polynomial Space Aggregates are a computational model similar to circuits, but the underlying graph is not necessarily acyclic. Logspace-uniform polynomial-size aggregates decide exactly the languages in PSPACE; without uniformity condition they decide the languages in PSPACE/poly. As a measure of similarity to boolean circuits we introduce the parameter component size. We ... more >>> TR10-185 | 2nd December 2010 Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu #### Agnostic Learning of Monomials by Halfspaces is Hard We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with$(1-\epsilon)$of the examples, it is$\mathrm{NP}$-hard to find a halfspace that is correct on$(1/2+\epsilon)$of the examples, for arbitrary constants$\epsilon ... more >>>

TR94-020 | 12th December 1994

#### Agnostic PAC-Learning of Functions on Analog Neural Nets

We consider learning on multi-layer neural nets with piecewise polynomial
activation functions and a fixed number k of numerical inputs. We exhibit
arbitrarily large network architectures for which efficient and provably
successful learning algorithms exist in the rather realistic refinement of
Valiant's model for probably approximately correct learning ("PAC-learning")
where ... more >>>

TR19-112 | 1st September 2019
Yotam Dikstein, Irit Dinur

#### Agreement testing theorems on layered set systems

We introduce a framework of layered subsets, and give a sufficient condition for when a set system supports an agreement test. Agreement testing is a certain type of property testing that generalizes PCP tests such as the plane vs. plane test.

Previous work has shown that high dimensional expansion ... more >>>

TR17-181 | 26th November 2017
Irit Dinur, Yuval Filmus, Prahladh Harsha

#### Agreement tests on graphs and hypergraphs

Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreement test, a function is given by an ensemble of local restrictions. The agreement test checks that the restrictions agree when they overlap, and the ... more >>>

TR00-013 | 14th February 2000
Daniel Král

#### Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization

Ordered binary decision diagrams (OBDDs) and parity ordered binary
decision diagrams have proved their importance as data structures
representing Boolean functions. In addition to parity OBDDs we study
their generalization which we call parity AOBDDs, give the algebraic
characterization theorem and compare their minimal size to the size
more >>>

TR15-172 | 3rd November 2015
Benny Applebaum, Shachar Lovett

#### Algebraic Attacks against Random Local Functions and Their Countermeasures

Revisions: 1

Suppose that you have $n$ truly random bits $x=(x_1,\ldots,x_n)$ and you wish to use them to generate $m\gg n$ pseudorandom bits $y=(y_1,\ldots, y_m)$ using a local mapping, i.e., each $y_i$ should depend on at most $d=O(1)$ bits of $x$. In the polynomial regime of $m=n^s$, $s>1$, the only known solution, ... more >>>

TR18-019 | 28th January 2018
Zeyu Guo, Nitin Saxena, Amit Sinhababu

#### Algebraic dependencies and PSPACE algorithms in approximative complexity

Revisions: 1

Testing whether a set $\mathbf{f}$ of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). The best complexity known is NP$^{\#\rm P}$ (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). ... more >>>

TR14-130 | 17th October 2014
Ankit Gupta

#### Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties

Revisions: 1

We present an algebraic-geometric approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-4 circuits with bounded top fanin. Using our approach, we devise such an algorithm for the case when such circuits have bounded bottom fanin and satisfy a certain non-degeneracy condition. In particular, we ... more >>>

TR11-022 | 14th February 2011
Malte Beecken, Johannes Mittmann, Nitin Saxena

#### Algebraic Independence and Blackbox Identity Testing

Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. Polynomials $\{f_1,\ldots, f_m\} \subset \mathbb{F}[x_1,\ldots, x_n]$ are called algebraically independent if there is no non-zero polynomial $F$ such that $F(f_1, \ldots, f_m) = 0$. The transcendence degree, $\mbox{trdeg}\{f_1,\ldots, f_m\}$, is the maximal ... more >>>

TR12-014 | 20th February 2012
Johannes Mittmann, Nitin Saxena, Peter Scheiblechner

#### Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

A set of multivariate polynomials, over a field of zero or large characteristic, can be tested for algebraic independence by the well-known Jacobian criterion. For fields of other characteristic $p>0$, there is no analogous characterization known. In this paper we give the first such criterion. Essentially, it boils down to ... more >>>

TR07-022 | 20th February 2007
Rafail Ostrovsky, William Skeith

#### Algebraic Lower Bounds for Computing on Encrypted Data

In cryptography, there has been tremendous success in building
primitives out of homomorphic semantically-secure encryption
schemes, using homomorphic properties in a black-box way. A few
notable examples of such primitives include items like private
information retrieval schemes and collision-resistant hash functions. In this paper, we illustrate a general
methodology for ... more >>>

TR16-101 | 1st July 2016
Toniann Pitassi, Iddo Tzameret

#### Algebraic Proof Complexity: Progress, Frontiers and Challenges

We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problems, and new directions of research. In particular, we focus on tight ... more >>>

TR01-011 | 21st January 2001
Dima Grigoriev, Edward Hirsch

#### Algebraic proof systems over formulas

We introduce two algebraic propositional proof systems F-NS
and F-PC. The main difference of our systems from (customary)
Nullstellensatz and Polynomial Calculus is that the polynomials
are represented as arbitrary formulas (rather than sums of
monomials). Short proofs of Tseitin's tautologies in the
constant-depth version of F-NS provide ... more >>>

TR10-097 | 16th June 2010
Iddo Tzameret

#### Algebraic Proofs over Noncommutative Formulas

Revisions: 1

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege--yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analogue of Frege proofs, different from that given in Buss ... more >>>

TR07-111 | 1st November 2007

#### Algebraic Property Testing: The Role of Invariance

We argue that the symmetries of a property being tested play a
central role in property testing. We support this assertion in the
context of algebraic functions, by examining properties of functions
mapping a vector space $\K^n$ over a field $\K$ to a subfield $\F$.
We consider $\F$-linear properties that ... more >>>

TR05-132 | 8th November 2005
Venkatesan Guruswami

#### Algebraic-geometric generalizations of the Parvaresh-Vardy codes

This paper is concerned with a new family of error-correcting codes
based on algebraic curves over finite fields, and list decoding
algorithms for them. The basic goal in the subject of list decoding is
to construct error-correcting codes $C$ over some alphabet $\Sigma$
which have good rate $R$, and at ... more >>>

TR08-005 | 15th January 2008
Scott Aaronson, Avi Wigderson

#### Algebrization: A New Barrier in Complexity Theory

Any proof of P!=NP will have to overcome two barriers: relativization
and natural proofs. Yet over the last decade, we have seen circuit
lower bounds (for example, that PP does not have linear-size circuits)
that overcome both barriers simultaneously. So the question arises of
whether there ... more >>>

TR08-039 | 7th April 2008
Oded Goldreich, Dana Ron

#### Algorithmic Aspects of Property Testing in the Dense Graphs Model

In this paper we consider two refined questions regarding
the query complexity of testing graph properties
The first question refers to the relation between adaptive
and non-adaptive testers, whereas the second question refers to
testability within complexity that
is inversely proportional to ... more >>>

TR11-128 | 21st September 2011
Michael Elberfeld, Andreas Jakoby, Till Tantau

#### Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

An algorithmic meta theorem for a logic and a class $C$ of structures states that all problems expressible in this logic can be solved efficiently for inputs from $C$. The prime example is Courcelle's Theorem, which states that monadic second-order (MSO) definable problems are linear-time solvable on graphs of bounded ... more >>>

TR09-147 | 30th December 2009
Stephan Kreutzer

#### Algorithmic Meta-Theorems

Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a logical and a
structural component, that is they are results of the form:
"every computational problem that can be formalised in a given logic L ... more >>>

TR18-010 | 14th January 2018
Alexander A. Sherstov

#### Algorithmic polynomials

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree ... more >>>

TR10-073 | 21st April 2010
Neeraj Kayal

#### Algorithms for Arithmetic Circuits

Given a multivariate polynomial f(x) in F[x] as an arithmetic circuit we would like to efficiently determine:

(i) [Identity Testing.] Is f(x) identically zero?

(ii) [Degree Computation.] Is the degree of the
polynomial f(x) at most a given integer d.

(iii) [Polynomial Equivalence.] Upto an ... more >>>

TR05-033 | 5th March 2005

#### Algorithms for Counting 2-SAT Solutions and Colorings with Applications

An algorithm is presented for counting the number of maximum weight satisfying assignments of a 2SAT formula. The worst case running time of $O(\mbox{poly($n$)} \cdot 1.2461^n)$ for formulas with $n$ variables improves on the previous bound of $O(\mbox{poly($n$)} \cdot 1.2561^n)$ by Dahll\"of, Jonsson, and Wahlstr\"om . The weighted 2SAT counting ... more >>>

TR13-123 | 6th September 2013
Joshua Grochow, Youming Qiao

#### Algorithms for group isomorphism via group extensions and cohomology

The isomorphism problem for groups given by multiplication tables (GpI) is well-known to be solvable in n^O(log n) time, but only recently has there been significant progress towards polynomial time. For example, in 2012 Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. ... more >>>

TR07-059 | 6th July 2007
Shankar Kalyanaraman, Chris Umans

#### Algorithms for Playing Games with Limited Randomness

only limited randomness. This constrains both the algorithms used to
compute equilibria (they should use little or no randomness) as well
as the mixed strategies that the participants are capable of playing
(these should be sparse). We frame algorithmic ... more >>>

TR01-012 | 4th January 2001
Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov

#### Algorithms for SAT and Upper Bounds on Their Complexity

We survey recent algorithms for the propositional
satisfiability problem, in particular algorithms
that have the best current worst-case upper bounds
on their complexity. We also discuss some related
issues: the derandomization of the algorithm of
Paturi, Pudlak, Saks and Zane, the Valiant-Vazirani
Lemma, and random walk ... more >>>

TR03-072 | 15th September 2003
Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

#### Algorithms for SAT based on search in Hamming balls

We present a simple randomized algorithm for SAT and prove an upper
bound on its running time. Given a Boolean formula F in conjunctive
normal form, the algorithm finds a satisfying assignment for F
(if any) by repeating the following: Choose an assignment A at
random and ... more >>>

TR10-122 | 18th July 2010
Zhixiang Chen, Bin Fu, Yang Liu, Robert Schweller

#### Algorithms for Testing Monomials in Multivariate Polynomials

This paper is our second step towards developing a theory of
testing monomials in multivariate polynomials. The central
question is to ask whether a polynomial represented by an
arithmetic circuit has some types of monomials in its sum-product
expansion. The complexity aspects of this problem and its variants
have been ... more >>>

TR11-124 | 15th September 2011

#### Algorithms for the Coin Weighing Problems with the Presence of Noise

The coin weighing problem is the following: Given $n$ coins for which $m$ of them are counterfeit with the same weight. The problem is to detect the counterfeit coins with minimal number of weighings. This problem has many applications in compressed sensing, multiple access adder channels, etc. The problem was ... more >>>

TR16-008 | 26th January 2016
Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

#### Algorithms from Natural Lower Bounds

Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization ... more >>>

TR13-117 | 1st September 2013
Igor Oliveira

#### Algorithms versus Circuit Lower Bounds

Different techniques have been used to prove several transference theorems of the form "nontrivial algorithms for a circuit class C yield circuit lower bounds against C". In this survey we revisit many of these results. We discuss how circuit lower bounds can be obtained from derandomization, compression, learning, and satisfiability ... more >>>

TR16-168 | 2nd November 2016
Eric Blais, Clement Canonne, Tom Gur

#### Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)

Revisions: 1

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method ... more >>>

TR17-150 | 26th September 2017
Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs

#### All Classical Adversary Methods are Equivalent for Total Functions

Revisions: 2

We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $\text{fbs}(f)$. That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. For partial functions, we show ... more >>>

TR06-122 | 20th September 2006
Noam Livne

#### All Natural NPC Problems Have Average-Case Complete Versions

Revisions: 1

In 1984 Levin put forward a suggestion for a theory of {\em average
case complexity}. In this theory a problem, called a {\em
distributional problem}, is defined as a pair consisting of a
decision problem and a probability distribution over the instances.
Introducing adequate notions of simple distributions and average
more >>>

TR97-040 | 17th September 1997
Dorit Dor, Shay Halperin, Uri Zwick

#### All Pairs Almost Shortest Paths

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple
argument shows that computing all distances in G with an additive
one-sided error of at most 1 is as hard as Boolean matrix
multiplication. Building on recent work of Aingworth, Chekuri and
Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time
more >>>

TR00-060 | 17th August 2000
Uri Zwick

#### All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

We present two new algorithms for solving the {\em All
Pairs Shortest Paths\/} (APSP) problem for weighted directed
graphs. Both algorithms use fast matrix multiplication algorithms.

The first algorithm
solves the APSP problem for weighted directed graphs in which the edge
weights are integers of small absolute value in ... more >>>

TR99-004 | 3rd February 1999
Valentine Kabanets

#### Almost $k$-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs

Revisions: 1

Andreev et al.~\cite{ABCR97} give constructions of Boolean
functions (computable by polynomial-size circuits) that require large
read-once branching program (1-b.p.'s): a function in P that requires
1-b.p. of size at least $2^{n-\polylog(n)}$, a function in quasipolynomial
time that requires 1-b.p. of size at least $2^{n-O(\log n)}$, and a
function in LINSPACE ... more >>>

TR02-048 | 31st July 2002
Noga Alon, Oded Goldreich, Yishay Mansour

#### Almost $k$-wise independence versus $k$-wise independence

We say that a distribution over $\{0,1\}^n$
is almost $k$-wise independent
if its restriction to every $k$ coordinates results in a
distribution that is close to the uniform distribution.
A natural question regarding almost $k$-wise independent
distributions is how close they are to some $k$-wise
independent distribution. We show ... more >>>

TR05-010 | 8th December 2004
Olivier Powell

#### Almost Completeness in Small Complexity Classes

We constructively prove the existence of almost complete problems under logspace manyone reduction for some small complexity classes by exhibiting a parametrizable construction which yields, when appropriately setting the parameters, an almost complete problem for PSPACE, the class of space efficiently decidable problems, and for SUBEXP, the class of problems ... more >>>

TR16-187 | 21st November 2016
morris yau

#### Almost Cubic Bound for Depth Three Circuits in VP

Revisions: 3

In "An Almost Cubic Lower Bound for $\sum\prod\sum$ circuits in VP", [BLS16] present an infinite family of polynomials, $\{P_n\}_{n \in \mathbb{Z}^+}$, with $P_n$
on $N = \Theta(n polylog(n))$
variables with degree $N$ being in VP such that every
$\sum\prod\sum$ circuit computing $P_n$ is of size $\Omega\big(\frac{N^3}{2^{\sqrt{\log N}}}\big)$.
We ... more >>>

TR07-012 | 22nd January 2007
Shachar Lovett, Sasha Sodin

#### Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits

Revisions: 1

It is well known that $\R^N$ has subspaces of dimension
proportional to $N$ on which the $\ell_1$ norm is equivalent to the
$\ell_2$ norm; however, no explicit constructions are known.
Extending earlier work by Artstein--Avidan and Milman, we prove that
such a subspace can be generated using $O(N)$ random bits.

... more >>>

TR07-086 | 7th September 2007
Venkatesan Guruswami, James R. Lee, Alexander Razborov

#### Almost Euclidean subspaces of $\ell_1^N$ via expander codes

We give an explicit (in particular, deterministic polynomial time)
construction of subspaces $X \subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,
$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$
If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits
and ... more >>>

TR11-049 | 9th April 2011
Noga Alon, Shachar Lovett

#### Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions

A family of permutations in $S_n$ is $k$-wise independent if a uniform permutation chosen from the family maps any distinct $k$ elements to any distinct $k$ elements equally likely. Efficient constructions of $k$-wise independent permutations are known for $k=2$ and $k=3$, but are unknown for $k \ge 4$. In fact, ... more >>>

TR09-120 | 18th November 2009
Charanjit Jutla

#### Almost Optimal Bounds for Direct Product Threshold Theorem

Revisions: 2

We consider weakly-verifiable puzzles which are challenge-response puzzles such that the responder may not
be able to verify for itself whether it answered the challenge correctly. We consider $k$-wise direct product of
such puzzles, where now the responder has to solve $k$ puzzles chosen independently in parallel.
Canetti et ... more >>>

TR10-183 | 29th November 2010
Raghu Meka

#### Almost Optimal Explicit Johnson-Lindenstrauss Transformations

Revisions: 2

The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known constructions of linear embeddings that satisfy the Johnson-Lindenstrauss property involve randomness. We address the question of explicitly constructing such embedding families and provide a construction ... more >>>

TR19-156 | 7th November 2019

#### Almost Optimal Testers for Concise Representations

We give improved and almost optimal testers for several classes of Boolean functions on $n$ inputs that have concise representation in the uniform and distribution-free model. Classes, such as $k$-Junta, $k$-Linear Function, $s$-Term DNF, $s$-Term Monotone DNF, $r$-DNF, Decision List, $r$-Decision List, size-$s$ Decision Tree, size-$s$ Boolean Formula, size-$s$ Branching ... more >>>

TR03-066 | 2nd September 2003
Daniele Micciancio

#### Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor

Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai (STOC 1996) connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous ... more >>>

TR15-200 | 4th December 2015
Andris Ambainis

#### Almost quadratic gap between partition complexity and query/communication complexity

Revisions: 1

We show nearly quadratic separations between two pairs of complexity measures:
1. We show that there is a Boolean function $f$ with $D(f)=\Omega((D^{sc}(f))^{2-o(1)})$ where $D(f)$ is the deterministic query complexity of $f$ and $D^{sc}$ is the subcube partition complexity of $f$;
2. As a consequence, we obtain that there is ... more >>>

TR19-178 | 5th December 2019
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

#### Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs

We show that the size of any regular resolution refutation of Tseitin formula $T(G,c)$ based on a graph $G$ is at least $2^{\Omega(tw(G)/\log n)}$, where $n$ is the number of vertices in $G$ and $tw(G)$ is the treewidth of $G$. For constant degree graphs there is known upper bound $2^{O(tw(G))}$ ... more >>>

TR16-195 | 19th November 2016
Pasin Manurangsi

#### Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph

Revisions: 1

In the Densest $k$-Subgraph problem, given an undirected graph $G$ and an integer $k$, the goal is to find a subgraph of $G$ on $k$ vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves only $O(n^{1/4 + \varepsilon})$ approximation ratio (Bhaskara et al., ... more >>>

TR17-192 | 15th December 2017
Krishnamoorthy Dinesh, Jayalal Sarma

Revisions: 1

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function $f:\{0,1\}^n \to \{0,1\}$, block sensitivity of $f$ is polynomially related to sensitivity of $f$ (denoted by $\mathbf{sens}(f)$). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, $f:\{0,1\}^n ... more >>> TR14-012 | 27th January 2014 Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz #### AM with Multiple Merlins Revisions: 1 We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close ... more >>> TR16-054 | 11th April 2016 Omri Weinstein, Huacheng Yu #### Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication This paper develops a new technique for proving amortized, randomized cell-probe lower bounds on dynamic data structure problems. We introduce a new randomized nondeterministic four-party communication model that enables "accelerated", error-preserving simulations of dynamic data structures. We use this technique to prove an$\Omega(n\left(\log n/\log\log n\right)^2)$cell-probe ... more >>> TR15-158 | 27th September 2015 Ofer Grossman, Dana Moshkovitz #### Amplification and Derandomization Without Slowdown We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm, and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms. The ... more >>> TR15-031 | 2nd March 2015 Marco Molinaro, David Woodruff, Grigory Yaroslavtsev #### Amplification of One-Way Information Complexity via Codes and Noise Sensitivity Revisions: 1 We show a new connection between the information complexity of one-way communication problems under product distributions and a relaxed notion of list-decodable codes. As a consequence, we obtain a characterization of the information complexity of one-way problems under product distributions for any error rate based on covering numbers. This generalizes ... more >>> TR18-058 | 5th April 2018 Thomas Watson #### Amplification with One NP Oracle Query We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, one-sided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our ... more >>> TR08-038 | 4th April 2008 Eric Allender, Michal Koucky #### Amplifying Lower Bounds by Means of Self-Reducibility Revisions: 2 We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>> TR15-102 | 22nd June 2015 Mario Szegedy #### An$O(n^{0.4732})$upper bound on the complexity of the GKS communication game We give an$5\cdot n^{\log_{30}5}$upper bund on the complexity of the communication game introduced by G. Gilmer, M. Kouck\'y and M. Saks \cite{saks} to study the Sensitivity Conjecture \cite{linial}, improving on their$\sqrt{999\over 1000}\sqrt{n}$bound. We also determine the exact complexity of the game up to$n\le 9$. more >>> TR15-016 | 16th January 2015 Diptarka Chakraborty, Raghunath Tewari #### An$O(n^{\epsilon})$Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs Revisions: 1 Given a graph$G$and two vertices$s$and$t$in it, {\em graph reachability} is the problem of checking whether there exists a path from$s$to$t$in$G$. We show that reachability in directed layered planar graphs can be decided in polynomial time and$O(n^\epsilon)$space, for ... more >>> TR16-126 | 8th August 2016 Subhash Khot, Igor Shinkar #### An$\widetilde{O}(n)$Queries Adaptive Tester for Unateness We present an adaptive tester for the unateness property of Boolean functions. Given a function$f:\{0,1\}^n \to \{0,1\}$the tester makes$O(n \log(n)/\epsilon)$adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 any function that is$\epsilon$-far from being unate. more >>> TR19-144 | 29th October 2019 Young Ko, Omri Weinstein #### An Adaptive Step Toward the Multiphase Conjecture Revisions: 1 In 2010, Patrascu proposed a dynamic set-disjointness problem, known as the Multiphase problem, as a candidate for proving$polynomial$lower bounds on the operational time of dynamic data structures. Patrascu conjectured that any data structure for the Multiphase problem must make$n^\epsilon$cell-probes in either the update or query phase, ... more >>> TR17-029 | 18th February 2017 Clement Canonne, Tom Gur #### An Adaptivity Hierarchy Theorem for Property Testing Revisions: 1 Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all ... more >>> TR11-157 | 25th November 2011 Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi #### An additive combinatorics approach to the log-rank conjecture in communication complexity Revisions: 1 For a {0,1}-valued matrix$M$let CC($M$) denote the deterministic communication complexity of the boolean function associated with$M$. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC($M$) is at most$\log^c({\mbox{rank}}(M))$for some absolute constant$c$where rank($M$) denotes the rank of$M$over the field ... more >>> TR96-010 | 9th February 1996 Christoph Meinel, Anna Slobodova #### An Adequate Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams Revisions: 1 Reducibility concepts are fundamental in complexity theory. Usually, they are defined as follows: A problem P is reducible to a problem S if P can be computed using a program or device for S as a subroutine. However, in the case of such restricted models as ... more >>> TR11-172 | 20th December 2011 Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg #### An Algorithmic Characterization of Multi-Dimensional Mechanisms We obtain a characterization of feasible, Bayesian, multi-item multi-bidder mechanisms with independent, additive bidders as distributions over hierarchical mechanisms. Combined with cyclic-monotonicity our results provide a complete characterization of feasible, Bayesian Incentive Compatible mechanisms for this setting. Our characterization is enabled by a novel, constructive proof of Border's theorem [Border ... more >>> TR16-143 | 15th September 2016 Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan #### An Almost Cubic Lower Bound for$\Sigma\Pi\Sigma$Circuits Computing a Polynomial in VP In this note, we prove that there is an explicit polynomial in VP such that any$\Sigma\Pi\Sigma$arithmetic circuit computing it must have size at least$n^{3-o(1)}$. Up to$n^{o(1)}$factors, this strengthens a recent result of Kayal, Saha and Tavenas (ICALP 2016) which gives a polynomial in VNP with ... more >>> TR16-006 | 22nd January 2016 Neeraj Kayal, Chandan Saha, Sébastien Tavenas #### An almost Cubic Lower Bound for Depth Three Arithmetic Circuits Revisions: 2 We show an$\Omega \left(\frac{n^3}{(\ln n)^2}\right)$lower bound on the size of any depth three ($\SPS$) arithmetic circuit computing an explicit multilinear polynomial in$n$variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson. more >>> TR08-108 | 19th November 2008 Nitin Saxena, C. Seshadhri #### An Almost Optimal Rank Bound for Depth-3 Identities We show that the rank of a depth-3 circuit (over any field) that is simple, minimal and zero is at most O(k^3\log d). The previous best rank bound known was 2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka (STOC 2005). This almost resolves the rank question first posed by ... more >>> TR17-124 | 6th August 2017 Mrinal Kumar, Ben Lee Volk #### An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits Revisions: 2 We prove a lower bound of$\Omega(n^2/\log^2 n)$on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial$f(x_1, \ldots, x_n)$. Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff [RSY08], who proved a lower bound of$\Omega(n^{4/3}/\log^2 n)$for the same ... more >>> TR14-114 | 27th August 2014 Roei Tell #### An Alternative Proof of an$\Omega(k)$Lower Bound for Testing$k$-linear Boolean Functions We provide an alternative proof for a known result stating that$\Omega(k)$queries are needed to test$k$-sparse linear Boolean functions. Similar to the approach of Blais and Kane (2012), we reduce the proof to the analysis of Hamming weights of vectors in affi ne subspaces of the Boolean hypercube. ... more >>> TR10-096 | 16th June 2010 Dana Moshkovitz #### An Alternative Proof of The Schwartz-Zippel Lemma Revisions: 1 We show a non-inductive proof of the Schwartz-Zippel lemma. The lemma bounds the number of zeros of a multivariate low degree polynomial over a finite field. more >>> TR00-018 | 16th February 2000 Oliver Kullmann #### An application of matroid theory to the SAT problem A basic property of minimally unsatisfiable clause-sets F is that c(F) >= n(F) + 1 holds, where c(F) is the number of clauses, and n(F) the number of variables. Let MUSAT(k) be the class of minimally unsatisfiable clause-sets F with c(F) <= n(F) + k. Poly-time decision algorithms are known ... more >>> TR04-110 | 24th November 2004 Tomoyuki Yamakami, Harumichi Nishimura #### An Application of Quantum Finite Automata to Interactive Proof Systems Quantum finite automata have been studied intensively since their introduction in late 1990s as a natural model of a quantum computer with finite-dimensional quantum memory space. This paper seeks their direct application to interactive proof systems in which a mighty quantum prover communicates with a ... more >>> TR09-085 | 14th September 2009 Christoph Behle, Andreas Krebs, Stephanie Reifferscheid #### An Approach to characterize the Regular Languages in TC0 with Linear Wires Revisions: 1 We consider the regular languages recognized by weighted threshold circuits with a linear number of wires. We present a simple proof to show that parity cannot be computed by such circuits. Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ... more >>> TR14-030 | 5th March 2014 Dana Moshkovitz #### An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing The Sliding Scale Conjecture in PCP states that there are PCP verifiers with a constant number of queries and soundness error that is exponentially small in the randomness of the verifier and the length of the prover's answers. The Sliding Scale Conjecture is one of the oldest open problems in ... more >>> TR97-017 | 5th May 1997 Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky #### An Approximation Algorithm for the Bandwidth Problem on Dense Graphs The bandwidth problem is the problem of numbering the vertices of a given graph$G$such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and is known to be NP-complete Papadimitriou [Pa76]. Only few special cases ... more >>> TR04-048 | 21st April 2004 André Lanka, Andreas Goerdt #### An approximation hardness result for bipartite Clique Assuming 3-SAT formulas are hard to refute on average, Feige showed some approximation hardness results for several problems like min bisection, dense$k$-subgraph, max bipartite clique and the 2-catalog segmentation problem. We show a similar result for max bipartite clique, but under the assumption, 4-SAT formulas are hard to refute ... more >>> TR15-065 | 18th April 2015 Benjamin Rossman, Rocco Servedio, Li-Yang Tan #### An average-case depth hierarchy theorem for Boolean circuits We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every$d \geq 2$, there is an explicit$n$-variable Boolean function$f$, computed by a linear-size depth-$d$formula, which is such that any depth-$(d-1)$... more >>> TR16-041 | 17th March 2016 Johan Hastad #### An average-case depth hierarchy theorem for higher depth We extend the recent hierarchy results of Rossman, Servedio and Tan \cite{rst15} to any$d \leq \frac {c \log n}{\log {\log n}}$for an explicit constant$c$. To be more precise, we prove that for any such$d$there is a function$F_d$that is computable by a read-once formula ... more >>> TR17-173 | 6th November 2017 Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam #### An Average-Case Lower Bound against ACC^0 In a seminal work, Williams [Wil14] showed that NEXP (non-deterministic exponential time) does not have polynomial-size ACC^0 circuits. Williams' technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known. We show that there is a language L in NEXP (resp. EXP^NP) ... more >>> TR98-069 | 7th December 1998 Rüdiger Reischuk, Thomas Zeugmann #### An Average-Case Optimal One-Variable Pattern Language Learner A new algorithm for learning one-variable pattern languages from positive data is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all operations till convergence to a correct hypothesis is achieved. For almost all meaningful distributions defining how ... more >>> TR95-038 | 2nd July 1995 Joe Kilian, Erez Petrank #### An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions We consider noninteractive zero-knowledge proofs in the shared random string model proposed by Blum, Feldman and Micali \cite{bfm}. Until recently there was a sizable polynomial gap between the most efficient noninteractive proofs for {\sf NP} based on general complexity assumptions \cite{fls} versus those based on specific algebraic assumptions \cite{Da}. ... more >>> TR17-129 | 27th August 2017 Or Meir #### An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds Revisions: 8 One of the important challenges in circuit complexity is proving strong lower bounds for constant-depth circuits. One possible approach to this problem is to use the framework of Karchmer-Wigderson relations: Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean function$f$there is a corresponding communication problem$\mathrm{KW}_{f}$, more >>> TR06-119 | 13th September 2006 Noga Alon, Oded Schwartz, Asaf Shapira #### An Elementary Construction of Constant-Degree Expanders We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement-product, which we analyze using an elementary combinatorial argument. The construction applies the replacement product (only twice!) to turn the Cayley expanders of \cite{AR}, whose degree is polylog n, into constant degree expanders. ... more >>> TR11-026 | 27th February 2011 Evgeny Demenkov, Alexander Kulikov #### An Elementary Proof of$3n-o(n)$Lower Bound on the Circuit Complexity of Affine Dispersers A Boolean function$f \colon \mathbb{F}^n_2 \rightarrow \mathbb{F}_2$is called an affine disperser for sources of dimension$d$, if$f$is not constant on any affine subspace of$\mathbb{F}^n_2$of dimension at least$d$. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for$d=o(n)$. The main ... more >>> TR10-182 | 26th November 2010 Shachar Lovett #### An elementary proof of anti-concentration of polynomials in Gaussian variables Recently there has been much interest in polynomial threshold functions in the context of learning theory, structural results and pseudorandomness. A crucial ingredient in these works is the understanding of the distribution of low-degree multivariate polynomials evaluated over normally distributed inputs. In particular, the two important properties are exponential tail ... more >>> TR10-091 | 14th May 2010 Nikolay Vereshchagin #### An Encoding Invariant Version of Polynomial Time Computable Distributions When we represent a decision problem,like CIRCUIT-SAT, as a language over the binary alphabet, we usually do not specify how to encode instances by binary strings. This relies on the empirical observation that the truth of a statement of the form CIRCUIT-SAT belongs to a complexity class$C$'' more >>> TR18-008 | 10th January 2018 Tom Gur, Igor Shinkar #### An Entropy Lower Bound for Non-Malleable Extractors A (k,\eps)-non-malleable extractor is a function nmExt : {0,1}^n x {0,1}^d -> {0,1} that takes two inputs, a weak source X~{0,1}^n of min-entropy k and an independent uniform seed s in {0,1}^d, and outputs a bit nmExt(X, s) that is \eps-close to uniform, even given the seed s and the ... more >>> TR14-165 | 3rd December 2014 Venkatesan Guruswami, Ameya Velingker #### An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets We prove a lower estimate on the increase in entropy when two copies of a conditional random variable$X | Y$, with$X$supported on$\mathbb{Z}_q=\{0,1,\dots,q-1\}$for prime$q$, are summed modulo$q$. Specifically, given two i.i.d. copies$(X_1,Y_1)$and$(X_2,Y_2)$of a pair of random variables$(X,Y)$, with$X$... more >>> TR01-083 | 29th October 2001 Nikolay Vereshchagin #### An enumerable undecidable set with low prefix complexity: a simplified proof Revisions: 1 We present a simplified proof of Solovay-Calude-Coles theorem stating that there is an enumerable undecidable set with the following property: prefix complexity of its initial segment of length n is bounded by prefix complexity of n (up to an additive constant). more >>> TR03-013 | 7th March 2003 Luca Trevisan #### An epsilon-Biased Generator in NC0 Comments: 1 Cryan and Miltersen recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator such that every bit of the output depends on a constant number k of bits of the seed. They show that for k=3 there ... more >>> TR12-127 | 3rd October 2012 Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari #### An Explicit VC-Theorem for Low-Degree Polynomials Let$X \subseteq \mathbb{R}^{n}$and let${\mathcal C}$be a class of functions mapping$\mathbb{R}^{n} \rightarrow \{-1,1\}.$The famous VC-Theorem states that a random subset$S$of$X$of size$O(\frac{d}{\epsilon^{2}} \log \frac{d}{\epsilon})$, where$d$is the VC-Dimension of${\mathcal C}$, is (with constant probability) an$\epsilon$-approximation for${\mathcal C}$... more >>> TR07-007 | 17th January 2007 Jan Krajicek #### An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams We prove an exponential lower bound on the size of proofs in the proof system operating with ordered binary decision diagrams introduced by Atserias, Kolaitis and Vardi. In fact, the lower bound applies to semantic derivations operating with sets defined by OBDDs. We do not assume ... more >>> TR12-098 | 3rd August 2012 Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi #### An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin Revisions: 3 Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of$\times$gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing ... more >>> TR14-005 | 14th January 2014 Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan #### An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas We show here a$2^{\Omega(\sqrt{d} \cdot \log N)}$size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree$d$on$N$variables (with$N = d^3$in our case) with$0, 1$-coefficients such that for any representation of ... more >>> TR15-109 | 1st July 2015 Mrinal Kumar, Ramprasad Saptharishi #### An exponential lower bound for homogeneous depth-5 circuits over finite fields In this paper, we show exponential lower bounds for the class of homogeneous depth-$5$circuits over all small finite fields. More formally, we show that there is an explicit family$\{P_d : d \in N\}$of polynomials in$VNP$, where$P_d$is of degree$d$in$n = d^{O(1)}$variables, ... more >>> TR12-081 | 26th June 2012 Neeraj Kayal #### An exponential lower bound for the sum of powers of bounded degree polynomials Revisions: 1 In this work we consider representations of multivariate polynomials in$F[x]$of the form$ f(x) = Q_1(x)^{e_1} + Q_2(x)^{e_2} + ... + Q_s(x)^{e_s},$where the$e_i$'s are positive integers and the$Q_i$'s are arbitary multivariate polynomials of bounded degree. We give an explicit$n$-variate polynomial$f$of degree$n$... more >>> TR95-057 | 24th November 1995 Dima Grigoriev, Marek Karpinski, A. C. Yao #### An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX We prove an exponential lower bound on the size of any fixed-degree algebraic decision tree for solving MAX, the problem of finding the maximum of$n$real numbers. This complements the$n-1$lower bound of Rabin \cite{R72} on the depth of ... more >>> TR19-005 | 16th January 2019 Omar Alrabiah, Venkatesan Guruswami #### An Exponential Lower Bound on the Sub-Packetization of MSR Codes An$(n,k,\ell)$-vector MDS code is a$\mathbb{F}$-linear subspace of$(\mathbb{F}^\ell)^n$(for some field$\mathbb{F}$) of dimension$k\ell$, such that any$k$(vector) symbols of the codeword suffice to determine the remaining$r=n-k$(vector) symbols. The length$\ell$of each codeword symbol is called the sub-packetization of the code. Such a ... more >>> TR94-018 | 12th December 1994 Jan Krajicek, Pavel Pudlak, Alan Woods #### An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle We prove lower bounds of the form$exp\left(n^{\epsilon_d}\right),\epsilon_d>0,$on the length of proofs of an explicit sequence of tautologies, based on the Pigeonhole Principle, in proof systems using formulas of depth$d,$for any constant$d.$This is the largest lower bound for the strongest proof system, for which ... more >>> TR18-083 | 25th April 2018 Tom Gur, Ron D. Rothblum, Yang P. Liu #### An Exponential Separation Between MA and AM Proofs of Proximity Revisions: 2 Non-interactive proofs of proximity allow a sublinear-time verifier to check that a given input is close to the language, given access to a short proof. Two natural variants of such proof systems are MA-proofs of Proximity (MAP), in which the proof is a function of the input only, and AM-proofs ... more >>> TR01-056 | 6th August 2001 Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart #### An Exponential Separation between Regular and General Resolution This paper gives two distinct proofs of an exponential separation between regular resolution and unrestricted resolution. The previous best known separation between these systems was quasi-polynomial. more >>> TR15-173 | 29th October 2015 Martin Schwarz #### An exponential time upper bound for Quantum Merlin-Arthur games with unentangled provers We prove a deterministic exponential time upper bound for Quantum Merlin-Arthur games with k unentangled provers. This is the first non-trivial upper bound of QMA(k) better than NEXP and can be considered an exponential improvement, unless EXP=NEXP. The key ideas of our proof are to use perturbation theory to reduce ... more >>> TR07-046 | 23rd April 2007 Philipp Hertel #### An Exponential Time/Space Speedup For Resolution Comments: 1 Satisfiability algorithms have become one of the most practical and successful approaches for solving a variety of real-world problems, including hardware verification, experimental design, planning and diagnosis problems. The main reason for the success is due to highly optimized algorithms for SAT based on resolution. The most successful of these ... more >>> TR07-034 | 29th March 2007 Anup Rao #### An Exposition of Bourgain's 2-Source Extractor A construction of Bourgain gave the first 2-source extractor to break the min-entropy rate 1/2 barrier. In this note, we write an exposition of his result, giving a high level way to view his extractor construction. We also include a proof of a generalization of Vazirani's XOR lemma that seems ... more >>> TR12-029 | 3rd April 2012 Shachar Lovett #### An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem The polynomial Freiman-Ruzsa conjecture is one of the important conjectures in additive combinatorics. It asserts than one can switch between combinatorial and algebraic notions of approximate subgroups with only a polynomial loss in the underlying parameters. This conjecture has also already found several applications in theoretical computer science. Recently, Tom ... more >>> TR05-067 | 28th June 2005 Zeev Dvir, Amir Shpilka #### An Improved Analysis of Mergers Mergers are functions that transform k (possibly dependent) random sources into a single random source, in a way that ensures that if one of the input sources has min-entropy rate$\delta$then the output has min-entropy rate close to$\delta$. Mergers have proven to be a very useful tool in ... more >>> TR06-107 | 26th August 2006 Arkadev Chattopadhyay #### An improved bound on correlation between polynomials over Z_m and MOD_q Revisions: 1 Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... more >>> TR15-117 | 21st July 2015 Boris Bukh, Venkatesan Guruswami #### An improved bound on the fraction of correctable deletions Revisions: 1 We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed$k \ge 2$, we construct a family of codes over alphabet of size$k$with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching$1-\frac{2}{k+1}$. In particular, for binary codes, we are able to ... more >>> TR13-150 | 4th November 2013 Ruiwen Chen, Valentine Kabanets, Nitin Saurabh #### An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas We give a deterministic #SAT algorithm for de Morgan formulas of size up to$n^{2.63}$, which runs in time$2^{n-n^{\Omega(1)}}$. This improves upon the deterministic #SAT algorithm of \cite{CKKSZ13}, which has similar running time but works only for formulas of size less than$n^{2.5}$. Our new algorithm is based on ... more >>> TR17-030 | 15th February 2017 Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari #### An Improved Dictatorship Test with Perfect Completeness A Boolean function$f:\{0,1\}^n\rightarrow \{0,1\}$is called a dictator if it depends on exactly one variable i.e$f(x_1, x_2, \ldots, x_n) = x_i$for some$i\in [n]$. In this work, we study a$k$-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems. ... more >>> TR00-057 | 25th July 2000 Martin Sauerhoff #### An Improved Hierarchy Result for Partitioned BDDs One of the great challenges of complexity theory is the problem of analyzing the dependence of the complexity of Boolean functions on the resources nondeterminism and randomness. So far, this problem could be solved only for very few models of computation. For so-called partitioned binary decision diagrams, which are a ... more >>> TR16-206 | 24th December 2016 Benjamin Rossman #### An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity Previous work of the author [39] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC$^0$... more >>> TR12-099 | 5th August 2012 Nikos Leonardos #### An improved lower bound for the randomized decision tree complexity of recursive majority Revisions: 1 We prove that the randomized decision tree complexity of the recursive majority-of-three is$\Omega(2.6^d)$, where$d$is the depth of the recursion. The proof is by a bottom up induction, which is same in spirit as the one in the proof of Saks and Wigderson in their FOCS 1986 paper ... more >>> TR05-030 | 12th February 2005 Evgeny Dantsin, Alexander Wolpert #### An Improved Upper Bound for SAT We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most$2^{n(1-1/\alpha)}$up to a polynomial factor, where$\alpha = \ln(m/n) + O(\ln \ln m)$and$n$,$m$are respectively the number of variables ... more >>> TR17-140 | 11th September 2017 Tong Qin, Osamu Watanabe #### An improvement of the algorithm of Hertli for the unique 3SAT problem We propose a simple idea for improving the randomized algorithm of Hertli for the Unique 3SAT problem. more >>> TR07-117 | 8th November 2007 Edward Hirsch, Dmitry Itsykson #### An infinitely-often one-way function based on an average-case assumption We assume the existence of a function f that is computable in polynomial time but its inverse function is not computable in randomized average-case polynomial time. The cryptographic setting is, however, different: even for a weak one-way function, every possible adversary should fail on a polynomial fraction of inputs. Nevertheless, ... more >>> TR12-131 | 18th October 2012 Mark Braverman, Ankur Moitra #### An Information Complexity Approach to Extended Formulations Revisions: 1 We prove an unconditional lower bound that any linear program that achieves an$O(n^{1-\epsilon})$approximation for clique has size$2^{\Omega(n^\epsilon)}$. There has been considerable recent interest in proving unconditional lower bounds against any linear program. Fiorini et al proved that there is no polynomial sized linear program for traveling salesman. ... more >>> TR14-047 | 8th April 2014 Mark Braverman, Omri Weinstein #### An Interactive Information Odometer with Applications Revisions: 1 We introduce a novel technique which enables two players to maintain an estimate of the internal information cost of their conversation in an online fashion without revealing much extra information. We use this construction to obtain new results about communication complexity and information-theoretically secure computation. As a first corollary, ... more >>> TR09-144 | 24th December 2009 Prahladh Harsha, Adam Klivans, Raghu Meka #### An Invariance Principle for Polytopes Let$X$be randomly chosen from$\{-1,1\}^n$, and let$Y$be randomly chosen from the standard spherical Gaussian on$\R^n$. For any (possibly unbounded) polytope$P$formed by the intersection of$k$halfspaces, we prove that$$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k ... more >>> TR06-011 | 2nd January 2006 Yijia Chen, Martin Grohe #### An Isomorphism between Subexponential and Parameterized Complexity Theory We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories. more >>> TR96-002 | 10th January 1996 Manindra Agrawal, Eric Allender #### An Isomorphism Theorem for Circuit Complexity We show that all sets complete for NC$^1$under AC$^0$reductions are isomorphic under AC$^0$-computable isomorphisms. Although our proof does not generalize directly to other complexity classes, we do show that, for all complexity classes C closed under NC$^1$-computable many-one reductions, the sets ... more >>> TR04-114 | 21st November 2004 Vladimir Trifonov #### An O(log n log log n) Space Algorithm for Undirected s,t-Connectivity We present a deterministic O(log n log log n) space algorithm for undirected s,t-connectivity. It is based on the deterministic EREW algorithm of Chong and Lam (SODA 93) and uses the universal exploration sequences for trees constructed by Kouck\'y (CCC 01). Our result improves the O(log^{4/3} n) bound of Armoni ... more >>> TR06-050 | 18th April 2006 Alexander Razborov, Sergey Yekhanin #### An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval A two server private information retrieval (PIR) scheme allows a user U to retrieve the i-th bit of an n-bit string x replicated between two servers while each server individually learns no information about i. The main parameter of interest in a PIR scheme is its communication complexity, namely the ... more >>> TR18-043 | 22nd February 2018 Andrei Romashchenko, Marius Zimand #### An operational characterization of mutual information in algorithmic information theory Revisions: 2 We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings$x$and$y$is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties, one having$x$and the complexity profile of the pair and the ... more >>> TR13-062 | 18th April 2013 C. Seshadhri, Deeparnab Chakrabarty #### An optimal lower bound for monotonicity testing over hypergrids For positive integers$n, d$, consider the hypergrid$[n]^d$with the coordinate-wise product partial ordering denoted by$\prec$. A function$f: [n]^d \mapsto \mathbb{N}$is monotone if$\forall x \prec y$,$f(x) \leq f(y)$. A function$f$is$\varepsilon$-far from monotone if at least an$\varepsilon$-fraction of values must ... more >>> TR10-140 | 17th September 2010 Amit Chakrabarti, Oded Regev #### An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance We prove an optimal$\Omega(n)$lower bound on the randomized communication complexity of the much-studied Gap-Hamming-Distance problem. As a consequence, we obtain essentially optimal multi-pass space lower bounds in the data stream model for a number of fundamental problems, including the estimation of frequency moments. The Gap-Hamming-Distance problem is a ... more >>> TR03-070 | 19th August 2003 Amit Chakrabarti, Oded Regev #### An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching We consider the approximate nearest neighbour search problem on the Hamming Cube$\b^d$. We show that a randomised cell probe algorithm that uses polynomial storage and word size$d^{O(1)}$requires a worst case query time of$\Omega(\log\log d/\log\log\log d)$. The approximation factor may be as loose as$2^{\log^{1-\eta}d}$for any ... more >>> TR15-130 | 11th August 2015 Ronald de Haan #### An Overview of Non-Uniform Parameterized Complexity We consider several non-uniform variants of parameterized complexity classes that have been considered in the literature. We do so in a homogenous notation, allowing a clear comparison of the various variants. Additionally, we consider some novel (non-uniform) parameterized complexity classes that come up in the framework of parameterized knowledge compilation. ... more >>> TR18-166 | 18th September 2018 Tayfun Pay, James Cox #### An overview of some semantic and syntactic complexity classes We review some semantic and syntactic complexity classes that were introduced to better understand the relationship between complexity classes P and NP. We also define several new complexity classes, some of which are associated with Mersenne numbers, and show their location in the complexity hierarchy. more >>> TR15-033 | 6th March 2015 Alexander Razborov #### An Ultimate Trade-Off in Propositional Proof Complexity Revisions: 1 We exhibit an unusually strong trade-off between resolution proof width and tree-like proof size. Namely, we show that for any parameter$k=k(n)$there are unsatisfiable$k$-CNFs that possess refutations of width$O(k)$, but such that any tree-like refutation of width$n^{1-\epsilon}/k$must necessarily have {\em double} exponential size$\exp(n^{\Omega(k)})$. Conceptually, ... more >>> TR06-056 | 27th April 2006 Salil Vadhan #### An Unconditional Study of Computational Zero Knowledge We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist. We establish several new characterizations of ZK, and use these characterizations to ... more >>> TR95-010 | 16th February 1995 Pavel Pudlak, Jiri Sgall #### An Upper Bound for a Communication Game Related to Time-Space Tradeoffs We prove an unexpected upper bound on a communication game proposed by Jeff Edmonds and Russell Impagliazzo as an approach for proving lower bounds for time-space tradeoffs for branching programs. Our result is based on a generalization of a construction of Erdos, Frankl and Rodl of a large 3-hypergraph ... more >>> TR18-168 | 25th September 2018 Alex Samorodnitsky #### An upper bound on$\ell_q$norms of noisy functions Revisions: 1 Let$T_{\epsilon}$be the noise operator acting on functions on the boolean cube$\{0,1\}^n$. Let$f$be a nonnegative function on$\{0,1\}^n$and let$q \ge 1$. We upper bound the$\ell_q$norm of$T_{\epsilon} f$by the average$\ell_q$norm of conditional expectations of$f$, given sets of roughly ... more >>> TR01-079 | 6th September 2001 Michele Zito #### An Upper Bound on the Space Complexity of Random Formulae in Resolution We prove that, with high probability, the space complexity of refuting a random unsatisfiable boolean formula in$k$-CNF on$n$variables and$m = \Delta n$clauses is$O(n \cdot \Delta^{-\frac{1}{k-2}})$. more >>> TR18-131 | 17th July 2018 Gautam Kamath, Christos Tzamos #### Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing We investigate distribution testing with access to non-adaptive conditional samples. In the conditional sampling model, the algorithm is given the following access to a distribution: it submits a query set$S$to an oracle, which returns a sample from the distribution conditioned on being from$S$. In the non-adaptive setting, ... more >>> TR97-052 | 11th November 1997 Eduardo D. Sontag #### Analog Neural Nets with Gaussian or other Common Noise Distributions cannot Recognize Arbitrary Regular Languages We consider recurrent analog neural nets where the output of each gate is subject to Gaussian noise, or any other common noise distribution that is nonzero on a large set. We show that many regular languages cannot be recognized by networks of this type, and more >>> TR95-025 | 8th May 1995 Günter Hotz, Gero Vierke, Bjoern Schieffer #### Analytic Machines Comments: 1 In this paper the$R$-machines defined by Blum, Shub and Smale are generalized by allowing infinite convergent computations. The description of real numbers is infinite. Therefore, considering arithmetic operations on real numbers should also imply infinite computations on {\em analytic machines}. We prove that$\R$-computable functions are$\Q$-analytic. We show ... more >>> TR05-025 | 20th February 2005 Zeev Dvir, Ran Raz #### Analyzing Linear Mergers Mergers are functions that transform k (possibly dependent) random sources into a single random source, in a way that ensures that if one of the input sources has min-entropy rate$\delta$then the output has min-entropy rate close to$\delta$. Mergers have proven to be a very useful tool in ... more >>> TR19-046 | 1st April 2019 Akash Kumar, C. Seshadhri, Andrew Stolman #### andom walks and forbidden minors II: A$\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs Revisions: 1 Let$G$be a graph with$n$vertices and maximum degree$d$. Fix some minor-closed property$\mathcal{P}$(such as planarity). We say that$G$is$\varepsilon$-far from$\mathcal{P}$if one has to remove$\varepsilon dn$edges to make it have$\mathcal{P}$. The problem of property testing$\mathcal{P}$was introduced in ... more >>> TR12-022 | 14th March 2012 Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler #### Annotations in Data Streams Revisions: 1 The central goal of data stream algorithms is to process massive streams of data using sublinear storage space. Motivated by work in the database community on outsourcing database and data stream processing, we ask whether the space usage of such algorithms can be further reduced by enlisting a more powerful ... more >>> TR97-045 | 29th September 1997 Oded Goldreich, David Zuckerman #### Another proof that BPP subseteq PH (and more). Comments: 1 We provide another proof of the Sipser--Lautemann Theorem by which$BPP\subseteq MA$($\subseteq PH$). The current proof is based on strong results regarding the amplification of$BPP$, due to Zuckerman. Given these results, the current proof is even simpler than previous ones. Furthermore, extending the proof leads ... more >>> TR06-143 | 15th November 2006 Frank Neumann, Carsten Witt #### Ant Colony Optimization and the Minimum Spanning Tree Problem Ant Colony Optimization (ACO) is a kind of randomized search heuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. ... more >>> TR18-194 | 15th November 2018 Amir Yehudayoff #### Anti-concentration in most directions Revisions: 5 We prove anti-concentration for the inner product of two independent random vectors in the discrete cube. Our results imply Chakrabarti and Regev's lower bound on the randomized communication complexity of the gap-hamming problem. They are also meaningful in the context of randomness extraction. The proof provides a framework for establishing ... more >>> TR13-147 | 25th October 2013 Adam Bouland, Scott Aaronson #### Any Beamsplitter Generates Universal Quantum Linear Optics Revisions: 3 In 1994, Reck et al. showed how to realize any linear-optical unitary transformation using a product of beamsplitters and phaseshifters. Here we show that any single beamsplitter that nontrivially mixes two modes, also densely generates the set of m by m unitary transformations (or orthogonal transformations, in the real case) ... more >>> TR14-061 | 21st April 2014 Raghav Kulkarni, Youming Qiao, Xiaoming Sun #### Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive For a Boolean function$f,$let$D(f)$denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine$f.$In a classic paper, Rivest and Vuillemin \cite{rv} show that any non-constant monotone property$\mathcal{P} : \{0, 1\}^{n \choose 2} \to ... more >>>

TR00-052 | 3rd July 2000
Beate Bollig, Ingo Wegener

#### Approximability and Nonapproximability by Binary Decision Diagrams

Many BDD (binary decision diagram) models are motivated
by CAD applications and have led to complexity theoretical
problems and results. Motivated by applications in genetic
programming Krause, Savick\'y, and Wegener (1999) have shown
that for the inner product function IP$_n$ and the direct
storage access function DSA$_n$ ... more >>>

TR00-091 | 21st December 2000
Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

#### Approximability of Dense Instances of NEAREST CODEWORD Problem

We give a polynomial time approximation scheme (PTAS) for dense
instances of the NEAREST CODEWORD problem.

more >>>

TR03-056 | 29th July 2003
Piotr Berman, Marek Karpinski

#### Approximability of Hypergraph Minimum Bisection

We prove that the problems of minimum bisection on k-uniform
hypergraphs are almost exactly as hard to approximate,
up to the factor k/3, as the problem of minimum bisection
on graphs. On a positive side, our argument gives also the
first approximation ... more >>>

TR06-045 | 13th March 2006
Jan Arpe, Bodo Manthey

#### Approximability of Minimum AND-Circuits

Revisions: 1

Given a set of monomials, the Minimum AND-Circuit problem asks for a
circuit that computes these monomials using AND-gates of fan-in two and
being of minimum size. We prove that the problem is not polynomial time
approximable within a factor of less than 1.0051 unless P = NP, even if
more >>>

TR14-065 | 2nd May 2014
Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska

#### Approximate Counting of Matchings in $(3,3)$-Hypergraphs

We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting ... more >>>

TR02-031 | 30th April 2002
Vikraman Arvind, Venkatesh Raman

#### Approximate Counting small subgraphs of bounded treewidth and related problems

Revisions: 1

We give a randomized approximation algorithm taking
$O(k^{O(k)}n^{b+O(1)})$ time to count the number of copies of a
$k$-vertex graph with treewidth at most $b$ in an $n$ vertex graph
$G$ with approximation ratio $1/k^{O(k)}$ and error probability
inverse exponential in $n$. This algorithm is based on ... more >>>

TR16-121 | 4th August 2016
Mark Bun, Justin Thaler

#### Approximate Degree and the Complexity of Depth Three Circuits

Revisions: 1

Threshold weight, margin complexity, and Majority-of-Threshold circuit size are basic complexity measures of Boolean functions that arise in learning theory, communication complexity, and circuit complexity. Each of these measures might exhibit a chasm at depth three: namely, all polynomial size Boolean circuits of depth two have polynomial complexity under the ... more >>>

TR18-197 | 22nd November 2018
Andrej Bogdanov

#### Approximate degree of AND via Fourier analysis

Revisions: 1

We give a new proof that the approximate degree of the AND function over $n$ inputs is $\Omega(\sqrt{n})$. Our proof extends to the notion of weighted degree, resolving a conjecture of Kamath and Vasudevan. As a consequence we confirm that the approximate degree of any read-once depth-2 De Morgan formula ... more >>>

TR19-082 | 2nd June 2019
Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson

#### Approximate degree, secret sharing, and concentration phenomena

The $\epsilon$-approximate degree $\widetilde{\text{deg}}_\epsilon(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $\epsilon$. The approximate degree of $f$ is at least $k$ iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly ... more >>>

TR19-085 | 7th June 2019
Xuangui Huang, Emanuele Viola

Revisions: 2

We prove that the Or function on $n$ bits can be point-wise approximated with error $\eps$ by a polynomial of degree $O(k)$ and weight $2^{O(n \log (1/\eps)/k)}$, for any $k \geq \sqrt{n \log 1/\eps}$. This result is tight for all $k$. Previous results were either not tight or had $\eps ... more >>> TR12-078 | 14th June 2012 Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev #### Approximate Graph Isomorphism We study optimization versions of Graph Isomorphism. Given two graphs$G_1,G_2$, we are interested in finding a bijection$\pi$from$V(G_1)$to$V(G_2)$that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an$n^{O(\log n)}$time approximation scheme that for any constant ... more >>> TR07-116 | 25th September 2007 Alexander A. Sherstov #### Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions Comments: 1 Let A_1,...,A_n be events in a probability space. The approximate inclusion-exclusion problem, due to Linial and Nisan (1990), is to estimate Pr[A_1 OR ... OR A_n] given Pr[AND_{i\in S}A_i] for all |S|<=k. Kahn et al. (1996) solve this problem optimally for each k. We study the following more general question: ... more >>> TR14-046 | 8th April 2014 Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff #### Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound We consider two known lower bounds on randomized communication complexity: The smooth rectangle bound and the logarithm of the approximate non-negative rank. Our main result is that they are the same up to a multiplicative constant and a small additive term. The logarithm of the nonnegative rank is known to ... more >>> TR10-032 | 19th January 2010 Jack H. Lutz, Brad Shutters #### Approximate Self-Assembly of the Sierpinski Triangle The Tile Assembly Model is a Turing universal model that Winfree introduced in order to study the nanoscale self-assembly of complex (typically aperiodic) DNA crystals. Winfree exhibited a self-assembly that tiles the first quadrant of the Cartesian plane with specially labeled tiles appearing at exactly the positions of points in ... more >>> TR15-046 | 2nd April 2015 Talya Eden, Amit Levi, Dana Ron #### Approximately Counting Triangles in Sublinear Time Comments: 1 We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in two models: Exact counting algorithms, which require reading the entire graph, and streaming algorithms, where the edges are given in a stream and the memory is limited. In this work ... more >>> TR11-171 | 15th December 2011 Piotr Indyk, Reut Levi, Ronitt Rubinfeld #### Approximating and Testing$k$-Histogram Distributions in Sub-linear time Revisions: 1 A discrete distribution$p$, over$[n]$, is a$k$-histogram if its probability distribution function can be represented as a piece-wise constant function with$k$pieces. Such a function is represented by a list of$k$intervals and$k$corresponding values. We consider the following problem: given a collection of samples ... more >>> TR05-073 | 14th July 2005 Oded Goldreich, Dana Ron #### Approximating Average Parameters of Graphs. Inspired by Feige ({\em 36th STOC}, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, ... more >>> TR13-051 | 2nd April 2013 Eric Blais, Li-Yang Tan #### Approximating Boolean functions with depth-2 circuits We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function. In the first direction, our main positive results are the first non-trivial universal upper bounds on ... more >>> TR01-042 | 31st May 2001 Marek Karpinski #### Approximating Bounded Degree Instances of NP-Hard Problems We present some of the recent results on computational complexity of approximating bounded degree combinatorial optimization problems. In particular, we present the best up to now known explicit nonapproximability bounds on the very small degree optimization problems which are of particular importance on the intermediate stages ... more >>> TR12-074 | 12th June 2012 Venkatesan Guruswami, Yuan Zhou #### Approximating Bounded Occurrence Ordering CSPs A theorem of Håstad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most$O(1)$constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive ... more >>> TR06-007 | 23rd November 2005 MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour #### Approximating Buy-at-Bulk$k$-Steiner trees In the buy-at-bulk$k$-Steiner tree (or rent-or-buy$k$-Steiner tree) problem we are given a graph$G(V,E)$with a set of terminals$T\subseteq V$including a particular vertex$s$called the root, and an integer$k\leq |T|$. There are two cost functions on the edges of$G$, a buy cost$b:E\longrightarrow ... more >>>

TR07-027 | 2nd February 2007
Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt

#### Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models

The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical results on this subject.
We consider the approximation ability of randomized search for the class of ... more >>>

TR16-116 | 26th July 2016
Subhash Khot, Rishi Saket

#### Approximating CSPs using LP Relaxation

This paper studies how well the standard LP relaxation approximates a $k$-ary constraint satisfaction problem (CSP) on label set $[L]$. We show that, assuming the Unique Games Conjecture, it achieves an approximation within $O(k^3\cdot \log L)$ of the optimal approximation factor. In particular we prove the following hardness result: let ... more >>>

TR98-048 | 6th July 1998
Irit Dinur, Guy Kindler, Shmuel Safra

#### Approximating CVP to Within Almost Polynomial Factor is NP-Hard

This paper shows finding the closest vector in a lattice
to be NP-hard to approximate to within any factor up to
$2^{(\log{n})^{1-\epsilon}}$ where
$\epsilon = (\log\log{n})^{-\alpha}$
and $\alpha$ is any positive constant $<{1\over 2}$.

more >>>

TR97-004 | 19th February 1997
Marek Karpinski, Alexander Zelikovsky

#### Approximating Dense Cases of Covering Problems

We study dense instances of several covering problems. An instance of
the set cover problem with $m$ sets is dense if there is $\epsilon>0$
such that any element belongs to at least $\epsilon m$ sets. We show
that the dense set cover problem can be approximated with ... more >>>

TR02-018 | 22nd March 2002
Piotr Berman, Marek Karpinski, Yakov Nekrich

#### Approximating Huffman Codes in Parallel

In this paper we present some new results on the approximate parallel
construction of Huffman codes. Our algorithm achieves linear work
and logarithmic time, provided that the initial set of elements
is sorted. This is the first parallel algorithm for that problem
with the optimal time and ... more >>>

TR00-072 | 14th July 2000
Peter Auer, Philip M. Long, Aravind Srinivasan

#### Approximating Hyper-Rectangles: Learning and Pseudo-random Sets

The PAC learning of rectangles has been studied because they have
been found experimentally to yield excellent hypotheses for several
applied learning problems. Also, pseudorandom sets for rectangles
have been actively studied recently because (i) they are a subproblem
common to the derandomization of depth-2 (DNF) ... more >>>

TR10-132 | 18th August 2010
Mahdi Cheraghchi, Johan Hastad, Marcus Isaksson, Ola Svensson

#### Approximating Linear Threshold Predicates

We study constraint satisfaction problems on the domain $\{-1,1\}$, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form $\mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n)$ for some positive integer weights $w_1, \dots, w_n$. Despite their simplicity, current techniques fall short of providing a classification ... more >>>

TR03-032 | 16th April 2003
Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

#### Approximating Longest Directed Path

We investigate the hardness of approximating the longest path and
the longest cycle in directed graphs on $n$ vertices. We show that
neither of these two problems can be polynomial time approximated
within $n^{1-\epsilon}$ for any $\epsilon>0$ unless
$\text{P}=\text{NP}$. In particular, the result holds for
more >>>

TR01-025 | 28th March 2001
Piotr Berman, Marek Karpinski

#### Approximating Minimum Unsatisfiability of Linear Equations

We consider the following optimization problem:
given a system of m linear equations in n variables over a certain field,
a feasible solution is any assignment of values to the variables, and the
minimized objective function is the number of equations that are not
satisfied. For ... more >>>

TR10-124 | 18th July 2010
Zhixiang Chen, Bin Fu

#### Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials

This paper is our third step towards developing a theory of testing monomials in multivariate polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a $\Pi\Sigma\Pi$ polynomial.
We first prove ... more >>>

TR18-097 | 15th May 2018
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

#### Approximating Operator Norms via Generalized Krivine Rounding

We consider the $(\ell_p,\ell_r)$-Grothendieck problem, which seeks to maximize the bilinear form $y^T A x$ for an input matrix $A \in {\mathbb R}^{m \times n}$ over vectors $x,y$ with $\|x\|_p=\|y\|_r=1$. The problem is equivalent to computing the $p \to r^\ast$ operator norm of $A$, where $\ell_{r^*}$ is the dual norm ... more >>>

TR01-038 | 14th May 2001
Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

#### Approximating Schedules for Dynamic Graphs Efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG),
is investigated under graph-theoretic and complexity aspects.
Such graphs embed constructors for parallel programs,
synchronization mechanisms as well as conditional branches.
They are capable of representing all possible executions of a
parallel or distributed program ... more >>>

TR99-002 | 22nd January 1999
Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

#### Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.

returns approximate closest vectors in a lattice, one may find in
polynomial-time approximate shortest vectors in a lattice.
The level of approximation is maintained; that is, for any function
$f$, the following holds:
Suppose that the subroutine, on input a ... more >>>

TR99-016 | 25th April 1999
Irit Dinur

#### Approximating SVP_\infty to within Almost-Polynomial Factors is NP-hard

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate
to within any factor up to $n^{1/\log\log n}$. This improves on the
best previous result \cite{ABSS} that showed quasi-NP-hardness for
smaller factors, namely $2^{\log^{1-\epsilon}n}$ for any constant
$\epsilon>0$. We show a direct reduction from SAT to these
problems, that ... more >>>

TR13-023 | 6th February 2013
Alexander A. Sherstov

#### Approximating the AND-OR Tree

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial
that approximates $f$ within $1/3$ at every point. We prove that the function $\bigwedge_{i=1}^{n}\bigvee_{j=1}^{n}x_{ij}$,
known as the AND-OR tree, has approximate degree $\Omega(n).$ This lower bound is tight
and closes a ... more >>>

TR14-092 | 22nd July 2014
Mark Braverman, Young Kun Ko, Omri Weinstein

#### Approximating the best Nash Equilibrium in $n^{o(\log n)}$-time breaks the Exponential Time Hypothesis

The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game
initiated a quest for finding \emph{approximate} Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory.

We study the computational complexity of finding an $\eps$-approximate Nash equilibrium with good social ... more >>>

TR19-163 | 16th November 2019
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten

We design a nonadaptive algorithm that, given a Boolean function $f\colon \{0,1\}^n \to \{0,1\}$ which is $\alpha$-far from monotone, makes poly$(n, 1/\alpha)$ queries and returns an estimate that, with high probability, is an $\widetilde{O}(\sqrt{n})$-approximation to the distance of $f$ to monotonicity. Furthermore, we show that for any constant $\kappa > ... more >>> TR05-084 | 31st July 2005 Mickey Brautbar, Alex Samorodnitsky #### Approximating the entropy of large alphabets We consider the problem of approximating the entropy of a discrete distribution P on a domain of size q, given access to n independent samples from the distribution. It is known that n > q is necessary, in general, for a good additive estimate of the entropy. A problem of ... more >>> TR12-025 | 23rd March 2012 Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin #### Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques We consider the problem of approximating the minmax value of a multiplayer game in strategic form. We argue that in 3-player games with 0-1 payoffs, approximating the minmax value within an additive constant smaller than$\xi/2$, where$\xi = \frac{3-\sqrt5}{2} \approx 0.382$, is not possible by a polynomial time algorithm. ... more >>> TR07-092 | 10th July 2007 Piotr Berman, Bhaskar DasGupta #### Approximating the Online Set Multicover Problems Via Randomized Winnowing In this paper, we consider the weighted online set k-multicover problem. In this problem, we have an universe V of elements, a family SS of subsets of V with a positive real cost for every S\in SS, and a coverage factor'' (positive integer) k. A subset \{i_0,i_1,\ldots\ \subseteq V of ... more >>> TR97-059 | 22nd December 1997 Jin-Yi Cai, Ajay Nerurkar #### Approximating the SVP to within a factor$\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$is NP-hard under randomized reductions Recently Ajtai showed that to approximate the shortest lattice vector in the$l_2$-norm within a factor$(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large constant$k$, is NP-hard under randomized reductions. We improve this result to show that to approximate a shortest lattice vector within a factor$(1+ \mbox{dim}^{-\epsilon})$, for any$\epsilon>0$, ... more >>> TR07-119 | 5th December 2007 Piotr Berman, Bhaskar DasGupta, Marek Karpinski #### Approximating Transitive Reductions for Directed Networks We consider <i>minimum equivalent digraph</i> (<i>directed network</i>) problem (also known as the <i>strong transitive reduction</i>), its maximum optimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios 1.5 for all the minimization problems and 2 for all the ... more >>> TR06-063 | 1st May 2006 Moses Charikar, Konstantin Makarychev, Yury Makarychev #### Approximation Algorithm for the Max k-CSP Problem We present a c.k/2^k approximation algorithm for the Max k-CSP problem (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an approximation guarantee of Omega(k/(2^k log k)). Our approximation guarantee matches the upper bound of Samorodnitsky and Trevisan up ... more >>> TR00-051 | 14th July 2000 Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas #### Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree$k$-regular graphs for ... more >>> TR05-034 | 5th April 2005 Luca Trevisan #### Approximation Algorithms for Unique Games Revisions: 1 , Comments: 1 Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is intractable to find a solution that satisfies even an ... more >>> TR06-101 | 22nd August 2006 Wenceslas Fernandez de la Vega, Marek Karpinski #### Approximation Complexity of Nondense Instances of MAX-CUT We prove existence of approximation schemes for instances of MAX-CUT with$\Omega(\frac{n^2}{\Delta})$edges which work in$2^{O^\thicksim(\frac{\Delta}{\varepsilon^2})}n^{O(1)}$time. This entails in particular existence of quasi-polynomial approximation schemes (QPTASs) for mildly sparse instances of MAX-CUT with$\Omega(\frac{n^2}{\operatorname{polylog} n})$edges. The result depends on new sampling method for smoothed linear programs that ... more >>> TR96-030 | 31st March 1996 Meera Sitharam #### Approximation from linear spaces and applications to complexity We develop an analytic framework based on linear approximation and point out how a number of complexity related questions -- on circuit and communication complexity lower bounds, as well as pseudorandomness, learnability, and general combinatorics of Boolean functions -- fit neatly into this framework. ... more >>> TR03-022 | 11th April 2003 Piotr Berman, Marek Karpinski, Alexander D. Scott #### Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT We study approximation hardness and satisfiability of bounded occurrence uniform instances of SAT. Among other things, we prove the inapproximability for SAT instances in which every clause has exactly 3 literals and each variable occurs exactly 4 times, and display an explicit ... more >>> TR02-073 | 12th December 2002 Janka Chlebíková, Miroslav Chlebik #### Approximation Hardness for Small Occurrence Instances of NP-Hard Problem The paper contributes to the systematic study (started by Berman and Karpinski) of explicit approximability lower bounds for small occurrence optimization problems. We present parametrized reductions for some packing and covering problems, including 3-Dimensional Matching, and prove the best known inapproximability results even for highly restricted versions of ... more >>> TR01-026 | 3rd April 2001 Piotr Berman, Marek Karpinski #### Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION We consider bounded occurrence (degree) instances of a minimum constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for graphs. MIN-LIN2 is an optimization problem for a given system of linear equations mod 2 to construct a solution that satisfies the minimum number of them. E3-OCC-MIN-E3-LIN2 ... more >>> TR13-066 | 25th April 2013 Marek Karpinski, Richard Schmied #### Approximation Hardness of Graphic TSP on Cubic Graphs We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used ... more >>> TR03-049 | 25th June 2003 Piotr Berman, Marek Karpinski, Alexander D. Scott #### Approximation Hardness of Short Symmetric Instances of MAX-3SAT We prove approximation hardness of short symmetric instances of MAX-3SAT in which each literal occurs exactly twice, and each clause is exactly of size 3. We display also an explicit approximation lower bound for that problem. The bound two on the number ... more >>> TR00-089 | 1st December 2000 Lars Engebretsen, Marek Karpinski #### Approximation Hardness of TSP with Bounded Metrics Revisions: 1 The general asymmetric (and metric) TSP is known to be approximable only to within an O(log n) factor, and is also known to be approximable within a constant factor as soon as the metric is bounded. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics ... more >>> TR18-127 | 9th July 2018 Stasys Jukna, Hannes Seiwert #### Approximation Limitations of Tropical Circuits We develop general lower bound arguments for approximating tropical (min,+) and (max,+) circuits, and use them to prove the first non-trivial, even super-polynomial, lower bounds on the size of such circuits approximating some explicit optimization problems. In particular, these bounds show that the approximation powers of pure dynamic programming algorithms ... more >>> TR00-058 | 1st August 2000 Martin Sauerhoff #### Approximation of Boolean Functions by Combinatorial Rectangles This paper deals with the number of monochromatic combinatorial rectangles required to approximate a Boolean function on a constant fraction of all inputs, where each rectangle may be defined with respect to its own partition of the input variables. The main result of the paper is that the number of ... more >>> TR06-124 | 25th September 2006 Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski #### Approximation of Global MAX-CSP Problems We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>> TR12-110 | 4th September 2012 Siu On Chan #### Approximation Resistance from Pairwise Independent Subgroups We show optimal (up to constant factor) NP-hardness for Max-k-CSP over any domain, whenever k is larger than the domain size. This follows from our main result concerning predicates over abelian groups. We show that a predicate is approximation resistant if it contains a subgroup that is ... more >>> TR12-040 | 17th April 2012 Sangxia Huang #### Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity In this paper, we study the approximability of Max CSP($P$) where$P$is a Boolean predicate. We prove that assuming Khot's$d$-to-1 Conjecture, if the set of accepting inputs of$P$strictly contains all inputs with even (or odd) parity, then it is NP-hard to approximate Max CSP($P$) better than ... more >>> TR08-009 | 7th December 2007 Per Austrin, Elchanan Mossel #### Approximation Resistant Predicates From Pairwise Independence We study the approximability of predicates on$k$variables from a domain$[q]$, and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games Conjecture. Specifically, we show that a predicate$P$is approximation resistant if there exists a balanced pairwise independent distribution over more >>> TR01-065 | 10th August 2001 Chandra Chekuri, Sanjeev Khanna #### Approximation Schemes for Preemptive Weighted Flow Time We present the first approximation schemes for minimizing weighted flow time on a single machine with preemption. Our first result is an algorithm that computes a$(1+\eps)$-approximate solution for any instance of weighted flow time in$O(n^{O(\ln W \ln P/\eps^3)})$time; here$P$is the ratio ... more >>> TR06-074 | 24th April 2006 Shahar Dobzinski, Noam Nisan #### Approximations by Computationally-Efficient VCG-Based Mechanisms We consider computationally-efficient incentive-compatible mechanisms that use the VCG payment scheme, and study how well they can approximate the social welfare in auction settings. We obtain a$2$-approximation for multi-unit auctions, and show that this is best possible, even though from a purely computational perspective an FPTAS exists. For combinatorial ... more >>> TR99-011 | 14th April 1999 Matthias Krause, Petr Savicky, Ingo Wegener #### Approximations by OBDDs and the variable ordering problem Ordered binary decision diagrams (OBDDs) and their variants are motivated by the need to represent Boolean functions in applications. Research concerning these applications leads also to problems and results interesting from theoretical point of view. In this paper, methods from communication complexity and ... more >>> TR19-154 | 6th November 2019 Venkatesan Guruswami, Andrii Riazanov, Min Ye #### Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity Revisions: 1 Let$W$be a binary-input memoryless symmetric (BMS) channel with Shannon capacity$I(W)$and fix any$\alpha > 0$. We construct, for any sufficiently small$\delta > 0$, binary linear codes of block length$O(1/\delta^{2+\alpha})$and rate$I(W)-\delta$that enable reliable communication on$W$with quasi-linear time encoding and decoding. ... more >>> TR09-114 | 13th November 2009 Emanuele Viola #### Are all distributions easy? Complexity theory typically studies the complexity of computing a function$h(x) : \{0,1\}^n \to \{0,1\}^m$of a given input$x$. We advocate the study of the complexity of generating the distribution$h(x)$for uniform$x$, given random bits. Our main results are: \begin{itemize} \item There are explicit$AC^0$circuits of ... more >>> TR15-160 | 30th September 2015 Clement Canonne #### Are Few Bins Enough: Testing Histogram Distributions Revisions: 1 A probability distribution over an ordered universe$[n]=\{1,\dots,n\}$is said to be a$k$-histogram if it can be represented as a piecewise-constant function over at most$k$contiguous intervals. We study the following question: given samples from an arbitrary distribution$D$over$[n]$, one must decide whether$D$is a ... more >>> TR09-089 | 26th September 2009 Guy Rothblum, Salil Vadhan #### Are PCPs Inherent in Efficient Arguments? Starting with Kilian (STOC 92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC 07) raised the question of whether PCPs ... more >>> TR15-152 | 16th September 2015 Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla #### Are Short Proofs Narrow? QBF Resolution is not Simple. The groundbreaking paper Short proofs are narrow - resolution made simple' by Ben-Sasson and Wigderson (J. ACM 2001) introduces what is today arguably the main technique to obtain resolution lower bounds: to show a lower bound for the width of proofs. Another important measure for resolution is space, and in ... more >>> TR09-057 | 23rd June 2009 Yonatan Bilu, Nathan Linial #### Are stable instances easy? We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. The question then arises whether stable instances of NP--hard problems are easier to solve. In particular, whether there exist algorithms that solve correctly ... more >>> TR15-145 | 5th September 2015 Eric Allender, Asa Goodwillie #### Arithmetic circuit classes over Zm We continue the study of the complexity classes VP(Zm) and LambdaP(Zm) which was initiated in [AGM15]. We distinguish between “strict” and “lax” versions of these classes and prove some new equalities and inclusions between these arithmetic circuit classes and various subclasses of ACC^1. more >>> TR13-028 | 14th February 2013 Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma #### Arithmetic Circuit Lower Bounds via MaxRank We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results :$\bullet$As ... more >>> TR09-026 | 17th February 2009 Vikraman Arvind, Pushkar Joglekar #### Arithmetic Circuit Size, Identity Testing, and Finite Automata Let$\F\{x_1,x_2,\cdots,x_n\}$be the noncommutative polynomial ring over a field$\F$, where the$x_i$'s are free noncommuting formal variables. Given a finite automaton$\A$with the$x_i$'s as alphabet, we can define polynomials$\f( mod A)$and$\f(div A)$obtained by natural operations that we ... more >>> TR15-194 | 30th November 2015 Mrinal Kumar, Shubhangi Saraf #### Arithmetic circuits with locally low algebraic rank Revisions: 1 In recent years there has been a flurry of activity proving lower bounds for homogeneous depth-4 arithmetic circuits [GKKS13, FLMS14, KLSS14, KS14c], which has brought us very close to statements that are known to imply VP$\neq$VNP. It is a big question to go beyond homogeneity, and in ... more >>> TR08-048 | 8th April 2008 Meena Mahajan, B. V. Raghavendra Rao #### Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae Functions in arithmetic NC1 are known to have equivalent constant width polynomial degree circuits, but the converse containment is unknown. In a partial answer to this question, we show that syntactic multilinear circuits of constant width and polynomial degree can be depth-reduced, though the resulting circuits need not be ... more >>> TR08-062 | 11th June 2008 Manindra Agrawal, V Vinay #### Arithmetic Circuits: A Chasm at Depth Four We show that proving exponential lower bounds on depth four arithmetic circuits imply exponential lower bounds for unrestricted depth arithmetic circuits. In other words, for exponential sized circuits additional depth beyond four does not help. We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>> TR13-026 | 11th February 2013 Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi #### Arithmetic circuits: A chasm at depth three Revisions: 1 We show that, over$\mathbb{C}$, if an$n$-variate polynomial of degree$d = n^{O(1)}$is computable by an arithmetic circuit of size$s$(respectively by an algebraic branching program of size$s$) then it can also be computed by a depth three circuit (i.e. a$\Sigma \Pi \Sigma$-circuit) of size ... more >>> TR99-008 | 19th March 1999 Eric Allender, Vikraman Arvind, Meena Mahajan #### Arithmetic Complexity, Kleene Closure, and Formal Power Series Revisions: 1 , Comments: 1 The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC^1 and GapL. More precisely, we apply the Kleene closure of languages and the formal power series operations of inversion and root ... more >>> TR15-061 | 14th April 2015 Benny Applebaum, Jonathan Avron, Christina Brzuska #### Arithmetic Cryptography Revisions: 1 We study the possibility of computing cryptographic primitives in a fully-black-box arithmetic model over a finite field F. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits which make only a ... more >>> TR01-095 | 12th November 2001 Hubie Chen #### Arithmetic Versions of Constant Depth Circuit Complexity Classes The boolean circuit complexity classes AC^0 \subseteq AC^0[m] \subseteq TC^0 \subseteq NC^1 have been studied intensely. Other than NC^1, they are defined by constant-depth circuits of polynomial size and unbounded fan-in over some set of allowed gates. One reason for interest in these classes is that they contain the ... more >>> TR07-087 | 11th July 2007 Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao #### Arithmetizing classes around NC^1 and L The parallel complexity class NC^1 has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. \cite{CMTV} considered arithmetizations of two of these classes, #NC^1 and #BWBP. We further this study to include arithmetization of other classes. In particular, we show that counting paths ... more >>> TR09-055 | 10th June 2009 Venkatesan Chakaravarthy, Sambuddha Roy #### Arthur and Merlin as Oracles We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class. Our main results are the following: (i)$BPP^{NP}_{||} \subseteq P^{prAM}_{||}$; (ii)$S_2^p \subseteq P^{prAM}$. In addition to providing new upperbounds for the classes$S_2^p$and$BPP^{NP}_{||}$, these results are interesting ... more >>> TR97-054 | 17th November 1997 Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolay Vereshchagin #### Arthur-Merlin Games in Boolean Decision Trees It is well known that probabilistic boolean decision trees cannot be much more powerful than deterministic ones (N.~Nisan, SIAM Journal on Computing, 20(6):999--1007, 1991). Motivated by a question if randomization can significantly speed up a nondeterministic computation via a boolean decision tree, we address structural properties of Arthur-Merlin games ... more >>> TR13-020 | 2nd February 2013 Tom Gur, Ran Raz #### Arthur-Merlin Streaming Complexity We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical$\mathcal{AM}$streaming algorithm for a wide class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it. ... more >>> TR09-001 | 26th November 2008 Venkatesan Guruswami #### Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes Algebraic codes that achieve list decoding capacity were recently constructed by a careful folding'' of the Reed-Solomon code. The low-degree'' nature of this folding operation was crucial to the list decoding algorithm. We show how such folding schemes conducive to list decoding arise out of the Artin-Frobenius automorphism at primes ... more >>> TR13-105 | 29th July 2013 Raghu Meka, Avi Wigderson #### Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique Revisions: 1 Finding cliques in random graphs and the closely related planted'' clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for t = ... more >>> TR03-038 | 15th May 2003 Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor #### Asymmetric k-center is log^*n-hard to Approximate We show that the asymmetric$k$-center problem is$\Omega(\log^* n)$-hard to approximate unless${\rm NP} \subseteq {\rm DTIME}(n^{poly(\log \log n)})$. Since an$O(\log^* n)$-approximation algorithm is known for this problem, this essentially resolves the approximability of this problem. This is the first natural problem whose approximability threshold does not polynomially ... more >>> TR99-048 | 7th December 1999 Beate Bollig, Ingo Wegener #### Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems Ordered binary decision diagrams (OBDDs) are nowadays the most common dynamic data structure or representation type for Boolean functions. Among the many areas of application are verification, model checking, and computer aided design. For many functions it is easy to estimate the OBDD ... more >>> TR95-026 | 7th June 1995 Claus-Peter Schnorr, Horst Helmut Hoerner #### Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction We introduce new algorithms for lattice basis reduction that are improvements of the LLL-algorithm. We demonstrate the power of these algorithms by solving random subset sum problems of arbitrary density with 74 and 82 many weights, by breaking the Chor-Rivest cryptoscheme in dimensions 103 and 151 ... more >>> TR98-076 | 13th November 1998 Nader Bshouty, Jeffrey J. Jackson, Christino Tamon #### Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution We study attribute efficient learning in the PAC learning model with membership queries. First, we give an {\it attribute efficient} PAC-learning algorithm for DNF with membership queries under the uniform distribution. Previous algorithms for DNF have sample size polynomial in the number of attributes$n$. Our algorithm is the first ... more >>> TR12-056 | 1st May 2012 Rocco Servedio, Li-Yang Tan, Justin Thaler #### Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions Revisions: 1 We study the challenging problem of learning decision lists attribute-efficiently, giving both positive and negative results. Our main positive result is a new tradeoff between the running time and mistake bound for learning length-$k$decision lists over$n$Boolean variables. When the allowed running time is relatively high, our new ... more >>> TR13-188 | 13th December 2013 Christian Glaßer, Maximilian Witek #### Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain: - For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible. - For P, the delta-levels of ... more >>> TR13-047 | 27th March 2013 Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek #### Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions Comments: 1 We investigate the autoreducibility and mitoticity of complete sets for several classes with respect to different polynomial-time and logarithmic-space reducibility notions. Previous work in this area focused on polynomial-time reducibility notions. Here we obtain new mitoticity and autoreducibility results for the classes EXP and NEXP with respect to some restricted ... more >>> TR16-012 | 21st January 2016 John Hitchcock, Hadi Shafei #### Autoreducibility of NP-Complete Sets We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following: - For every$k \geq 2$, there is a$k$-T-complete set for NP that is$k$-T autoreducible, but is not$k$-tt autoreducible ... more >>> TR05-011 | 21st December 2004 Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang #### Autoreducibility, Mitoticity, and Immunity We show the following results regarding complete sets: NP-complete sets and PSPACE-complete sets are many-one autoreducible. Complete sets of any level of PH, MODPH, or the Boolean hierarchy over NP are many-one autoreducible. EXP-complete sets are many-one mitotic. NEXP-complete sets are weakly many-one mitotic. PSPACE-complete sets are weakly Turing-mitotic. ... more >>> TR19-079 | 28th May 2019 Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka #### Average Bias and Polynomial Sources Revisions: 2 We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution$Z$over$\{0,1\}^n$, its average bias is:$b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|$. A source with average bias at most$2^{-k}$has min-entropy at least$k$, and ... more >>> TR13-054 | 4th April 2013 Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook #### Average Case Lower Bounds for Monotone Switching Networks Revisions: 1 An approximate computation of a Boolean function by a circuit or switching network is a computation which computes the function correctly on the majority of the inputs (rather than on all inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many subareas ... more >>> TR95-019 | 14th April 1995 Jin-Yi Cai, Alan L. Selman #### Average time complexity classes TR06-073 | 8th June 2006 Andrej Bogdanov, Luca Trevisan #### Average-Case Complexity Revisions: 1 We survey the theory of average-case complexity, with a focus on problems in NP. more >>> TR03-031 | 8th April 2003 Birgit Schelm #### Average-Case Complexity Theory of Approximation Problems Both average-case complexity and the study of the approximability properties of NP-optimization problems are well established and active fields of research. By applying the notion of average-case complexity to approximation problems we provide a formal framework that allows the classification of NP-optimization problems according to their average-case approximability. Thus, known ... more >>> TR17-039 | 28th February 2017 Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan #### Average-Case Fine-Grained Hardness We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., ... more >>> TR98-037 | 29th June 1998 Johannes Köbler, Rainer Schuler #### Average-Case Intractability vs. Worst-Case Intractability We use the assumption that all sets in NP (or other levels of the polynomial-time hierarchy) have efficient average-case algorithms to derive collapse consequences for MA, AM, and various subclasses of P/poly. As a further consequence we show for C in {P(PP), PSPACE} that ... more >>> TR18-029 | 9th February 2018 Neeraj Kayal, vineet nair, Chandan Saha #### Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs Revisions: 2 Let us call a matrix$X$as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix$F$as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to ... more >>> TR15-191 | 26th November 2015 Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan #### Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is \epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at most n^{1+\epsilon_d} ... more >>> TR12-062 | 17th May 2012 Ilan Komargodski, Ran Raz #### Average-Case Lower Bounds for Formula Size Revisions: 2 We give an explicit function$h:\{0,1\}^n\to\{0,1\}$such that any deMorgan formula of size$O(n^{2.499})$agrees with$h$on at most$\frac{1}{2} + \epsilon$fraction of the inputs, where$\epsilon$is exponentially small (i.e.$\epsilon = 2^{-n^{\Omega(1)}}$). Previous lower bounds for formula size were obtained for exact computation. The same ... more >>> TR11-006 | 20th January 2011 Sebastian Müller, Iddo Tzameret #### Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas Revisions: 1 Separating different propositional proof systems---that is, demonstrating that one proof system cannot efficiently simulate another proof system---is one of the main goals of proof complexity. Nevertheless, all known separation results between non-abstract proof systems are for specific families of hard tautologies: for what we know, in the average case all ... more >>> TR10-055 | 31st March 2010 Eric Allender #### Avoiding Simplicity is Complex Revisions: 2 It is a trivial observation that every decidable set has strings of length$n$with Kolmogorov complexity$\log n + O(1)$if it has any strings of length$n\$ at all. Things become much more interesting when one asks whether a similar property holds when one
considers *resource-bounded* Kolmogorov complexity. ... more >>>

ISSN 1433-8092 | Imprint