Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2015:
All reports in year 2015:

TR15-001 | 2nd January 2015
Nir Bitansky, Omer Paneth, Alon Rosen

#### On the Cryptographic Hardness of Finding a Nash Equilibrium

Revisions: 1

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which ... more >>>

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

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

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

TR15-003 | 3rd January 2015
Oded Goldreich, Emanuele Viola, Avi Wigderson

#### On Randomness Extraction in AC0

We consider randomness extraction by AC0 circuits. The main parameter, $n$, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound $k=k(n)$, the seed length $r=r(n)$, the output length $m=m(n)$, and the (output) deviation bound $\epsilon=\epsilon(n)$.

\to \{0,1\}$such that the xor of two independent copies ($D+D$) does not fool$f$, for any of the following choices: 1.$\epsilon = 2^{-\Omega(n)}$and$f$is in P/poly; 2.$\epsilon = 2^{-\Omega(n/\log n)}$and$f$is ... more >>> TR15-006 | 6th January 2015 Nader Bshouty #### Dense Testers: Almost Linear Time and Locally Explicit Constructions We develop a new notion called {\it$(1-\epsilon)$-tester for a set$M$of functions}$f:A\to C$. A$(1-\epsilon)$-tester for$M$maps each element$a\in A$to a finite number of elements$B_a=\{b_1,\ldots,b_t\}\subset B$in a smaller sub-domain$B\subset A$where for every$f\in M$if$f(a)\not=0$then$f(b)\not=0$for at ... more >>> TR15-007 | 8th January 2015 Jonah Brown-Cohen, Prasad Raghavendra #### Combinatorial Optimization Algorithms via Polymorphisms An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture of [BKJ00]. Roughly speaking, the characterization asserts that a CSP$\Lambda$is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to ... more >>> TR15-008 | 14th January 2015 Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen #### The Power of Negations in Cryptography Revisions: 1 The study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be ... more >>> 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 >>> TR15-010 | 19th January 2015 Maciej Li\'skiewicz, Rüdiger Reischuk, Ulrich Wölfel #### Security Levels in Steganography -- Insecurity does not Imply Detectability This paper takes a fresh look at security notions for steganography -- the art of encoding secret messages into unsuspicious covertexts such that an adversary cannot distinguish the resulting stegotexts from original covertexts. Stegosystems that fulfill the security notion used so far, however, are quite inefficient. This ... more >>> TR15-011 | 22nd January 2015 Subhash Khot, Dor Minzer, Muli Safra #### On Monotonicity Testing and Boolean Isoperimetric type Theorems We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes$\tilde{O}(\sqrt{n}/\epsilon^2)$non-adaptive queries to a function$f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is$\epsilon$-far from being monotone ... more >>> TR15-012 | 24th January 2015 Mika Göös #### Lower Bounds for Clique vs. Independent Set We prove an$\omega(\log n)$lower bound on the conondeterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies superpolynomial lower bounds for the Alon--Saks--Seymour conjecture in graph theory. Our approach is to first exhibit a query complexity ... more >>> TR15-013 | 28th January 2015 Subhash Khot, Igor Shinkar #### On Hardness of Approximating the Parameterized Clique Problem In the$Gap-clique(k, \frac{k}{2})$problem, the input is an$n$-vertex graph$G$, and the goal is to decide whether$G$contains a clique of size$k$or contains no clique of size$\frac{k}{2}$. It is an open question in the study of fixed parameterized tractability whether the$Gap-clique(k, \frac{k}{2})$problem ... more >>> TR15-014 | 18th January 2015 Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler #### Reliable Communication over Highly Connected Noisy Networks We consider the task of multiparty computation performed over networks in the presence of random noise. Given an$n$-party protocol that takes$R$rounds assuming noiseless communication, the goal is to find a coding scheme that takes$R'$rounds and computes the same function with high probability even when the ... more >>> TR15-015 | 30th January 2015 Neeraj Kayal, Chandan Saha #### Multi-$k$-ic depth three circuit lower bound In a multi-$k$-ic depth three circuit every variable appears in at most$k$of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables ... 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 >>> TR15-017 | 20th January 2015 Bruno Bauwens, Marius Zimand #### Linear list-approximation for short programs (or the power of a few random bits) A$c$-short program for a string$x$is a description of$x$of length at most$C(x) + c$, where$C(x)$is the Kolmogorov complexity of$x$. We show that there exists a randomized algorithm that constructs a list of$n$elements that contains a$O(\log n)$-short program for$x$. ... more >>> TR15-018 | 31st January 2015 Eric Allender, Ian Mertz #### Complexity of Regular Functions Revisions: 1 We give complexity bounds for various classes of functions computed by cost register automata. more >>> TR15-019 | 3rd February 2015 Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira #### Constructing Near Spanning Trees with Few Local Inspections Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let$G$be a connected bounded-degree graph. Given an edge$e$in$G$we would like ... more >>> TR15-020 | 31st January 2015 Michael Viderman #### Explicit Strong LTCs with inverse poly-log rate and constant soundness Revisions: 3 An error-correcting code$C \subseteq \F^n$is called$(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most$q$queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords$x\notin C$with probability at least$\epsilon \cdot \delta(x,C)$, where ... more >>> TR15-021 | 5th February 2015 Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf #### Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his ... more >>> TR15-022 | 9th February 2015 Nutan Limaye, Guillaume Malod, Srikanth Srinivasan #### Lower bounds for non-commutative skew circuits Revisions: 1 Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan's hard polynomial is in fact computable by linear sized skew circuits (skew circuits are circuits where every multiplication gate has the property that all but one of ... more >>> TR15-023 | 10th February 2015 Mark Braverman, Jon Schneider #### Information complexity is computable The information complexity of a function$f$is the minimum amount of information Alice and Bob need to exchange to compute the function$f$. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function$f$to within any additive error$\alpha>0$, thus resolving an ... more >>> TR15-024 | 16th February 2015 Oded Goldreich, Tom Gur, Ron Rothblum #### Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>> TR15-025 | 22nd February 2015 Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff #### Teaching and compressing for low VC-dimension In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. We present relatively efficient constructions of {\em sample compression schemes} and for classes of low VC-dimension. Let$C$be a finite boolean concept class of VC-dimension$d$. Set$k ... more >>>

TR15-026 | 21st February 2015
Siyao Guo, Ilan Komargodski

#### Negation-Limited Formulas

Revisions: 1

Understanding the power of negation gates is crucial to bridge the exponential gap between monotone and non-monotone computation. We focus on the model of formulas over the De Morgan basis and consider it in a negation-limited setting.

We prove that every formula that contains $t$ negation gates can be shrunk ... more >>>

TR15-027 | 25th February 2015
Benny Applebaum

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

Revisions: 1

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

TR15-028 | 27th February 2015
Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland

#### Relative Discrepancy does not separate Information and Communication Complexity

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>

TR15-029 | 18th February 2015
Stanislav Zak

#### Inherent logic and complexity

Abstract. The old intuitive question "what does the machine think" at
different stages of its computation is examined. Our paper is based on
the formal de nitions and results which are collected in the branching
program theory around the intuitive question "what does the program
know about the contents of ... more >>>

TR15-030 | 6th March 2015
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

#### ${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$ lower bounds for the Boolean Inner Product

Revisions: 1

$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuits are $\mathrm{AC}^{0}$ circuits augmented with a layer of parity gates just above the input layer. We study the $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have ... 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 >>>

TR15-032 | 21st February 2015
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky

