Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2014:
All reports in year 2014:
TR14-001 | 4th January 2014
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

#### Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

In this paper we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a polynomial $f(X_1,\ldots,X_n)$, the task of computing arithmetic circuits for the factors ... more >>>

TR14-002 | 8th January 2014
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

#### Direct Sum Testing

Revisions: 1

For a string $a \in \{0,1\}^n$ its $k$-fold direct sum encoding is a function $f_a$ that takes as input sets $S \subseteq [n]$ of
size $k$ and outputs $f_a(S) = \sum_{i \in S} a_i$.
In this paper we are interested in the Direct Sum Testing Problem,
where we are given ... more >>>

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

#### Testing Equivalence of Polynomials under Shifts

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

TR14-004 | 30th November 2013

#### On $r$-Simple $k$-Path

An $r$-simple $k$-path is a {path} in the graph of length $k$ that
passes through each vertex at most $r$ times. The \simpath{r}{k}
problem, given a graph $G$ as input, asks whether there exists an
$r$-simple $k$-path in $G$. We first show that this problem is
NP-Complete. We then show ... 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 >>>

TR14-006 | 16th January 2014
Venkatesan Guruswami, Euiwoong Lee

#### Inapproximability of Feedback Vertex Set for Bounded Length Cycles

Revisions: 1

The Feedback Vertex Set problem (FVS), where the goal is to find a small subset of vertices that intersects every cycle in an input directed graph, is among the fundamental problems whose approximability is not well-understood. One can efficiently find an $\widetilde{O}(\log n)$ factor approximation, and while a constant-factor approximation ... more >>>

TR14-007 | 17th January 2014
Mark Braverman, Klim Efremenko

#### List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

In this paper we extend the notion of list decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient
to a noise rate of up to $1/2-\varepsilon$, ... more >>>

TR14-008 | 20th January 2014
Vinodchandran Variyam