#### Graph Isomorphism, Color Refinement, and Compactness

Revisions: 2

Color refinement is a classical technique used to show that two given graphs $G$ and $H$
are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph $G$ amenable to color refinement if the color-refinement procedure succeeds in distinguishing $G$ from any non-isomorphic ... 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 >>>

TR15-034 | 8th March 2015
Xin Li

#### Three-Source Extractors for Polylogarithmic Min-Entropy

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

TR15-035 | 22nd February 2015
Sunil K S, Balagopal Komarath, Jayalal Sarma

#### Comparator Circuits over Finite Bounded Posets

Revisions: 1

Comparator circuit model was originally introduced by Mayr and Subramanian (1992) to capture problems which are not known to be P-complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem We know ... more >>>

TR15-036 | 17th February 2015
David Gajser

#### Verifying whether One-Tape Turing Machines Run in Linear Time

We discuss the following family of problems, parameterized by integers $C\geq 2$ and $D\geq 1$: Does a given one-tape non-deterministic $q$-state Turing machine make at most $Cn+D$ steps on all computations on all inputs of length $n$, for all $n$?

Assuming a fixed tape and input alphabet, we show that ... more >>>

TR15-037 | 20th February 2015
Arnab Bhattacharyya, Palash Dey

#### Sample Complexity for Winner Prediction in Elections

Predicting the winner of an election is a favorite problem both for news media pundits and computational social choice theorists. Since it is often infeasible to elicit the preferences of all the voters in a typical prediction scenario, a common algorithm used for winner prediction is to run the election ... more >>>

TR15-038 | 11th March 2015
Gil Cohen

#### Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

Revisions: 1

We introduce and construct a pseudorandom object which we call a local correlation breaker (LCB). Informally speaking, an LCB is a function that gets as input a sequence of $r$ (arbitrarily correlated) random variables and an independent weak-source. The output of the LCB is a sequence of $r$ random variables ... more >>>

TR15-039 | 16th March 2015
Anup Rao, Makrand Sinha

#### On Parallelizing Streaming Algorithms

We study the complexity of parallelizing streaming algorithms (or equivalently, branching programs). If $M(f)$ denotes the minimum average memory required to compute a function $f(x_1,x_2, \dots, x_n)$ how much memory is required to compute $f$ on $k$ independent streams that arrive in parallel? We show that when the inputs (updates) ... more >>>

TR15-040 | 24th March 2015
Shay Moran, Amir Yehudayoff

#### Proper PAC learning is compressing

Revisions: 1

We prove that proper PAC learnability implies compression. Namely, if a concept $C \subseteq \Sigma^X$ is properly PAC learnable with $d$ samples, then $C$ has a sample compression scheme of size $2^{O(d)}$.
In particular, every boolean concept class with constant VC dimension has a sample compression scheme of constant size. ... more >>>

TR15-041 | 25th March 2015
Mark Bun, Justin Thaler

#### Dual Polynomials for Collision and Element Distinctness

The approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within error $1/3$ in the $\ell_\infty$ norm. In an influential result, Aaronson and Shi (J. ACM 2004) proved tight $\tilde{\Omega}(n^{1/3})$ and $\tilde{\Omega}(n^{2/3})$ lower bounds on ... more >>>

TR15-042 | 30th March 2015
Ilya Volkovich

#### Computations beyond Exponentiation Gates and Applications

In Arithmetic Circuit Complexity the standard operations are $\{+,\times\}$.
Yet, in some scenarios exponentiation gates are considered as well (see e.g. \cite{BshoutyBshouty98,ASSS12,Kayal12,KSS14}).
In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power.
That is, beyond an exponentiation gate. As ... more >>>

TR15-043 | 2nd April 2015

#### Robust testing of lifted codes with applications to low-degree testing

A local tester for a code probabilistically looks at a given word at a small set of coordinates and based on this local view accepts codewords with probability one while rejecting words far from the code with constant probabilility. A local tester for a code is said to be robust'' ... more >>>

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

#### The communication complexity of interleaved group products

Revisions: 1

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

TR15-045 | 1st April 2015
Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

#### Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings

Revisions: 1

A one-way function is $d$-local if each of its outputs depends on at most $d$ input bits. In (Applebaum, Ishai, and Kushilevitz, FOCS 2004) it was shown that, under relatively mild assumptions, there exist $4$-local one-way functions (OWFs). This result is not far from optimal as it is not hard ... more >>>

TR15-046 | 2nd April 2015
Talya Eden, Amit Levi, Dana Ron

#### Approximately Counting Triangles in Sublinear Time

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

TR15-047 | 2nd April 2015
Swastik Kopparty, Mrinal Kumar, Michael Saks

#### Efficient indexing of necklaces and irreducible polynomials over finite fields

We study the problem of indexing irreducible polynomials over finite fields, and give the first efficient algorithm for this problem. Specifically, we show the existence of poly(n, log q)-size circuits that compute a bijection between {1, ... , |S|} and the set S of all irreducible, monic, univariate polynomials of ... more >>>

TR15-048 | 14th February 2015

#### Width Hierarchy for $k$-OBDD of Small Width

Revisions: 1

In this paper was explored well known model $k$-OBDD. There are proven width based hierarchy of classes of boolean functions which computed by $k$-OBDD. The proof of hierarchy is based on sufficient condition of Boolean function's non representation as $k$-OBDD and complexity properties of Boolean
function SAF. This function is ... more >>>

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

#### The Landscape of Communication Complexity Classes

Revisions: 1

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

TR15-050 | 4th April 2015
Mika Göös, Toniann Pitassi, Thomas Watson

#### Deterministic Communication vs. Partition Number

Revisions: 1

We show that deterministic communication complexity can be superlogarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the Clique vs. Independent Set problem, which in particular yields new lower bounds for the log-rank conjecture. All these results follow from a simple ... more >>>

TR15-051 | 5th April 2015
Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

#### Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions

Revisions: 2

A circuit $C$ \emph{compresses} a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ if given an input $x\in \{0,1\}^n$ the circuit $C$ can shrink $x$ to a shorter $\ell$-bit string $x'$ such that later, a computationally-unbounded solver $D$ will be able to compute $f(x)$ based on $x'$. In this paper we study the existence of ... more >>>

TR15-052 | 6th April 2015

#### Depth-4 Identity Testing and Noether's Normalization Lemma

Revisions: 1

We consider the \emph{black-box} polynomial identity testing problem for a sub-class of
depth-4 circuits. Such circuits compute polynomials of the following type:
$C(x) = \sum_{i=1}^k \prod_{j=1}^{d_i} Q_{i,j},$
where $k$ is the fan-in of the top $\Sigma$ gate and $r$ is the maximum degree of the ... more >>>

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

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

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

TR15-054 | 7th April 2015
Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

#### Welfare Maximization with Limited Interaction

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model
where agent's valuations are unknown to the central planner, and therefore communication is required to determine an
efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is $n$, ... more >>>

TR15-055 | 13th April 2015
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

#### How to Compress Asymmetric Communication

We study the relationship between communication and information in 2-party communication protocols when the information is asymmetric. If $I^A$ denotes the number of bits of information revealed by the first party, $I^B$ denotes the information revealed by the second party, and $C$ is the number of bits of communication in ... more >>>

TR15-056 | 3rd April 2015
Sanjam Garg, Steve Lu, Rafail Ostrovsky

#### Black-Box Garbled RAM

Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations ... more >>>

TR15-057 | 13th April 2015
Anup Rao, Makrand Sinha

#### Simplified Separation of Information and Communication

Revisions: 3

We give an example of a boolean function whose information complexity is exponentially
smaller than its communication complexity. Our result simplifies recent work of Ganor, Kol and
Raz (FOCS'14, STOC'15).

more >>>

TR15-058 | 1st April 2015
Peng Cui

#### Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion

In this paper, the author puts forward a variation of Feige's Hypothesis, which claims that it is hard on average refuting Unbalanced Max 3-XOR under biased assignments on a natural distribution. Under this hypothesis, the author strengthens the previous known hardness for approximating Minimum Unique Game, $5/4-\epsilon$, by proving that ... more >>>

TR15-059 | 10th April 2015
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

#### Feasible Interpolation for QBF Resolution Calculi

In sharp contrast to classical proof complexity we are currently short of lower bound techniques for QBF proof systems. In this paper we establish the feasible interpolation technique for all resolution-based QBF systems, whether modelling CDCL or expansion-based solving. This both provides the first general lower bound method for QBF ... more >>>

TR15-060 | 14th April 2015
Omri Weinstein

#### Information Complexity and the Quest for Interactive Compression

Revisions: 1

Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is ... 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 >>>

TR15-062 | 15th April 2015
Sangxia Huang

#### $2^{(\log N)^{1/4-o(1)}}$ Hardness for Hypergraph Coloring

Revisions: 2

We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(\log N)^{1/4-o(1)}}$ colors, where $N$ is the number of vertices. There has been much focus on hardness of hypergraph coloring recently. Guruswami, H{\aa}stad, Harsha, Srinivasan and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with ... 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 >>>

TR15-064 | 19th April 2015
Ilan Komargodski, Pravesh Kothari, Madhu Sudan

#### Communication with Contextual Uncertainty

Revisions: 1

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information $x$ and Bob gets $y$, where $(x,y)$ is drawn from a known distribution, and Bob ... more >>>

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

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

#### The Classification of Reversible Bit Operations

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

TR15-067 | 21st April 2015
Pavel Hrubes

#### On hardness of multilinearization, and VNP completeness in characteristics two

For a boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$, let $\hat{f}$ be the unique multilinear polynomial such that $f(x)=\hat{f}(x)$ holds for every $x\in \{0,1\}^n$. We show that, assuming $\hbox{VP}\not=\hbox{VNP}$, there exists a polynomial-time computable $f$ such that $\hat{f}$ requires super-polynomial arithmetic circuits. In fact, this $f$ can be taken as a monotone 2-CNF, ... more >>>

TR15-068 | 21st April 2015
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

#### High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Revisions: 3

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

TR15-069 | 21st April 2015
Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

#### On Fortification of General Games

Revisions: 1

A recent result of Moshkovitz~\cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel ... more >>>

TR15-070 | 22nd April 2015
Himanshu Tyagi, Shaileshh Venkatakrishnan , Pramod Viswanath, Shun Watanabe

#### Information Complexity Density and Simulation of Protocols

Revisions: 1

A simulation of an interactive protocol entails the use of an interactive communication to produce the output of the protocol to within a fixed statistical distance $\epsilon$. Recent works in the TCS community have propagated that the information complexity of the protocol plays a central role in characterizing the minimum ... more >>>

TR15-071 | 23rd April 2015
Mrinal Kumar, Shubhangi Saraf

#### Sums of products of polynomials in few variables : lower bounds and polynomial identity testing

We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T \prod_{j = 1}^d Q_{ij}$$
such that each $Q_{ij}$ is an arbitrary polynomial that depends on at most $s$ variables.

... more >>>

TR15-072 | 23rd April 2015
Roei Tell

#### On Being Far from Far and on Dual Problems in Property Testing

Revisions: 4

For a set $\Pi$ in a metric space and $\delta>0$, denote by $\mathcal{F}_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. In property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing ... more >>>

TR15-073 | 25th April 2015
Neeraj Kayal, Chandan Saha

#### Lower Bounds for Sums of Products of Low arity Polynomials

We prove an exponential lower bound for expressing a polynomial as a sum of product of low arity polynomials. Specifically, we show that for the iterated matrix multiplication polynomial, $IMM_{d, n}$ (corresponding to the product of $d$ matrices of size $n \times n$ each), any expression of the form
more >>>

TR15-074 | 29th April 2015
Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein

#### ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness

We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all $k$-subgraphs have density at most $1-\epsilon$, requires $n^{\tilde \Omega(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for ... more >>>

TR15-075 | 29th April 2015
Eshan Chattopadhyay, Vipul Goyal, Xin Li

#### Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Revisions: 1

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are \emph{seeded non-malleable extractors}, introduced by Dodis and Wichs \cite{DW09}; \emph{seedless non-malleable extractors}, introduced by Cheraghchi and Guruswami ... more >>>

TR15-076 | 28th April 2015
Mahdi Cheraghchi, Piotr Indyk

For every fixed constant $\alpha > 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \mathbb{R}^N$ in time $k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tilde{x} \in \mathbb{R}^N$ satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>> TR15-077 | 4th May 2015 Arnab Bhattacharyya, Abhishek Bhowmick #### Using higher-order Fourier analysis over general fields Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas. ... more >>> TR15-078 | 4th May 2015 Mladen Mikša, Jakob Nordström #### A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on proof size. [Alekhnovich and Razborov '03] established that if the clause-variable incidence graph of a CNF formula F is a good ... more >>> TR15-079 | 7th May 2015 Oded Goldreich, Avishay Tal #### Matrix Rigidity of Random Toeplitz Matrices We prove that random$n$-by-$n$Toeplitz (alternatively Hankel) matrices over$GF(2)$have rigidity$\Omega(\frac{n^3}{r^2\log n})$for rank$r \ge \sqrt{n}$, with high probability. This improves, for$r = o(n/\log n \log\log n)$, over the$\Omega(\frac{n^2}{r} \cdot\log(\frac{n}{r}))$bound that is known for many explicit matrices. Our result implies that the explicit ... 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 >>> TR15-081 | 12th May 2015 Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette #### Near-optimal bounds on bounded-round quantum communication complexity of disjointness We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with$r$rounds, we prove a lower bound of$\tilde{\Omega}(n/r)$on the communication required for computing disjointness of input size$n$, which is optimal up to logarithmic factors. The previous best lower bound ... more >>> TR15-082 | 13th May 2015 Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright #### Beating the random assignment on constraint satisfaction problems of bounded degree We show that for any odd$k$and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a$\frac{1}{2} + \Omega(1/\sqrt{D})$fraction of constraints, where$D$is a bound on the number of constraints that each variable occurs in. ... more >>> TR15-083 | 14th May 2015 Omri Weinstein, David Woodruff #### The Simultaneous Communication of Disjointness with Applications to Data Streams We study$k$-party set disjointness in the simultaneous message-passing model, and show that even if each element$i\in[n]$is guaranteed to either belong to all$k$parties or to at most$O(1)$parties in expectation (and to at most$O(\log n)$parties with high probability), then$\Omega(n \min(\log 1/\delta, \log ... more >>>

TR15-084 | 21st May 2015
Or Ordentlich, Ofer Shayevitz, Omri Weinstein

#### Dictatorship is the Most Informative Balanced Function at the Extremes

Revisions: 2

Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all ... more >>>

TR15-085 | 23rd May 2015
Irit Dinur, Prahladh Harsha, Guy Kindler

#### Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition

We show that every language in NP has a PCP verifier that tosses $O(\log n)$ random coins, has perfect completeness, and a soundness error of at most $1/poly(n)$, while making at most $O(poly\log\log n)$ queries into a proof over an alphabet of size at most $n^{1/poly\log\log n}$. Previous constructions that ... more >>>

TR15-086 | 28th May 2015
Jop Briet

#### On Embeddings of $\ell_1^k$ from Locally Decodable Codes

We show that any $q$-query locally decodable code (LDC) gives a copy of $\ell_1^k$ with small distortion in the Banach space of $q$-linear forms on $\ell_{p_1}^N\times\cdots\times\ell_{p_q}^N$, provided $1/p_1 + \cdots + 1/p_q \leq 1$ and where $k$, $N$, and the distortion are simple functions of the code parameters. We exhibit ... more >>>

TR15-087 | 30th May 2015

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of ''permutation-invariant'' functions. A partial function $f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$ is permutation-invariant if for every bijection $\pi:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, it is the case that $f(\mathbf{x}, \mathbf{y}) ... more >>> TR15-088 | 31st May 2015 Anat Ganor, Gillat Kol, Ran Raz #### Exponential Separation of Communication and External Information We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman [Bra13]. Previously, only a separation of communication complexity and internal information complexity was known [GKR14,GKR15]. More precisely, we obtain an explicit example of a search problem with ... more >>> TR15-089 | 31st May 2015 Eldar Fischer, Oded Lachish, Yadu Vadusev #### Trading query complexity for sample-based testing and multi-testing scalability} We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than$1$, power of$n$. Since the query ... more >>> TR15-090 | 1st June 2015 Alexander Kozachinsky #### On Slepian--Wolf Theorem with Interaction Revisions: 1 In this paper we study interactive one-shot'' analogues of the classical Slepian-Wolf theorem. Alice receives a value of a random variable$X$, Bob receives a value of another random variable$Y$that is jointly distributed with$X$. Alice's goal is to transmit$X$to Bob (with some error probability$\varepsilon$). ... more >>> TR15-091 | 3rd June 2015 Joshua Brody, Mario Sanchez #### Dependent Random Graphs and Multiparty Pointer Jumping We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges. We call such graphs dependent random graphs. Our main result in this direction is a thorough understanding of the clique number of dependent random graphs. ... more >>> TR15-092 | 31st May 2015 Yael Tauman Kalai, Ilan Komargodski #### Compressing Communication in Distributed Protocols Revisions: 2 We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of ... more >>> TR15-093 | 5th June 2015 Aviad Rubinstein #### Inapproximability of Nash Equilibrium We prove that finding an$\epsilon$-approximate Nash equilibrium is PPAD-complete for constant$\epsilon$and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions. As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete ... more >>> TR15-094 | 10th June 2015 Eli Ben-Sasson, iddo Ben-Tov, Ivan Bjerre Damgard, Yuval Ishai, Noga Ron-Zewi #### On Public Key Encryption from Noisy Codewords Several well-known public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of inverting noisy linear encodings. These schemes are limited in that they either require the underlying field to grow with the security parameter, ... more >>> TR15-095 | 14th June 2015 Gil Cohen #### Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of$2\log{n}$-Ramsey graphs on$n$vertices. Matching Erdös' result with a constructive proof is a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in ... more >>> TR15-096 | 5th June 2015 Abhishek Bhowmick, Shachar Lovett #### Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory Let$f$be a polynomial of degree$d$in$n$variables over a finite field$\mathbb{F}$. The polynomial is said to be unbiased if the distribution of$f(x)$for a uniform input$x \in \mathbb{F}^n$is close to the uniform distribution over$\mathbb{F}$, and is called biased otherwise. The polynomial ... more >>> TR15-097 | 16th June 2015 Marek Karpinski #### Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the ... more >>> TR15-098 | 15th June 2015 Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs #### Separations in Query Complexity Based on Pointer Functions Revisions: 2 In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function$f$on$n=2^k$bits defined by a complete binary tree of NAND gates of depth$k$, which achieves$R_0(f) = O(D(f)^{0.7537\ldots})$. ... more >>> TR15-099 | 12th June 2015 Ruiwen Chen #### Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases We give a \#SAT algorithm for boolean formulas over arbitrary finite bases. Let$B_k$be the basis composed of all boolean functions on at most$k$inputs. For$B_k$-formulas on$n$inputs of size$cn$, our algorithm runs in time$2^{n(1-\delta_{c,k})}$for$\delta_{c,k} = c^{-O(c^2k2^k)}$. We also show the average-case ... more >>> TR15-100 | 16th June 2015 Bireswar Das, Patrick Scharpfenecker, Jacobo Toran #### Succinct Encodings of Graph Isomorphism It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity. We introduce a new way for encoding graph problems, based on$\textrm{CNF}$or$\textrm{DNF}$formulas. We show that contrary to the other existing succinct models, there are ... more >>> TR15-101 | 15th June 2015 Patrick Scharpfenecker #### On the structure of Solution-Graphs for Boolean Formulas Revisions: 2 In this work we extend the study of solution graphs and prove that for boolean formulas in a class called CPSS, all connected components are partial cubes of small dimension, a statement which was proved only for some cases in [Schwerdtfeger 2013]. In contrast, we show that general Schaefer formulas ... 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-104 | 13th May 2015 Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont #### Streaming Property Testing of Visibly Pushdown Languages Revisions: 2 In the context of language recognition, we demonstrate the superiority of streaming property testers against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum et al, a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs ... more >>> TR15-105 | 21st June 2015 Venkatesan Guruswami, Euiwoong Lee #### Towards a Characterization of Approximation Resistance for Symmetric CSPs A Boolean constraint satisfaction problem (CSP) is called approximation resistant if independently setting variables to$1$with some probability$\alpha$achieves the best possible approximation ratio for the fraction of constraints satisfied. We study approximation resistance of a natural subclass of CSPs that we call Symmetric Constraint Satisfaction Problems (SCSPs), ... more >>> TR15-106 | 22nd June 2015 Itay Berman, Iftach Haitner, Aris Tentes #### Coin Flipping of Any Constant Bias Implies One-Way Functions Revisions: 1 We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g.,$.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias$\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike ... more >>> TR15-107 | 21st June 2015 Sagnik Mukhopadhyay, Swagato Sanyal #### Towards Better Separation between Deterministic and Randomized Query Complexity We show that there exists a Boolean function$F$which observes the following separations among deterministic query complexity$(D(F))$, randomized zero error query complexity$(R_0(F))$and randomized one-sided error query complexity$(R_1(F))$:$R_1(F) = \widetilde{O}(\sqrt{D(F)})$and$R_0(F)=\widetilde{O}(D(F))^{3/4}$. This refutes the conjecture made by Saks and Wigderson that for any Boolean ... more >>> TR15-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 >>> 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 >>> TR15-110 | 8th July 2015 Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf #### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity Revisions: 1 An error correcting code is said to be \emph{locally testable} if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a small number of symbols of the string. Locally testable codes (LTCs) are both interesting in their ... more >>> TR15-111 | 8th July 2015 Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky #### Low Distortion Embedding from Edit to Hamming Distance using Coupling Revisions: 1 The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings$x,y$lying in the Boolean hypercube. The edit distance between$x$and$y$is defined as the minimum number of character insertion, deletion, and bit flips needed for converting$x$into$y$. ... more >>> TR15-112 | 16th July 2015 Ruiwen Chen, Rahul Santhanam #### Improved Algorithms for Sparse MAX-SAT and MAX-$k$-CSP We give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX-$k$-CSP. For instances with$n$variables and$cn$clauses (constraints), we give algorithms running in time$\poly(n)\cdot 2^{n(1-\mu)}$for \begin{itemize} \item$\mu = \Omega(\frac{1}{c} )$and polynomial space solving MAX-SAT and MAX-$k$-SAT, \item$\mu = \Omega(\frac{1}{\sqrt{c}} )$and ... more >>> TR15-113 | 9th July 2015 Amit Chakrabarti, Tony Wirth #### Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover Set cover, over a universe of size$n$, may be modelled as a data-streaming problem, where the$m$sets that comprise the instance are to be read one by one. A semi-streaming algorithm is allowed only$O(n \text{ poly}\{\log n, \log m\})$space to process this ... more >>> TR15-114 | 18th July 2015 Avishay Tal #### #SAT Algorithms from Shrinkage We present a deterministic algorithm that counts the number of satisfying assignments for any de Morgan formula$F$of size at most$n^{3-16\epsilon}$in time$2^{n-n^{\epsilon}}\cdot \mathrm{poly}(n)$, for any small constant$\epsilon>0$. We do this by derandomizing the randomized algorithm mentioned by Komargodski et al. (FOCS, 2013) and Chen et ... more >>> TR15-115 | 20th July 2015 Ilya Volkovich #### A Guide to Learning Arithmetic Circuits An \emph{arithmetic circuit} is a directed acyclic graph in which the operations are$\{+,\times\}$. In this paper, we exhibit several connections between learning algorithms for arithmetic circuits and other problems. In particular, we show that: \begin{enumerate} \item Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds. ... more >>> TR15-116 | 21st July 2015 Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky #### Efficient Low-Redundancy Codes for Correcting Multiple Deletions Revisions: 1 We consider the problem of constructing binary codes to recover from$k$-bit deletions with efficient encoding/decoding, for a fixed$k$. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with$\approx 2^n/n$codewords of length$n$, i.e., at most$\log n$... 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 >>> TR15-118 | 23rd July 2015 Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan #### The shifted partial derivative complexity of Elementary Symmetric Polynomials We continue the study of the shifted partial derivative measure, introduced by Kayal (ECCC 2012), which has been used to prove many strong depth-4 circuit lower bounds starting from the work of Kayal, and that of Gupta et al. (CCC 2013). We show a strong lower bound on the dimension ... more >>> TR15-119 | 23rd July 2015 Eshan Chattopadhyay, David Zuckerman #### Explicit Two-Source Extractors and Resilient Functions Revisions: 5 We explicitly construct an extractor for two independent sources on$n$bits, each with min-entropy at least$\log^C n$for a large enough constant$C$. Our extractor outputs one bit and has error$n^{-\Omega(1)}$. The best previous extractor, by Bourgain [B2], required each source to have min-entropy$.499n$. A key ... more >>> TR15-120 | 12th July 2015 Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi #### Understanding PPA-Completeness Revisions: 1 The search complexity classes {\bf PPA} and {\bf PPAD} were proposed by Papadimitriou twenty years ago for characterizing the computational difficulties of many interesting natural search problems. While many members in the complete class of {\bf PPAD}, {\bf PPAD}-completeness, are established in the past twenty years, the understanding of the ... more >>> TR15-121 | 25th July 2015 Xin Li #### Extractors for Affine Sources with Polylogarithmic Entropy We give the first explicit construction of deterministic extractors for affine sources over$F_2$, with entropy$k \geq \log^C n$for some large enough constant$C$, where$n$is the length of the source. Previously the best known results are by Bourgain \cite{Bourgain07}, Yehudayoff \cite{Yehudayoff10} and Li \cite{Li11a}, which require ... more >>> TR15-122 | 29th July 2015 Shiteng Chen, Periklis Papakonstantinou #### Correlation lower bounds from correlation upper bounds We show that for any coprime$m,r$there is a circuit of the form$\text{MOD}_m\circ \text{AND}_{d(n)}$whose correlation with$\text{MOD}_r$is at least$2^{-O\left( \frac{n}{d(n)} \right) }$. This is the first correlation lower bound for arbitrary$m,r$, whereas previously lower bounds were known for prime$m$. Our motivation is the ... more >>> 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 >>> TR15-124 | 3rd August 2015 Vikraman Arvind, Pushkar Joglekar, Raja S #### Noncommutative Valiant's Classes: Structure and Complete Problems Revisions: 1 In this paper we explore the noncommutative analogues,$\mathrm{VP}_{nc}$and$\mathrm{VNP}_{nc}$, of Valiant's algebraic complexity classes and show some striking connections to classical formal language theory. Our main results are the following: (1) We show that Dyck polynomials (defined from the Dyck languages of formal language theory) are complete for ... more >>> TR15-125 | 5th August 2015 Xin Li #### Improved Constructions of Two-Source Extractors Revisions: 2 In a recent breakthrough \cite{CZ15}, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy$k \geq \log^C n$for some large enough constant$C$. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to$k^{\Omega(1)}$, while the error remains$n^{-\Omega(1)}$. ... more >>> TR15-126 | 27th July 2015 Jacob Steinhardt, Gregory Valiant, Stefan Wager #### Memory, Communication, and Statistical Queries Revisions: 1 If a concept class can be represented with a certain amount of memory, can it be efficiently learned with the same amount of memory? What concepts can be efficiently learned by algorithms that extract only a few bits of information from each example? We introduce a formal framework for studying ... more >>> TR15-127 | 7th August 2015 Stasys Jukna, Georg Schnitger #### On the Optimality of Bellman--Ford--Moore Shortest Path Algorithm Revisions: 1 We prove a general lower bound on the size of branching programs over any semiring of zero characteristic, including the (min,+) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum ... more >>> TR15-128 | 10th August 2015 Roee David, Elazar Goldenberg, Robert Krauthgamer #### Local Reconstruction of Low-Rank Matrices and Subspaces Revisions: 2 We study the problem of \emph{reconstructing a low-rank matrix}, where the input is an$n\times m$matrix$M$over a field$\mathbb{F}$and the goal is to reconstruct a (near-optimal) matrix$M'$that is low-rank and close to$M$under some distance function$\Delta$. Furthermore, the reconstruction must be local, ... more >>> TR15-129 | 7th August 2015 Alex Samorodnitsky #### On the entropy of a noisy function Revisions: 1 Let$f$be a nonnegative function on$\{0,1\}^n$. We upper bound the entropy of the image of$f$under the noise operator with noise parameter$\epsilon$by the average entropy of conditional expectations of$f$, given sets of roughly$(1-2\epsilon)^2 \cdot n$variables. As an application, we show that for ... 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 >>> TR15-131 | 10th August 2015 Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson #### Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can ... more >>> TR15-132 | 13th August 2015 Daniel Reichman, Igor Shinkar #### On Percolation and NP-Hardness Revisions: 2 We consider the robustness of computational hardness of problems whose input is obtained by applying independent random deletions to worst-case instances. For some classical NP-hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary graph are ... more >>> TR15-133 | 12th August 2015 Olaf Beyersdorff, Ilario Bonacina, Leroy Chew #### Lower bounds: from circuits to QBF proof systems A general and long-standing belief in the proof complexity community asserts that there is a close connection between progress in lower bounds for Boolean circuits and progress in proof size lower bounds for strong propositional proof systems. Although there are famous examples where a transfer from ideas and techniques from ... more >>> TR15-134 | 19th August 2015 Fu Li, Iddo Tzameret, Zhengyu Wang #### Characterizing Propositional Proofs as Non-Commutative Formulas Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the ... more >>> TR15-135 | 19th August 2015 Arnab Bhattacharyya, Palash Dey #### Fishing out Winners from Vote Streams Revisions: 1 We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of$n$votes on$m$candidates into a small space data structure so as to be able to obtain the winner determined ... 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 >>> TR15-137 | 22nd August 2015 Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito #### On the Role of Shared Randomness in Simultaneous Communication Two parties wish to carry out certain distributed computational tasks, and they are given access to a source of correlated random bits. It allows the parties to act in a correlated manner, which can be quite useful. But what happens if the shared randomness is not perfect? In this work, ... more >>> TR15-138 | 25th August 2015 Michal Koucky #### Nonuniform catalytic space and the direct sum for space Revisions: 1 This paper initiates the study of$k$-catalytic branching programs, a nonuniform model of computation that is the counterpart to the uniform catalytic space model of Buhrman, Cleve, Koucky, Loff and Speelman (STOC 2014). A$k$-catalytic branching program computes$k$boolean functions simultaneously on the same$n$-bit input. Each function has ... more >>> TR15-139 | 25th August 2015 Eli Ben-Sasson, Gal Maor #### Lower bound for communication complexity with no public randomness We give a self contained proof of a logarithmic lower bound on the communication complexity of any non redundant function, given that there is no access to shared randomness. This bound was first stated in Yao's seminal paper [STOC 1979], but no full proof appears in the literature. Our proof ... more >>> TR15-140 | 26th August 2015 Adam Case, Jack H. Lutz, Donald Stull #### Reachability Problems for Continuous Chemical Reaction Networks Chemical reaction networks (CRNs) model the behavior of molecules in a well-mixed system. The emerging field of molecular programming uses CRNs not only as a descriptive tool, but as a programming language for chemical computation. Recently, Chen, Doty and Soloveichik introduced a new model of chemical kinetics, rate-independent continuous CRNs ... more >>> TR15-141 | 26th August 2015 Pushkar Joglekar, Aravind N.R. #### On the expressive power of read-once determinants We introduce and study the notion of read-$k$projections of the determinant: a polynomial$f \in \mathbb{F}[x_1, \ldots, x_n]$is called a {\it read-$k$projection of determinant} if$f=det(M)$, where entries of matrix$M$are either field elements or variables such that each variable appears at most$k$times in ... more >>> TR15-142 | 28th August 2015 Srikanth Srinivasan #### A Compression Algorithm for$AC^0[\oplus]$circuits using Certifying Polynomials A recent work of Chen, Kabanets, Kolokolova, Shaltiel and Zuckerman (CCC 2014, Computational Complexity 2015) introduced the Compression problem for a class$\mathcal{C}$of circuits, defined as follows. Given as input the truth table of a Boolean function$f:\{0,1\}^n \rightarrow \{0,1\}$that has a small (say size$s$) circuit from ... more >>> TR15-143 | 31st August 2015 Benjamin Rossman #### The Average Sensitivity of Bounded-Depth Formulas We show that unbounded fan-in boolean formulas of depth$d+1$and size$s$have average sensitivity$O(\frac{1}{d}\log s)^d$. In particular, this gives a tight$2^{\Omega(d(n^{1/d}-1))}$lower bound on the size of depth$d+1$formulas computing the PARITY function. These results strengthen the corresponding$2^{\Omega(n^{1/d})}$and$O(\log s)^d$bounds for circuits ... more >>> TR15-144 | 1st September 2015 Raghu Meka #### Explicit resilient functions matching Ajtai-Linial Revisions: 1 A Boolean function on n variables is q-resilient if for any subset of at most q variables, the function is very likely to be determined by a uniformly random assignment to the remaining n-q variables; in other words, no coalition of at most q variables has significant influence on the ... 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 >>> TR15-146 | 7th September 2015 Elette Boyle, Moni Naor #### Is There an Oblivious RAM Lower Bound? Revisions: 1 An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e. for every input the observed locations accessed are similarly distributed. Great progress has been made in recent years in minimizing the overhead of ORAM constructions, with the goal of ... more >>> TR15-147 | 8th September 2015 Alexander A. Sherstov #### The Power of Asymmetry in Constant-Depth Circuits The threshold degree of a Boolean function$f$is the minimum degree of a real polynomial$p$that represents$f$in sign:$f(x)\equiv\mathrm{sgn}\; p(x)$. Introduced in the seminal work of Minsky and Papert (1969), this notion is central to some of the strongest algorithmic and complexity-theoretic results for more >>> TR15-148 | 9th September 2015 Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider #### Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility Revisions: 1 We introduce the Nondeterministic Strong Exponential Time Hypothesis (NSETH) as a natural extension of the Strong Exponential Time Hypothesis (SETH). We show that both refuting and proving NSETH would have interesting consequences. In particular we show that disproving NSETH would ... more >>> TR15-149 | 8th September 2015 Mohammad Hajiabadi, Bruce Kapron #### Gambling, Computational Information, and Encryption Security We revisit the question, originally posed by Yao (1982), of whether encryption security may be characterized using computational information. Yao provided an affirmative answer, using a compression-based notion of computational information to give a characterization equivalent to the standard computational notion of semantic security. We give two other equivalent characterizations. ... more >>> TR15-150 | 13th September 2015 Gaurav Sinha #### Reconstruction of$\Sigma\Pi\Sigma(2)$Circuits over Reals Revisions: 3 Reconstruction of arithmertic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing$\Sigma\Pi\Sigma(2)$circuits over$\R$, i.e. depth$-3$circuits with fan-in$2$at the top addition ... more >>> TR15-151 | 14th September 2015 Eshan Chattopadhyay, David Zuckerman #### New Extractors for Interleaved Sources Revisions: 1 We study how to extract randomness from a$C$-interleaved source, that is, a source comprised of$C$independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields: (1) For some$\delta>0, c > 0$, explicit extractors for$2$-interleaved sources on$\{ ... 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 >>>

TR15-153 | 21st September 2015
Tim Roughgarden

#### Computing Equilibria: A Computational Complexity Perspective

Computational complexity is the subfield of computer science that rigorously studies the intrinsic difficulty of computational problems. This survey explains how complexity theory defines “hard problems”; applies these concepts to several equilibrium computation problems; and discusses implications for computation, games, and behavior. We assume minimal prior background in computer science.

... more >>>

TR15-154 | 22nd September 2015
Neeraj Kayal, Vineet Nair, Chandan Saha

#### Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following:

1. There exists an explicit $n$-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) ... more >>>

TR15-155 | 22nd September 2015
Venkatesan Guruswami, Euiwoong Lee

#### Nearly Optimal NP-Hardness of Unique Coverage

The {\em Unique Coverage} problem, given a universe $V$ of elements and a collection $E$ of subsets of $V$, asks to find $S \subseteq V$ to maximize the number of $e \in E$ that intersects $S$ in {\em exactly one} element. When each $e \in E$ has cardinality at most ... more >>>

TR15-156 | 21st September 2015
Tim Roughgarden

#### Communication Complexity (for Algorithm Designers)

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

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

TR15-157 | 1st September 2015
Thomas O'Neil

#### Representation-Independent Fixed Parameter Tractability for Vertex Cover and Weighted Monotone Satisfiability

A symmetric representation for a set of objects requires the same amount of space for the set as for its complement. Complexity classifications that are based on the length of the input can depend on whether the representation is symmetric. In this article we describe a symmetric representation scheme for ... 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-159 | 28th September 2015
Juraj Hromkovic

#### Why the Concept of Computational Complexity is Hard for Verifiable Mathematics

Mathematics was developed as a strong research instrument with fully verifiable argumentations. We call any formal theory based on syntactic rules that enables to algorithmically verify for any given text whether it is a proof or not algorithmically verifiable mathematics (AV-mathematics for short). We say that a decision problem L ... 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 >>>

TR15-161 | 24th September 2015
Chaoping Xing, chen yuan

#### A new class of rank-metric codes and their list decoding beyond the unique decoding radius

Compared with classical block codes, efficient list decoding of rank-metric codes seems more difficult. The evidences to support this view include: (i) so far people have not found polynomial time list decoding algorithms of rank-metric codes with decoding radius beyond $(1-R)/2$ (where $R$ is the rate of code) if ratio ... more >>>

TR15-162 | 9th October 2015
Eric Allender, Joshua Grochow, Cris Moore

#### Graph Isomorphism and Circuit Size

Revisions: 1

We show that the Graph Automorphism problem is ZPP-reducible to MKTP, the problem of minimizing time-bounded Kolmogorov complexity. MKTP has previously been studied in connection with the Minimum Circuit Size Problem (MCSP) and is often viewed as essentially a different encoding of MCSP. All prior reductions to MCSP have applied ... more >>>

TR15-163 | 11th October 2015
James Aisenberg, Maria Luisa Bonet, Sam Buss

#### 2-D Tucker is PPA complete

The 2-D Tucker search problem is shown to be PPA-hard under many-one reductions; therefore it is complete for PPA. The same holds for $k$-D Tucker for all $k\ge 2$. This corrects a claim in the literature that the Tucker search problem is in PPAD.

more >>>

TR15-164 | 13th October 2015
Pavel Hrubes, Amir Yehudayoff

#### On isoperimetric profiles and computational complexity

The isoperimetric profile of a graph is a function that measures, for an integer $k$, the size of the smallest edge boundary over all sets of vertices of size $k$. We observe a connection between isoperimetric profiles and computational complexity. We illustrate this connection by an example from communication complexity, ... more >>>

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

#### Towards Optimal Deterministic Coding for Interactive Communication

Revisions: 1

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

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

TR15-166 | 17th October 2015
Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov

#### A better-than-$3n$ lower bound for the circuit complexity of an explicit function

Revisions: 1

We consider Boolean circuits over the full binary basis. We prove a $(3+\frac{1}{86})n-o(n)$ lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the $3n-o(n)$ bound of Norbert Blum (1984). The proof is based on the gate ... more >>>

TR15-167 | 15th October 2015
Mika Göös, T.S. Jayram

#### A Composition Theorem for Conical Juntas

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two applications:

$\bullet~$ $\textbf{AND-OR trees}$: We show a near-optimal $\tilde{\Omega}(n^{0.753...})$ randomised communication lower bound ... more >>>

TR15-168 | 18th October 2015
Gillat Kol

#### Interactive Compression for Product Distributions

We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol ... more >>>

TR15-169 | 23rd October 2015
Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson

#### Randomized Communication vs. Partition Number

Revisions: 1

We show that \emph{randomized} communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal \emph{randomized} lower bounds for the Clique vs.\ Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\"o\"os, Pitassi, and Watson, {\small FOCS~2015}).

more >>>

TR15-170 | 26th October 2015
Alexander Golovnev, Alexander Kulikov

#### Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds

In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An $(n,k,s)$-quadratic disperser is a function on $n$ variables that is not constant on any subset of $\mathbb{F}_2^n$ of size at least $s$ ... more >>>

TR15-171 | 28th October 2015
Joshua Grochow

#### Monotone projection lower bounds from extended formulation lower bounds

In this short note, we show that the permanent is not complete for non-negative polynomials in $VNP_{\mathbb{R}}$ under monotone p-projections. In particular, we show that Hamilton Cycle polynomial and the cut polynomials are not monotone p-projections of the permanent. To prove this we introduce a new connection between monotone projections ... 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 >>>

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

TR15-174 | 18th October 2015
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

#### Complexity of distributions and average-case hardness

We address a natural question in average-case complexity: does there exist a language $L$ such that for all easy distributions $D$ the distributional problem $(L, D)$ is easy on the average while there exists some more hard distribution $D'$ such that $(L, D')$ is hard on the average? We consider ... more >>>