The graph reachability problem, the computational task of deciding whether there is a path between two given nodes in a graph is the canonical problem for studying space bounded computations. Three central open questions regarding the space complexity of the reachability problem over directed graphs are: (1) improving Savitch's $O(\log^2 ... more >>> TR14-009 | 21st January 2014 Alexander A. Sherstov #### Breaking the Minsky-Papert Barrier for Constant-Depth Circuits The threshold degree of a Boolean function$f$is the minimum degree of a real polynomial$p$that represents$f$in sign:$f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth$\{\wedge,\vee\}$-circuit in$n$variables with threshold degree$\Omega(n^{1/3}).$This bound underlies ... more >>> 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 >>> TR14-011 | 22nd January 2014 Dmitry Gavinsky, Pavel Pudlak #### Partition Expanders We introduce a new concept, which we call partition expanders. The basic idea is to study quantitative properties of graphs in a slightly different way than it is in the standard definition of expanders. While in the definition of expanders it is required that the number of edges between any ... 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 >>> TR14-013 | 30th January 2014 Mark Braverman, Kanika Pasricha #### The computational hardness of pricing compound options It is generally assumed that you can make a financial asset out of any underlying event or combination thereof, and then sell a security. We show that while this is theoretically true from the financial engineering perspective, compound securities might be intractable to price. Even given no information asymmetries, or ... more >>> TR14-014 | 28th January 2014 Olaf Beyersdorff, Leroy Chew #### The Complexity of Theorem Proving in Circumscription and Minimal Entailment Circumscription is one of the main formalisms for non-monotonic reasoning. It uses reasoning with minimal models, the key idea being that minimal models have as few exceptions as possible. In this contribution we provide the first comprehensive proof-complexity analysis of different proof systems for propositional circumscription. In particular, we investigate ... more >>> TR14-015 | 24th January 2014 Jack H. Lutz, Neil Lutz #### Lines Missing Every Random Point Revisions: 1 This paper proves that there is, in every direction in Euclidean space, a line that misses every computably random point. Our proof of this fact shows that a famous set constructed by Besicovitch in 1964 has computable measure 0. more >>> TR14-016 | 16th January 2014 Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz #### The Complexity of Debate Checking We study probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. We consider debates of partial and zero information, where the prover is prevented from seeing some or all of ... more >>> TR14-017 | 9th February 2014 Eli Ben-Sasson, Emanuele Viola #### Short PCPs with projection queries We construct a PCP for NTIME(2$^n$) with constant soundness,$2^n \poly(n)$proof length, and$\poly(n)$queries where the verifier's computation is simple: the queries are a projection of the input randomness, and the computation on the prover's answers is a 3CNF. The previous upper bound for these two computations was more >>> TR14-018 | 13th February 2014 Arnab Bhattacharyya #### Polynomial decompositions in polynomial time Fix a prime$p$. Given a positive integer$k$, a vector of positive integers${\bf \Delta} = (\Delta_1, \Delta_2, \dots, \Delta_k)$and a function$\Gamma: \mathbb{F}_p^k \to \F_p$, we say that a function$P: \mathbb{F}_p^n \to \mathbb{F}_p$is$(k,{\bf \Delta},\Gamma)$-structured if there exist polynomials$P_1, P_2, \dots, P_k:\mathbb{F}_p^n \to \mathbb{F}_p$... more >>> TR14-019 | 14th February 2014 Parikshit Gopalan, Amir Yehudayoff #### Inequalities and tail bounds for elementary symmetric polynomials This paper studies the elementary symmetric polynomials$S_k(x)$for$x \in \mathbb{R}^n$. We show that if$|S_k(x)|,|S_{k+1}(x)|$are small for some$k>0$then$|S_\ell(x)|$is also small for all$\ell > k$. We use this to prove probability tail bounds for the symmetric polynomials when the inputs are only$t$-wise ... more >>> TR14-020 | 18th February 2014 Pavel Hrubes, Anup Rao #### Circuits with Medium Fan-In Revisions: 1 We consider boolean circuits in which every gate may compute an arbitrary boolean function of$k$other gates, for a parameter$k$. We give an explicit function$f:\bits^n \rightarrow \bits$that requires at least$\Omega(\log^2 n)$non-input gates when$k = 2n/3$. When the circuit is restricted to being depth ... more >>> TR14-021 | 18th February 2014 Clement Canonne, Ronitt Rubinfeld #### Testing probability distributions underlying aggregated data In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution$D$over$[n]$. More precisely, we define both the dual and extended ... more >>> TR14-022 | 19th February 2014 Shay Moran, Makrand Sinha, Amir Yehudayoff #### Fooling Pairs in Randomized Communication Complexity Revisions: 1 Fooling pairs are one of the standard methods for proving lower bounds for deterministic two-player communication complexity. We study fooling pairs in the context of randomized communication complexity. We show that every fooling pair induces far away distributions on transcripts of private-coin protocols. We then conclude that the private-coin randomized ... more >>> TR14-023 | 19th February 2014 Gil Cohen, Anat Ganor, Ran Raz #### Two Sides of the Coin Problem Revisions: 1 In the Coin Problem, one is given n independent flips of a coin that has bias$\beta > 0$towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply ... more >>> TR14-024 | 19th February 2014 Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider #### 0-1 Integer Linear Programming with a Linear Number of Constraints We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time$2^{(1-\text{poly}(1/c))n}$where$n$is the number of variables and$cn$is the number of constraints. The key ... more >>> TR14-025 | 25th February 2014 Oded Goldreich, Tom Gur, Ilan Komargodski #### Strong Locally Testable Codes with Relaxed Local Decoders Locally testable codes (LTCs) are error-correcting codes that admit very efficient codeword tests. An LTC is said to be strong if it has a proximity-oblivious tester; that is, a tester that makes only a constant number of queries and reject non-codewords with probability that depends solely on their distance from ... more >>> TR14-026 | 27th February 2014 Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf #### Lower Bounds for Approximate LDCs We study an approximate version of$q$-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A$q$-query$(\alpha,\delta)$-approximate LDC is a set$V$of$n$points in$\mathbb{R}^d$so that, for each$i \in [d]$there are$\Omega(\delta n)$... 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 >>> TR14-028 | 27th February 2014 Vikraman Arvind, S Raja #### The Complexity of Two Register and Skew Arithmetic Computation We study two register arithmetic computation and skew arithmetic circuits. Our main results are the following: (1) For commutative computations, we show that an exponential circuit size lower bound for a model of 2-register straight-line programs (SLPs) which is a universal model of computation (unlike width-2 algebraic branching programs that ... more >>> TR14-029 | 4th March 2014 Oded Goldreich, Dana Ron #### On Learning and Testing Dynamic Environments Revisions: 3 We initiate a study of learning and testing dynamic environments, focusing on environment that evolve according to a fixed local rule. The (proper) learning task consists of obtaining the initial configuration of the environment, whereas for non-proper learning it suffices to predict its future values. The testing task consists of ... 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 >>> TR14-031 | 16th February 2014 Joao Marques-Silva, Mikolas Janota #### On the Query Complexity of Selecting Few Minimal Sets Propositional Satisfiability (SAT) solvers are routinely used for solving many function problems. A natural question that has seldom been addressed is: what is the best worst-case number of calls to a SAT solver for solving some target function problem? This paper develops tighter upper bounds on the query complexity of more >>> TR14-032 | 8th March 2014 Olaf Beyersdorff, Leroy Chew #### Tableau vs. Sequent Calculi for Minimal Entailment In this paper we compare two proof systems for minimal entailment: a tableau system OTAB and a sequent calculus MLK, both developed by Olivetti (J. Autom. Reasoning, 1992). Our main result shows that OTAB-proofs can be efficiently translated into MLK-proofs, i.e., MLK p-simulates OTAB. The simulation is technically very involved ... more >>> TR14-033 | 10th March 2014 Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen #### Candidate Weak Pseudorandom Functions in$\mathrm{AC}0 \circ \mathrm{MOD}2$Revisions: 1 Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class$\mathrm{AC}^0( \mathrm{MOD}_2)$. Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications. We study the minimal complexity requirements for ... more >>> TR14-034 | 3rd March 2014 Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram #### On the complexity of trial and error for constraint satisfaction problems In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if ... more >>> TR14-035 | 13th March 2014 Diptarka Chakraborty, A. Pavan, Raghunath Tewari, Vinodchandran Variyam, Lin Yang #### New Time-Space Upperbounds for Directed Reachability in High-genus and$H$-minor-free Graphs. We obtain the following new simultaneous time-space upper bounds for the directed reachability problem. (1) A polynomial-time,$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus$g$. (2) A polynomial-time,$\tilde{O}(n^{2/3})$-space algorithm for all$H$-minor-free graphs given the tree decomposition, and (3) for$K_{3, 3}$-free and ... more >>> TR14-036 | 8th March 2014 Mikolas Janota, Leroy Chew, Olaf Beyersdorff #### On Unification of QBF Resolution-Based Calculi Revisions: 1 Several calculi for quantified Boolean formulas (QBFs) exist, but relations between them are not yet fully understood. This paper defines a novel calculus, which is resolution-based and enables unification of the principal existing resolution-based QBF calculi, namely Q-resolution, long-distance Q-resolution and the expansion-based calculus ... more >>> TR14-037 | 21st March 2014 Hamidreza Jahanjou, Eric Miles, Emanuele Viola #### Succinct and explicit circuits for sorting and connectivity We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$circuits ... more >>> TR14-038 | 24th March 2014 Ilario Bonacina, Nicola Galesi, Neil Thapen #### Total space in resolution Revisions: 1 We show$\Omega(n^2)$lower bounds on the total space used in resolution refutations of random$k$-CNFs over$n$variables, and of the graph pigeonhole principle and the bit pigeonhole principle for$n$holes. This answers the long-standing open problem of whether there are families of$k$-CNF formulas of size$O(n)$... more >>> TR14-039 | 28th March 2014 Andrzej Lingas #### Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps :-) Revisions: 1 We observe that if we allow for the use of division and the floor function besides multiplication, addition and subtraction then we can compute the arithmetic convolution of two n-dimensional integer vectors in O(n) steps and perform the arithmetic matrix multiplication of two integer n times n matrices ... more >>> TR14-040 | 30th March 2014 Hamed Hatami, Pooya Hatami, Shachar Lovett #### General systems of linear forms: equidistribution and true complexity Revisions: 1 The densities of small linear structures (such as arithmetic progressions) in subsets of Abelian groups can be expressed as certain analytic averages involving linear forms. Higher-order Fourier analysis examines such averages by approximating the indicator function of a subset by a function of bounded number of polynomials. Then, to approximate ... more >>> TR14-041 | 31st March 2014 Shachar Lovett #### Recent advances on the log-rank conjecture in communication complexity The log-rank conjecture is one of the fundamental open problems in communication complexity. It speculates that the deterministic communication complexity of any two-party function is equal to the log of the rank of its associated matrix, up to polynomial factors. Despite much research, we still know very little about this ... more >>> TR14-042 | 2nd April 2014 Kashyap Dixit, Deeparnab Chakrabarty, Madhav Jha, C. Seshadhri #### Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the {\em uniform} distribution on the domain. ... more >>> TR14-043 | 2nd April 2014 Venkatesan Guruswami, Euiwoong Lee #### Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs Consider a$K$-uniform hypergraph$H = (V,E)$. A coloring$c : V \rightarrow \{1, 2, \dots, k \}$with$k$colors is rainbow if every hyperedge$e$contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A ... more >>> TR14-044 | 2nd April 2014 Daniel Dewey #### Additively efficient universal computers 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 >>> TR14-045 | 7th April 2014 Mrinal Kumar, Shubhangi Saraf #### On the power of homogeneous depth 4 arithmetic circuits Revisions: 2 We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in$VP$. Our results hold for the {\it Iterated Matrix Multiplication} polynomial - in particular we show that any homogeneous depth 4 circuit computing the$(1,1)$entry in the product of$n$... 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 >>> 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 >>> TR14-048 | 10th April 2014 Avishay Tal #### Shrinkage of De Morgan Formulae from Quantum Query Complexity Revisions: 1 We give a new and improved proof that the shrinkage exponent of De Morgan formulae is$2$. Namely, we show that for any Boolean function$f: \{-1,1\}^n \to \{-1,1\}$, setting each variable out of$x_1, \ldots, x_n$with probability$1-p$to a randomly chosen constant, reduces the expected formula size ... more >>> TR14-049 | 11th April 2014 Anat Ganor, Gillat Kol, Ran Raz #### Exponential Separation of Information and Communication Revisions: 1 We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity$\leq O(k)$, and distributional communication complexity$\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of ... more >>> TR14-050 | 21st March 2014 Edward Hirsch, Dmitry Sokolov #### On the probabilistic closure of the loose unambiguous hierarchy Revisions: 1 Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy$prUH_\bullet$with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that ... more >>> TR14-051 | 12th April 2014 Subhash Khot, Rishi Saket #### Hardness of Coloring$2$-Colorable$12$-Uniform Hypergraphs with$2^{(\log n)^{\Omega(1)}}$Colors We show that it is quasi-NP-hard to color$2$-colorable$12$-uniform hypergraphs with$2^{(\log n)^{\Omega(1) }}$colors where$n$is the number of vertices. Previously, Guruswami et al. [GHHSV14] showed that it is quasi-NP-hard to color$2$-colorable$8$-uniform hypergraphs with$2^{2^{\Omega(\sqrt{\log \log n})}}$colors. Their result is obtained by composing a ... more >>> TR14-052 | 14th April 2014 Joshua Grochow, Toniann Pitassi #### Circuit complexity, proof complexity, and polynomial identity testing We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>> TR14-053 | 15th April 2014 Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman #### Computing with a full memory: Catalytic space Revisions: 1 We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state ... more >>> TR14-054 | 16th April 2014 Dana Moshkovitz #### Parallel Repetition of Fortified Games Revisions: 2 The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G^k in terms of the value of the game G and the number of repetitions k. Contrary to what one might have guessed, the value of G^k is not val(G)^k, but rather a more complicated ... more >>> TR14-055 | 17th April 2014 Mika Göös, Thomas Watson #### Communication Complexity of Set-Disjointness for All Probabilities Revisions: 1 We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions ... more >>> TR14-056 | 18th April 2014 Zeev Dvir, Rafael Mendes de Oliveira #### Factors of Sparse Polynomials are Sparse Revisions: 1 , Comments: 1 We show that if$f(x_1,\ldots,x_n)$is a polynomial with$s$monomials and$g(x_1,\ldots,x_n)$divides$f$then$g$has at most$\max(s^{O(\log s \log\log s)},d^{O(\log d)})$monomials, where$d$is a bound on the individual degrees of$f$. This answers a question of von zur Gathen and Kaltofen (JCSS ... more >>> TR14-057 | 17th April 2014 Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar #### Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness Revisions: 3 In this paper, we propose a quantification of distributions on a set of strings, in terms of how close to pseudorandom the distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences first introduced by Lutz \cite{Lutz:DISS}. We show that this definition ... more >>> TR14-058 | 20th April 2014 Ilya Volkovich #### On Learning, Lower Bounds and (un)Keeping Promises We extend the line of research initiated by Fortnow and Klivans \cite{FortnowKlivans09} that studies the relationship between efficient learning algorithms and circuit lower bounds. In \cite{FortnowKlivans09}, it was shown that if a Boolean circuit class$\mathcal{C}$has an efficient \emph{deterministic} exact learning algorithm, (i.e. an algorithm that uses membership and ... more >>> TR14-059 | 21st April 2014 Boaz Barak, David Steurer #### Sum-of-squares proofs and the quest toward optimal algorithms Revisions: 2 In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible ... more >>> TR14-060 | 21st April 2014 Anup Rao, Amir Yehudayoff #### Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness Revisions: 1 We show that the deterministic multiparty communication complexity of set disjointness for$k$parties on a universe of size$n$is$\Omega(n/4^k)$. We also simplify Sherstov's proof showing an$\Omega(\sqrt{n}/(k2^k))$lower bound for the randomized communication complexity of set disjointness. 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 >>>