TR15-175 | 5th November 2015
Scott Aaronson, Shalev Ben-David, Robin Kothari

#### Separations in query complexity using cheat sheets

We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity ... more >>>

TR15-176 | 6th November 2015
Vikraman Arvind, Raja S

#### Some Lower Bound Results for Set-Multilinear Arithmetic Computations

Revisions: 1

In this paper, we study the structure of set-multilinear arithmetic
circuits and set-multilinear branching programs with the aim of
showing lower bound results. We define some natural restrictions of
these models for which we are able to show lower bound results. Some
of our results extend existing lower bounds, while ... more >>>

TR15-177 | 9th November 2015
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

#### Bipartite Perfect Matching is in quasi-NC

Revisions: 2

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>

TR15-178 | 10th November 2015

#### Extractors for Sumset Sources

We propose a new model of weak random sources which we call sumset sources. A sumset source $\mathbf{X}$ is the sum of $C$ independent sources $\mathbf{X}_1,\ldots,\mathbf{X}_C$, where each $\mathbf{X}_i$ is an $n$-bit source with min-entropy $k$. We show that extractors for this class of sources can be used to give ... 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-180 | 4th November 2015
Bo Tang, Jiapeng Zhang

#### Barriers to Black-Box Constructions of Traitor Tracing Systems

Reducibility between different cryptographic primitives is a fundamental problem in modern cryptography. As one of the primitives, traitor tracing systems help content distributors recover the identities of users that collaborated in the pirate construction by tracing pirate decryption boxes. We present the first negative result on designing efficient traitor tracing ... more >>>

TR15-181 | 13th November 2015
Neeraj Kayal, Chandan Saha, Sébastien Tavenas

#### On the size of homogeneous and of depth four formulas with low individual degree

Let $r \geq 1$ be an integer. Let us call a polynomial $f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}]$ as a multi-$r$-ic polynomial if the degree of $f$ with respect to any variable is at most $r$ (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output ... more >>>

TR15-182 | 13th November 2015
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

#### Bounded Indistinguishability and the Complexity of Recovering Secrets

Revisions: 1

We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by ... more >>>

TR15-183 | 16th November 2015
Gil Cohen

#### Non-Malleable Extractors - New Tools and Improved Constructions

A non-malleable extractor is a seeded extractor with a very strong guarantee - the output of a non-malleable extractor obtained using a typical seed is close to uniform even conditioned on the output obtained using any other seed. The first contribution of this paper consists of two new and improved ... more >>>

TR15-184 | 21st November 2015
Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

#### Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs

Read-$k$ oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs).
In this work, we give an exponential lower bound of $\exp(n/k^{O(k)})$ on the width of any read-$k$ oblivious ABP computing some explicit multilinear polynomial $f$ that is computed by a ... more >>>