TR14-062 | 22nd March 2014
Alexander Kozachinsky

#### On the role of private coins in unbounded-round Information Complexity

We prove a version of "Reversed Newman Theorem" in context of information complexity: every private-coin communication protocol with information complexity $I$ and communication complexity $C$ can be replaced by public-coin protocol with the same behavior so that it's information complexity does not exceed $O\left(\sqrt{IC}\right)$. This result holds for unbounded-round communication ... more >>>

TR14-063 | 23rd April 2014

#### Embedding Hard Learning Problems into Gaussian Space

We give the first representation-independent hardness result for agnostically learning halfspaces with respect to the Gaussian distribution. We reduce from the problem of learning sparse parities with noise with respect to the uniform distribution on the hypercube (sparse LPN), a notoriously hard problem in computer science and show that ... more >>>

TR14-064 | 24th April 2014

#### The Power of Super-logarithmic Number of Players

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

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

TR14-066 | 17th April 2014
Suguru Tamaki, Yuichi Yoshida

#### Robust Approximation of Temporal CSP

A temporal constraint language $\Gamma$ is a set of relations with first-order definitions in $({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from $\Gamma$. CSP($\Gamma$) admits robust approximation if, for any $\varepsilon \geq 0$, given a $(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an ... more >>>

TR14-067 | 4th May 2014
Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

#### Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>

TR14-068 | 5th May 2014
Eric Allender, Bireswar Das

#### Zero Knowledge and Circuit Minimization

Revisions: 1

We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is
efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RP^MCSP.

This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these ... more >>>

TR14-069 | 5th May 2014
Shashank Agrawal, Divya Gupta, Hemanta Maji, Omkant Pandey, Manoj Prabhakaran

#### Explicit Non-Malleable Codes Resistant to Permutations

The notion of non-malleable codes was introduced as a relaxation of standard error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value.

In the information theoretic setting, although existence of such codes for various ... more >>>

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

#### The Complexity of Geometric Graph Isomorphism

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

TR14-071 | 7th May 2014
Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

#### O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem

We show an O(sqrt(n))-space and polynomial-time algorithm for solving the planar directed graph reachability problem. Imai et al. showed in CCC 2013 that the problem is solvable in O(n^{1/2+eps})-space and polynomial-time by using separators for planar graphs, and it has been open whether the space bound can be improved to ... more >>>

TR14-072 | 29th April 2014
Sajin Koroth, Jayalal Sarma

#### Depth Lower Bounds against Circuits with Sparse Orientation

Revisions: 1

We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function $f$ is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit computing $f$. We prove trade-off results between the depth and the weight/structure ... more >>>

TR14-073 | 14th May 2014
Shachar Lovett, Cris Moore, Alexander Russell

#### Group representations that resist random sampling

Revisions: 1

We show that there exists a family of groups $G_n$ and nontrivial irreducible representations $\rho_n$ such that, for any constant $t$, the average of $\rho_n$ over $t$ uniformly random elements $g_1, \ldots, g_t \in G_n$ has operator norm $1$ with probability approaching 1 as $n \rightarrow \infty$. More quantitatively, we ... more >>>

TR14-074 | 14th May 2014

#### Topology matters in communication

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

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

TR14-076 | 27th May 2014
Thomas Steinke

#### Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs

Revisions: 1

We present an explicit pseudorandom generator for oblivious, read-once, width-$3$ branching programs, which can read their input bits in any order. The generator has seed length $\tilde{O}( \log^3 n ).$ The previously best known seed length for this model is $n^{1/2+o(1)}$ due to Impagliazzo, Meka, and Zuckerman (FOCS '12). Our ... more >>>

TR14-077 | 2nd June 2014
Andris Ambainis, Jevgenijs Vihrovs

#### Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma

Revisions: 2

We study the structure of sets $S\subseteq\{0, 1\}^n$ with small sensitivity. The well-known Simon's lemma says that any $S\subseteq\{0, 1\}^n$ of sensitivity $s$ must be of size at least $2^{n-s}$. This result has been useful for proving lower bounds on sensitivity of Boolean functions, with applications to the theory of ... more >>>

TR14-078 | 7th June 2014
Mika Göös, Toniann Pitassi, Thomas Watson

#### Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication

We study whether information complexity can be used to attack the long-standing open problem of proving lower bounds against Arthur--Merlin (AM) communication protocols. Our starting point is to show that---in contrast to plain randomized communication complexity---every boolean function admits an AM communication protocol where on each yes-input, the distribution of ... more >>>

TR14-079 | 11th June 2014
Simon Straub, Thomas Thierauf, Fabian Wagner

#### Counting the Number of Perfect Matchings in $K_5$-free Graphs

Counting the number of perfect matchings in arbitrary graphs is a $\#$P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for $K_{3,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>>

TR14-080 | 11th June 2014
Stasys Jukna

#### Lower Bounds for Tropical Circuits and Dynamic Programs

Revisions: 1

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower ... more >>>

TR14-081 | 13th June 2014
Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, Marc Vinyals

#### From Small Space to Small Width in Resolution

In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of CNF formulas is always an upper bound on the width needed to refute them. Their proof is beautiful but somewhat mysterious in that it relies heavily on tools ... more >>>

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

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

Revisions: 3

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

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

#### The Computational Benefit of Correlated Instances

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

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

TR14-085 | 29th June 2014
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

#### Hitting-sets for ROABP and Sum of Set-Multilinear circuits

We give a $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best time-complexity known for this class was $n^{O(\log^2 n)}$ due to Forbes-Saptharishi-Shpilka (STOC 2014), and that too only for multilinear ROABP. We get rid of their ... more >>>

TR14-086 | 11th July 2014
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

#### Verifiable Stream Computation and Arthur–Merlin Communication

In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling ... more >>>

TR14-087 | 12th July 2014
Abhishek Bhowmick, Shachar Lovett

#### List decoding Reed-Muller codes over small fields

Revisions: 1

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes.

Fix a finite field $\mathbb{F}$. ... more >>>

TR14-088 | 13th July 2014
Swagato Sanyal

#### Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity

We prove that the Fourier dimension of any Boolean function with
Fourier sparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof
method yields an improved bound of $\widetilde{O}(\sqrt{s})$
assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every
Boolean function of sparsity $s$ there is an affine subspace of
more >>>

TR14-089 | 16th July 2014
Neeraj Kayal, Chandan Saha

#### Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin

Revisions: 1

Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field $\mathbb{F}$ of characteristic zero. We resolve this problem by proving a $N^{\Omega(\frac{d}{\tau})}$ lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin ... more >>>

TR14-090 | 11th July 2014
Justin Thaler

#### Semi-Streaming Algorithms for Annotated Graph Streams

Revisions: 2

Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require $\Omega(n^2)$ space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of ... more >>>

TR14-091 | 22nd July 2014
Ryan O'Donnell, A. C. Cem Say

#### One time-travelling bit is as good as logarithmically many

Revisions: 1

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On ... 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 >>>

TR14-093 | 22nd July 2014
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

#### Resolution complexity of perfect mathcing principles for sparse graphs

The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph $G_n$ such that the resolution complexity of the perfect matching principle for $G_n$ is $2^{\Omega(n)}$, where $n$ is ... more >>>

TR14-094 | 24th July 2014
Zeev Dvir, Sivakanth Gopi

#### 2-Server PIR with sub-polynomial communication

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the $i$th bit of an $n$-bit database replicated among two servers (which do not communicate) while not revealing any information about $i$ to either server. In this work we construct a 1-round 2-server PIR with total communication cost ... more >>>

TR14-095 | 24th July 2014
Mark Braverman, Ankit Garg

#### Small value parallel repetition for general games

Revisions: 1

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. We use information theoretic techniques in our proof. Our proofs also extend to the high value regime (value close to 1) ... more >>>

TR14-096 | 29th July 2014
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

#### Solving Linear Equations Parameterized by Hamming Weight

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:
1. Does $Ax=b$ have a solution of weight at most $t$?
2. Does $Ax=b$ have a solution of weight exactly $t$?
3. Does $Ax=b$ have a ... more >>>

TR14-097 | 31st July 2014
Oded Goldreich, Liav Teichner

#### Super-Perfect Zero-Knowledge Proofs

Revisions: 1

We initiate a study of super-perfect zero-knowledge proof systems.
Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time.
In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated
by a strict probabilistic polynomial-time that ... more >>>

TR14-098 | 30th July 2014
Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

#### Simultaneous Approximation of Constraint Satisfaction Problems

Given $k$ collections of 2SAT clauses on the same set of variables $V$, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.

Our main result is that ... more >>>

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

#### The Complexity of DNF of Parities

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

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

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

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

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

TR14-101 | 8th August 2014
Balthazar Bauer, Shay Moran, Amir Yehudayoff

#### Internal compression of protocols to entropy

Revisions: 1

We study internal compression of communication protocols
to their internal entropy, which is the entropy of the transcript from the players' perspective.
We first show that errorless compression to the internal entropy
(and hence to the internal information) is impossible.
We then provide two internal compression schemes with error.
One ... more >>>

TR14-102 | 4th August 2014

#### Non-Malleable Codes Against Constant Split-State Tampering

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10} as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions $\mathcal{F}$ consists ... 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 >>>

TR14-104 | 9th August 2014
Atri Rudra, Mary Wootters

#### It'll probably work out: improved list-decoding through random operations

In this work, we introduce a framework to study the effect of random operations on the combinatorial list decodability of a code.
The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural ... more >>>

TR14-105 | 9th August 2014
Craig Gentry

#### Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington’s Theorem

We show that, for many noncommutative algebras A, the hardness of computing the determinant of matrices over A follows almost immediately from Barrington’s Theorem. Barrington showed how to express a NC1 circuit as a product program over any non-solvable group. We construct a simple matrix directly from Barrington’s product program ... more >>>

TR14-106 | 9th August 2014
Craig Gentry

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

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

TR14-107 | 10th August 2014
Or Meir

#### Locally Correctable and Testable Codes Approaching the Singleton Bound

Revisions: 2

Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are codes that admit local algorithms for decoding and testing respectively. The local algorithms are randomized algorithms that make only a small number of queries to their input. LCCs and LTCs are both interesting in their own right, and have important applications in ... more >>>

TR14-108 | 10th August 2014
Andrej Bogdanov, Christina Brzuska

#### On Basing Size-Verifiable One-Way Functions on NP-Hardness

Revisions: 1

We prove that if the hardness of inverting a size-verifiable one-way function can
be based on NP-hardness via a general (adaptive) reduction, then coAM is contained in NP. This
claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but
was later retracted (STOC 2010).

more >>>

TR14-109 | 14th August 2014
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

#### Quantum lower bound for inverting a permutation with advice

Revisions: 1

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on ... more >>>

TR14-110 | 19th August 2014
Uriel Feige, Shlomo Jozeph

#### Separation between Estimation and Approximation

We show (under standard assumptions) that there are NP optimization problems for which estimation is easier than approximation. Namely, one can estimate the value of the optimal solution within a ratio of $\rho$, but it is difficult to find a solution whose value is within $\rho$ of optimal.
As an ... more >>>

TR14-111 | 15th August 2014
Vikraman Arvind, Gaurav Rattan

#### Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity

We give a $O^*(k^{O(k)})$ time isomorphism testing algorithm for graphs of eigenvalue multiplicity bounded by $k$ which improves on the previous
best running time bound of $O^*(2^{O(k^2/\log k)})$.

more >>>

TR14-112 | 23rd August 2014
Louay Bazzi

#### Entropy of weight distributions of small-bias spaces and pseudobinomiality

Revisions: 1

A classical bound in Information Theory asserts that small $L_1$-distance between probability distributions implies small difference in Shannon entropy, but the converse need not be true. We show that if a probability distribution on $\{0,1\}^n$ has small-bias, then the converse holds for its weight distribution in the proximity of the ... more >>>

TR14-113 | 27th August 2014
Anat Ganor, Gillat Kol, Ran Raz

#### Exponential Separation of Information and Communication for Boolean Functions

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol for a partial boolean function cannot always be compressed to ... 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 >>>

TR14-115 | 27th August 2014
Roei Tell

#### Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees

Revisions: 1

A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication ... more >>>

TR14-116 | 6th September 2014
Rahul Mehta

#### 2048 is (PSPACE) Hard, but Sometimes Easy

We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result
holds for a version of the problem where the player has oracle access to the computer player's moves.
Specifically, we show that for an $n \times n$ game board $G$, computing a
more >>>

TR14-117 | 18th August 2014
Shiva Manne, Manjish Pal

#### Fast Approximate Matrix Multiplication by Solving Linear Systems

In this paper, we present novel deterministic algorithms for multiplying two $n \times n$ matrices approximately. Given two matrices $A,B$ we return a matrix $C'$ which is an \emph{approximation} to $C = AB$. We consider the notion of approximate matrix multiplication in which the objective is to make the Frobenius ... more >>>

TR14-118 | 9th September 2014
Albert Atserias, Massimo Lauria, Jakob Nordström

#### Narrow Proofs May Be Maximally Long

We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n^O(w) is essentially tight. ... more >>>

TR14-119 | 15th September 2014
Mark Braverman, Jieming Mao

#### Simulating Noisy Channel Interaction

We show that $T$ rounds of interaction over the binary symmetric channel $BSC_{1/2-\epsilon}$ with feedback can be simulated with $O(\epsilon^2 T)$ rounds of interaction over a noiseless channel. We also introduce a more general "energy cost'' model of interaction over a noisy channel. We show energy cost to be equivalent ... more >>>

TR14-120 | 16th September 2014
Olaf Beyersdorff, Leroy Chew, Mikolas Janota

#### Proof Complexity of Resolution-based QBF Calculi

Proof systems for quantified Boolean formulas (QBFs) provide a theoretical underpinning for the performance of important
QBF solvers. However, the proof complexity of these proof systems is currently not well understood and in particular
lower bound techniques are missing. In this paper we exhibit a new and elegant proof technique ... more >>>

TR14-121 | 22nd September 2014
Sebastian Mueller

#### Graph Structure and Parity Games

We investigate the possible structural changes one can perform on a game graph without destroying the winning regions of the players playing a parity game on it. More precisely, given a game graph $(G,p)$ for which we can efficiently compute winning regions, can we remove or add a vertex or ... more >>>

TR14-122 | 30th September 2014
Eric Allender, Anna Gal, Ian Mertz

#### Dual VP Classes

Revisions: 2

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of
a class of high-degree polynomials that can be simulated via arithmetic circuits ... more >>>

TR14-123 | 7th October 2014
Shachar Lovett, Jiapeng Zhang

#### Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions

The noisy population recovery problem is a basic statistical inference problem. Given an unknown distribution in $\{0,1\}^n$ with support of size $k$,
and given access only to noisy samples from it, where each bit is flipped independently with probability $1/2-\eps$,
estimate the original probability up to an additive error of ... more >>>

TR14-124 | 7th October 2014
Periklis Papakonstantinou

#### The Depth Irreducibility Hypothesis

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

TR14-125 | 9th October 2014
Anindya De

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

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

TR14-126 | 9th October 2014
Debasis Mandal, A. Pavan, Rajeswari Venugopalan

#### Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis

We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a {\em worst-case} hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time $O(2^{2^{n^c}})$ (for some $c > 1$) accepting $\Sigma^*$ whose accepting ... more >>>

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

#### Batch Codes through Dense Graphs without Short Cycles

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

TR14-128 | 10th October 2014
Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana , Maciej Obremski

#### Non-malleable Reductions and Applications

Revisions: 3

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either ... more >>>

TR14-129 | 10th October 2014
Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana , Maciej Obremski

#### Leakage-resilient non-malleable codes

Revisions: 1

A recent trend in cryptography is to construct cryptosystems that are secure against physical attacks. Such attacks are usually divided into two classes: the \emph{leakage} attacks in which the adversary obtains some information about the internal state of the machine, and the \emph{tampering} attacks where the adversary can modify this ... 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 >>>

TR14-131 | 7th October 2014
Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah

#### A game characterisation of tree-like Q-Resolution size

We provide a characterisation for the size of proofs in tree-like Q-Resolution by a Prover-Delayer game, which is inspired by a similar characterisation for the proof size in classical tree-like Resolution. This gives the first successful transfer of one of the lower bound techniques for classical proof systems to QBF ... more >>>

TR14-132 | 23rd October 2014
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

#### Information Complexity for Multiparty Communication

Revisions: 2

In this paper, we have studied the information complexity for the communication model involving more than two parties. A lot of work has already been done on the information complexity in two party communication model and the question of extending the definition of information complexity to the multiparty communication model ... more >>>

TR14-133 | 15th October 2014

#### Mutual Dimension

We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory ... more >>>

TR14-134 | 10th October 2014
Martin Lück, Arne Meier, Irina Schindler

#### Parameterized Complexity of CTL: Courcelle's Theorem For Infinite Vocabularies

Revisions: 3

We present a complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is temporal depth and pathwidth. Our results show a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The two real operator fragments which are in FPT ... more >>>

TR14-135 | 23rd October 2014
Noga Alon, Shay Moran, Amir Yehudayoff

#### Sign rank, VC dimension and spectral gaps

Revisions: 2

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>

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

#### Classical Automata on Promise Problems

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

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

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

#### The space complexity of cutting planes refutations

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

TR14-139 | 31st October 2014
Hong Van Le

#### Lower bounds for the circuit size of partially homogeneous polynomials

Revisions: 1

In this paper
we associate to each multivariate polynomial $f$ that is homogeneous relative to a subset of its variables a series of polynomial families $P_\lambda (f)$ of $m$-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in $P_\lambda (f)$ is bounded from above ... more >>>

TR14-140 | 31st October 2014
Hong Van Le

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

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

TR14-141 | 24th October 2014
Shachar Lovett

#### Linear codes cannot approximate the network capacity within any constant factor

Network coding studies the capacity of networks to carry information, when internal nodes are allowed to actively encode information. It is known that for multi-cast networks, the network coding capacity can be achieved by linear codes. It is also known not to be true for general networks. The best separation ... more >>>

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

#### Candidate Lasserre Integrality Gap For Unique Games

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

TR14-143 | 3rd November 2014
Ronald de Haan, Stefan Szeider

#### Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These parameterized problems are based on problems whose complexity lies at the second level of the Polynomial Hierarchy or higher. The list will be updated as ... more >>>

TR14-144 | 30th October 2014
Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan

#### Learning circuits with few negations

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and ... more >>>

TR14-145 | 4th November 2014
Yuan Li, Alexander Razborov, Benjamin Rossman

#### On the $AC^0$ Complexity of Subgraph Isomorphism

Let $P$ be a fixed graph (hereafter called a pattern''), and let
$Subgraph(P)$ denote the problem of deciding whether a given graph $G$
contains a subgraph isomorphic to $P$. We are interested in
$AC^0$-complexity of this problem, determined by the smallest possible exponent
$C(P)$ for which $Subgraph(P)$ possesses bounded-depth circuits ... more >>>

TR14-146 | 6th November 2014
Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan

#### Space proof complexity for random $3$-CNFs via a $(2-\epsilon)$-Hall's Theorem

We investigate the space complexity of refuting $3$-CNFs in Resolution and algebraic systems. No lower bound for refuting any family of $3$-CNFs was previously known for the total space in resolution or for the monomial space in algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a ... more >>>

TR14-147 | 6th November 2014
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

Revisions: 1

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$ where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently hard'' two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ ... more >>> TR14-148 | 8th November 2014 Vitaly Feldman, Will Perkins, Santosh Vempala #### On the Complexity of Random Satisfiability Problems with Planted Solutions Revisions: 1 We consider the problem of identifying a planted assignment given a random$k$-SAT formula consistent with the assignment. This problem exhibits a large algorithmic gap: while the planted solution can always be identified given a formula with$O(n\log n)$clauses, there are distributions over clauses for which the best known ... more >>> TR14-149 | 10th November 2014 Kai-Min Chung, Xin Li, Xiaodi Wu #### Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new ... more >>> TR14-150 | 10th November 2014 Justin Thaler #### Lower Bounds for the Approximate Degree of Block-Composed Functions Revisions: 3 We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function$f$on$N$bits, define$F(x_1, \dots, x_M) = \text{OMB}(f(x_1), \dots, f(x_M))$to be the function on$M \cdot N$bits obtained by block-composing$f$with a specific DNF known ... more >>> TR14-151 | 13th November 2014 Debajyoti Bera #### Quantum One-Sided Exact Error Algorithms Revisions: 2 We define a complexity class for randomized algorithms with one-sided error that is exactly equal to a constant (unlike the usual definitions, in which the error is only bounded above or below by a constant). We show that the corresponding quantum classes (one each for a different error probability) are ... more >>> TR14-152 | 13th November 2014 Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo #### Tighter Relations Between Sensitivity and Other Complexity Measures Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other major complexity measures. Despite much attention to the problem and major advances ... more >>> TR14-153 | 14th November 2014 Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan #### Communication with Imperfectly Shared Randomness Revisions: 2 The communication complexity of many fundamental problems reduces greatly when the communicating parties share randomness that is independent of the inputs to the communication task. Natural communication processes (say between humans) however often involve large amounts of shared correlations among the communicating players, but rarely allow for perfect sharing of ... more >>> TR14-154 | 20th November 2014 Andris Ambainis, Yuval Filmus, Francois Le Gall #### Fast Matrix Multiplication: Limitations of the Laser Method Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time$O(n^{2.3755})$. Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time$O(n^{2.3729})$. These algorithms are obtained by analyzing higher ... more >>> TR14-155 | 21st November 2014 Scott Aaronson, Andris Ambainis #### Forrelation: A Problem that Optimally Separates Quantum from Classical Computing We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum ... more >>> TR14-156 | 26th November 2014 Jayadev Acharya, Clement Canonne, Gautam Kamath #### A Chasm Between Identity and Equivalence Testing with Conditional Queries Revisions: 1 A recent model for property testing of probability distributions enables tremendous savings in the sample complexity of testing algorithms, by allowing them to condition the sampling on subsets of the domain. In particular, Canonne et al. showed that, in this setting, testing identity of an unknown distribution$D$(i.e., ... more >>> TR14-157 | 27th November 2014 Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk #### Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models. For depth-3 multilinear formulas, of size$\exp(n^\delta)$, we give a hitting set of size$\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$. ... more >>> TR14-158 | 26th November 2014 Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf #### Deterministic Identity Testing for Sum of Read Once ABPs Revisions: 2 A read once ABP is an arithmetic branching program with each variable occurring in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity, i.e. ... more >>> TR14-159 | 27th November 2014 A. C. Cem Say, Abuzer Yakaryilmaz #### Magic coins are useful for small-space quantum machines Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use logarithmic space, it is known that such magic coins'' give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits ... more >>> TR14-160 | 27th November 2014 Gil Cohen, Igor Shinkar #### Zero-Fixing Extractors for Sub-Logarithmic Entropy An$(n,k)$-bit-fixing source is a distribution on$n$bit strings, that is fixed on$n-k$of the coordinates, and jointly uniform on the remaining$k$bits. Explicit constructions of bit-fixing extractors by Gabizon, Raz and Shaltiel [SICOMP 2006] and Rao [CCC 2009], extract$(1-o(1)) \cdot k$bits for$k = ... more >>>

TR14-161 | 27th November 2014
Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

#### Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs

Revisions: 2

The perfect matching problem has a randomized $NC$ algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We ... more >>>

TR14-162 | 28th November 2014
Michael Forbes, Venkatesan Guruswami

#### Dimension Expanders via Rank Condensers

An emerging theory of "linear-algebraic pseudorandomness" aims to understand the linear-algebraic analogs of fundamental Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In this work, we study and highlight the interrelationships between several such algebraic objects such as subspace designs, dimension ... more >>>

TR14-163 | 29th November 2014
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

#### Homomorphism polynomials complete for VP

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant ... more >>>

TR14-164 | 30th November 2014
Cody Murray, Ryan Williams

#### On the (Non) NP-Hardness of Computing Circuit Complexity

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function $f$ and a size parameter $k$, is the circuit complexity of $f$ at most $k$? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of ... 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 >>>

TR14-166 | 8th December 2014
Mark Bun, Thomas Steinke

#### Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

Polynomial approximations to boolean functions have led to many positive results in computer science. In particular, polynomial approximations to the sign function underly algorithms for agnostically learning halfspaces, as well as pseudorandom generators for halfspaces. In this work, we investigate the limits of these techniques by proving inapproximability results for ... more >>>

TR14-167 | 11th November 2014
Beate Bollig

#### On the Minimization of (Complete) Ordered Binary Decision Diagrams

Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions.
Some applications work with a restricted variant called complete OBDDs
which is strongly related to nonuniform deterministic finite automata.
One of its complexity measures is the width which has been investigated
in several areas in computer science ... more >>>

TR14-168 | 8th December 2014
Ilya Volkovich

#### Deterministically Factoring Sparse Polynomials into Multilinear Factors

We present the first efficient deterministic algorithm for factoring sparse polynomials that split into multilinear factors.
Our result makes partial progress towards the resolution of the classical question posed by von zur Gathen and Kaltofen in \cite{GathenKaltofen85} to devise an efficient deterministic algorithm for factoring (general) sparse polynomials.
We achieve ... more >>>

TR14-169 | 9th December 2014
Stasys Jukna

#### Lower Bounds for Monotone Counting Circuits

A {+,x}-circuit counts a given multivariate polynomial f, if its values on 0-1 inputs are the same as those of f; on other inputs the circuit may output arbitrary values. Such a circuit counts the number of monomials of evaluated to 1 by a given 0-1 input vector (with multiplicities ... more >>>

TR14-170 | 10th December 2014
Yael Tauman Kalai, Ran Raz

#### On the Space Complexity of Linear Programming with Preprocessing

Revisions: 1

Linear Programs are abundant in practice, and tremendous effort has been put into designing efficient algorithms for such problems, resulting with very efficient (polynomial time) algorithms. A fundamental question is: what is the space complexity of Linear Programming?

It is widely believed that (even approximating) Linear Programming requires a large ... more >>>

TR14-171 | 11th December 2014
Lance Fortnow, Rahul Santhanam

We strengthen the non-deterministic time hierarchy theorem of
\cite{Cook72, Seiferas-Fischer-Meyer78, Zak83} to show that the lower bound
holds against sublinear advice. More formally, we show that for any constants
$c$ and $d$ such that $1 \leq c < d$, there is a language in $\NTIME(n^d)$
which is not in $\NTIME(n^c)/n^{1/d}$. ... more >>>

TR14-172 | 12th December 2014
Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin

#### Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

A square matrix $V$ is called rigid if every matrix $V^\prime$ obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major ... more >>>

TR14-173 | 13th December 2014
Igor Carboni Oliveira, Rahul Santhanam

#### Majority is incompressible by AC$^0[p]$ circuits

Revisions: 1

We consider $\cal C$-compression games, a hybrid model between computational and communication complexity. A $\cal C$-compression game for a function $f \colon \{0,1\}^n \to \{0,1\}$ is a two-party communication game, where the first party Alice knows the entire input $x$ but is restricted to use strategies computed by $\cal C$-circuits, ... more >>>

TR14-174 | 14th December 2014
Avishay Tal

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

Revisions: 2

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

TR14-175 | 15th December 2014
Abhishek Bhowmick, Shachar Lovett

#### Nonclassical polynomials as a barrier to polynomial lower bounds

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of ... more >>>

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

#### The Minimum Oracle Circuit Size Problem

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

TR14-177 | 14th December 2014
Andreas Krebs, Klaus-Joern Lange, Michael Ludwig

#### Visibly Counter Languages and Constant Depth Circuits

We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC0, and show that they are contained in FO[+].

more >>>

TR14-178 | 5th December 2014
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

#### Heuristic time hierarchies via hierarchies for sampling distributions

We give a new simple proof of the time hierarchy theorem for heuristic BPP originally proved by Fortnow and Santhanam [FS04] and then simplified and improved by Pervyshev [P07]. In the proof we use a hierarchy theorem for sampling distributions recently proved by Watson [W13]. As a byproduct we get ... more >>>

TR14-179 | 20th December 2014
Salman Beigi, Omid Etesami, Amin Gohari

#### Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources

A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible.
In this paper, we study the generalization of SV ... more >>>

TR14-180 | 22nd December 2014
Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

#### Space-Efficient Approximations for Subset Sum

SUBSET SUM is a well known NP-complete problem:
given $t \in Z^{+}$ and a set $S$ of $m$ positive integers, output YES if and only if there is a subset $S^\prime \subseteq S$ such that the sum of all numbers in $S^\prime$ equals $t$. The problem and its search ... more >>>

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

#### The space "just above" BQP

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

TR14-182 | 22nd December 2014
Dana Moshkovitz

#### Direct Product Testing With Nearly Identical Sets

In this work we analyze a direct product test in which each of two provers receives a subset of size n of a ground set U,
and the two subsets intersect in about (1-\delta)n elements.
We show that if each of the provers provides labels to the n ... more >>>

TR14-183 | 25th December 2014
Nikhil Balaji, Andreas Krebs, Nutan Limaye

#### Skew Circuits of Small Width

A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs -- polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known that width-3 PBPs ... more >>>

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

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

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

ISSN 1433-8092 | Imprint