TR15-185 | 24th November 2015
Arnab Bhattacharyya, Sivakanth Gopi

#### Lower bounds for constant query affine-invariant LCCs and LTCs

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is ... more >>>

TR15-186 | 24th November 2015
Benny Applebaum, Pavel Raykov

#### On the Relationship between Statistical Zero-Knowledge and Statistical Randomized Encodings

\emph{Statistical Zero-knowledge proofs} (Goldwasser, Micali and Rackoff, SICOMP 1989) allow a computationally-unbounded server to convince a computationally-limited client that an input $x$ is in a language $\Pi$ without revealing any additional information about $x$ that the client cannot compute by herself. \emph{Randomized encoding} (RE) of functions (Ishai and Kushilevitz, FOCS ... more >>>

TR15-187 | 24th November 2015
Nir Bitansky, Vinod Vaikuntanathan

#### A Note on Perfect Correctness by Derandomization

Revisions: 1

In this note, we show how to transform a large class of erroneous cryptographic schemes into perfectly correct ones. The transformation works for schemes that are correct on every input with probability noticeably larger than half, and are secure under parallel repetition. We assume the existence of one-way functions ... more >>>

TR15-188 | 24th November 2015
Daniel Kane, Ryan Williams

#### Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for ... more >>>

TR15-189 | 25th November 2015
Shay Moran, Cyrus Rashtchian

#### Shattered Sets and the Hilbert Function

Revisions: 2

We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result ... more >>>

TR15-190 | 2nd November 2015
Esther Ezra, Shachar Lovett

#### On the Beck-Fiala Conjecture for Random Set Systems

Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems $(X,\Sigma)$, where each element $x \in X$ lies in $t$ randomly selected sets of $\Sigma$, where $t$ is an integer parameter. We provide new bounds in two regimes of parameters. We ... 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 >>>

TR15-192 | 26th November 2015
Ruiwen Chen, Rahul Santhanam

#### Satisfiability on Mixed Instances

The study of the worst-case complexity of the Boolean Satisfiability (SAT) problem has seen considerable progress in recent years, for various types of instances including CNFs \cite{PPZ99, PPSZ05, Sch99, Sch05}, Boolean formulas \cite{San10} and constant-depth circuits \cite{IMP12}. We systematically investigate the complexity of solving {\it mixed} instances, where different parts ... more >>>

TR15-193 | 26th November 2015
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket

#### On the hardness of learning sparse parities

This work investigates the hardness of computing sparse solutions to systems of linear equations over $\mathbb{F}_2$. Consider the $k$-EvenSet problem: given a homogeneous system of linear equations over $\mathbb{F}_2$ on $n$ variables, decide if there exists a nonzero solution of Hamming weight at most $k$ (i.e. a $k$-sparse solution). While ... 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 >>>

TR15-195 | 3rd December 2015
Robin Kothari

#### Nearly optimal separations between communication (or query) complexity and partitions

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) ... more >>>

TR15-196 | 4th December 2015
Andris Ambainis

#### Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Revisions: 1

We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials.
Namely, a partial Boolean function $f$ is computable by a 1-query quantum algorithm with error bounded by $\epsilon<1/2$ iff $f$ can be approximated by a degree-2 polynomial with error bounded by $\epsilon'<1/2$.
This result holds for two ... more >>>

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

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

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

Our ... more >>>

TR15-198 | 30th November 2015
Shuichi Hirahara, Osamu Watanabe

#### Limits of Minimum Circuit Size Problem as Oracle

Revisions: 1

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a ... more >>>

TR15-199 | 7th December 2015

#### Relaxed partition bound is quadratically tight for product distributions

Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $\mu$ on $\{0,1\}^n \times \{0,1\}^n$, we show that $${{CC}}^\mu_{0.49}(f) = O\left(\left(\log {{rprt}}_{1/4}(f) \cdot \log \log {{rprt}}_{1/4}(f)\right)^2\right),$$ where ${{CC}^\mu_\varepsilon(f)$ is the distributional communication complexity with error at most $\varepsilon$ under the distribution $\mu$ and ... 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 >>>

TR15-201 | 10th December 2015
C Ramya, Raghavendra Rao B V

#### Limitations of sum of products of Read-Once Polynomials

Revisions: 1

We study limitations of polynomials computed by depth two circuits built over read-once polynomials (ROPs) and depth three syntactically multi-linear formulas.
We prove an exponential lower bound for the size of the $\Sigma\Pi^{[N^{1/30}]}$ arithmetic circuits built over syntactically multi-linear $\Sigma\Pi\Sigma^{[N^{8/15}]}$ arithmetic circuits computing a product of variable ... more >>>

TR15-202 | 11th December 2015
Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

#### Building above read-once polynomials: identity testing and hardness of representation

Polynomial Identity Testing (PIT) algorithms have focused on
polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted
formulas (ROFs) and are the simplest of read-restricted polynomials.
Building structures above these, we show the following:
\begin{enumerate}
\item A deterministic polynomial-time non-black-box ... more >>>

TR15-203 | 13th December 2015
Scott Aaronson, Shalev Ben-David

#### Sculpting Quantum Speedups

Given a problem which is intractable for both quantum and classical algorithms, can we find a sub-problem for which quantum algorithms provide an exponential advantage? We refer to this problem as the "sculpting problem." In this work, we give a full characterization of sculptable functions in the query complexity setting. ... more >>>

TR15-204 | 14th December 2015
Meena Mahajan, Anuj Tawari

#### Sums of read-once formulas: How many summands suffice?

Revisions: 2

An arithmetic read-once formula (ROF) is a formula (circuit of fan-out
1) over
$+, \times$ where each variable labels at most one leaf.
Every multilinear polynomial can be expressed as the sum of ROFs.
In this work, we prove, for certain multilinear polynomials,
a tight lower bound ... more >>>

TR15-205 | 15th December 2015
Emanuele Viola

#### Quadratic maps are hard to sample

This note proves the existence of a quadratic GF(2) map
$p : \{0,1\}^n \to \{0,1\}$ such that no constant-depth circuit
of size $\poly(n)$ can sample the distribution $(u,p(u))$
for uniform $u$.

more >>>

TR15-206 | 15th December 2015
Benny Applebaum, Pavel Raykov

#### From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back

Goos, Pitassi and Watson (ITCS, 2015) have recently introduced the notion of Zero-Information Arthur-Merlin Protocols (ZAM). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs $x$ and $y$ respectively, and Merlin, the ... more >>>

TR15-207 | 23rd December 2015
Ofer Grossman

#### Finding Primitive Roots Pseudo-Deterministically

Pseudo-deterministic algorithms are randomized search algorithms which output unique solutions (i.e., with high probability they output the same solution on each execution). We present a pseudo-deterministic algorithm that, given a prime $p,$ finds a primitive root modulo $p$ in time $\exp(O(\sqrt{\log p \log \log p}))$. This improves upon the previous ... more >>>

TR15-208 | 26th December 2015
Shafi Goldwasser, Ofer Grossman

#### Perfect Bipartite Matching in Pseudo-Deterministic $RNC$

Revisions: 2

In this paper we present a pseudo-deterministic $RNC$ algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses $poly(n)$ processors, $poly({\log n})$ depth, $poly(\log n)$ random bits, and outputs for each bipartite input graph a unique perfect matching with high probability. That ... more >>>

TR15-209 | 29th December 2015
Eli Ben-Sasson, Gal Maor

#### On the information leakage of public-output protocols

In this paper three complexity measures are studied: (i) internal information, (ii) external information, and (iii) a measure called here "output information". Internal information (i) measures the counter-party privacy-loss inherent in a communication protocol. Similarly, the output information (iii) measures the reduction in input-privacy that is inherent when the output ... more >>>

ISSN 1433-8092 | Imprint