Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2013:
All reports in year 2013:
TR13-001 | 2nd January 2013
Gillat Kol, Ran Raz

#### Interactive Channel Capacity

Revisions: 1

We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel), and the communication complexity of the same problem over the binary symmetric channel with noise rate $\epsilon$, where ... more >>>

TR13-002 | 31st December 2012
Venkatesan Guruswami, Krzysztof Onak

#### Superlinear lower bounds for multipass graph processing

Revisions: 3

We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:

* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),

* testing if two ... more >>>

TR13-003 | 2nd January 2013
Eric Miles, Emanuele Viola

#### Shielding circuits with groups

Revisions: 2

We show how to efficiently compile any given circuit $C$
into a leakage-resistant circuit $\widehat{C}$ such that any
function on the wires of $\widehat{C}$ that leaks information
during a computation $\widehat{C}(x)$ yields advantage in
computing the product of $|\widehat{C}|^{\Omega(1)}$ elements
of the alternating group $A_u$. In combination with new
compression ... more >>>

TR13-004 | 11th November 2012
A. C. Cem Say, Abuzer Yakaryilmaz

#### Finite state verifiers with constant randomness

We give a new characterization of NL as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. ... more >>>

TR13-005 | 2nd January 2013
Alexander A. Sherstov

#### Communication Lower Bounds Using Directional Derivatives

We prove that the set disjointness problem has randomized communication complexity
$\Omega(\sqrt{n}/2^{k}k)$ in the number-on-the-forehead model with $k$ parties, a quadratic improvement
on the previous bound $\Omega(\sqrt{n}/2^{k})^{1/2}$. Our result remains valid for quantum
protocols, where it is essentially tight. Proving it was an open problem since 1997, ... more >>>

TR13-006 | 8th January 2013
Balagopal Komarath, Jayalal Sarma

#### Pebbling, Entropy and Branching Program Size Lower Bounds

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al.(2011). Proving an exponential lower bound for the size of the non-deterministic thrifty branching programs would separate NL from P under the thrifty hypothesis. In this ... more >>>

TR13-007 | 8th January 2013
Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand

#### Short lists with short programs in short time

Revisions: 1

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on ... more >>>

TR13-008 | 7th January 2013
Adam Klivans, Raghu Meka

#### Moment-Matching Polynomials

We give a new framework for proving the existence of low-degree, polynomial approximators for Boolean functions with respect to broad classes of non-product distributions. Our proofs use techniques related to the classical moment problem and deviate significantly from known Fourier-based methods, which require the underlying distribution to have some product ... more >>>

TR13-009 | 9th January 2013
Zahra Jafargholi, Emanuele Viola

#### 3SUM, 3XOR, Triangles

Revisions: 1

We show that if one can solve 3SUM on a set of size $n$
in time $n^{1+\epsilon}$ then one can list $t$ triangles in a
graph with $m$ edges in time $\tilde O(m^{1+\epsilon}t^{1/3+\epsilon'})$ for any $\epsilon' > 0$. This is a
reversal of Patrascu's reduction from 3SUM to
listing triangles ... more >>>

TR13-010 | 4th January 2013
Yang Liu, Shengyu Zhang

#### Quantum and randomized communication complexity of XOR functions in the SMP model

Communication complexity of XOR functions $f (x \oplus y)$ has attracted increasing attention in recent years, because of its connections to Fourier analysis, and its exhibition of exponential separations between classical and quantum communication complexities of total functions.However, the complexity of certain basic functions still seems elusive especially in the ... more >>>

TR13-011 | 10th January 2013

#### Multilinear Complexity is Equivalent to Optimal Tester Size

In this paper we first show that Tester for an $F$-algebra $A$
and multilinear forms (see Testers and their Applications ECCC 2012) is equivalent to multilinear
algorithm for the product of elements in $A$
(see Algebraic
complexity theory. vol. 315, Springer-Verlag). Our
result is constructive in deterministic polynomial time. ... more >>>

TR13-012 | 16th January 2013
Hasan Abasi, Nader Bshouty

#### A Simple Algorithm for Undirected Hamiltonicity

We develop a new algebraic technique that gives a simple randomized algorithm for the simple $k$-path problem with the same complexity $O^*(1.657^k)$ as in [A. Bj\"orklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010, pp. 173--182, (2010). A. Bj\"orklund, T. Husfeldt, P. Kaski, M. Koivisto. Narrow sieves for parameterized paths and ... more >>>

TR13-013 | 18th January 2013
Daniel Apon, Jonathan Katz, Alex Malozemoff

#### One-Round Multi-Party Communication Complexity of Distinguishing Sums

Revisions: 1

We consider an instance of the following problem: Parties $P_1,..., P_k$ each receive an input $x_i$, and a coordinator (distinct from each of these parties) wishes to compute $f(x_1,..., x_k)$ for some predicate $f$. We are interested in one-round protocols where each party sends a single message to the coordinator; ... more >>>

TR13-014 | 11th January 2013
Zvika Brakerski, Moni Naor

#### Fast Algorithms for Interactive Coding

Consider two parties who wish to communicate in order to execute some interactive protocol $\pi$. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits as he pleases, thus interrupting the execution of ... more >>>

TR13-015 | 18th January 2013
Iordanis Kerenidis, Mathieu Laurière, David Xiao

#### New lower bounds for privacy in communication protocols

Communication complexity is a central model of computation introduced by Yao in 1979, where
two players, Alice and Bob, receive inputs x and y respectively and want to compute $f(x; y)$ for some fixed
function f with the least amount of communication. Recently people have revisited the question of the ... more >>>

TR13-016 | 17th January 2013
Olaf Beyersdorff

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

Revisions: 1

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

TR13-017 | 23rd January 2013
Pratik Worah

#### A Short Excursion into Semi-Algebraic Hierarchies

This brief survey gives a (roughly) self-contained overview of some complexity theoretic results about semi-algebraic proof systems and related hierarchies and the strong connections between them. The article is not intended to be a detailed survey on "Lift and Project" type optimization hierarchies (cf. Chlamtac and Tulsiani) or related proof ... more >>>

TR13-018 | 29th January 2013
Luke Friedman, Yixin Xu

#### Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams

A propositional proof system based on ordered binary decision diagrams (OBDDs) was introduced by Atserias et al. Krajicek proved exponential lower bounds for a strong variant of this system using feasible interpolation, and Tveretina et al. proved exponential lower bounds for restricted versions of this system for refuting formulas derived ... more >>>

TR13-019 | 31st January 2013
Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf

#### On Two-Level Poset Games

We consider the complexity of determining the winner of a finite, two-level poset game.
This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete.
We give a simple formula allowing one to compute the status ... more >>>

TR13-020 | 2nd February 2013
Tom Gur, Ran Raz

#### Arthur-Merlin Streaming Complexity

We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical $\mathcal{AM}$ streaming algorithm for a wide class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it.

... more >>>

TR13-021 | 5th February 2013
Kristoffer Arnsfelt Hansen, Vladimir Podolskii

#### Polynomial threshold functions and Boolean threshold circuits

We study the complexity of computing Boolean functions on general
Boolean domains by polynomial threshold functions (PTFs). A typical
example of a general Boolean domain is $\{1,2\}^n$. We are mainly
interested in the length (the number of monomials) of PTFs, with
their degree and weight being of secondary interest. We ... more >>>

TR13-022 | 5th February 2013
Michael Viderman

#### Strong LTCs with inverse poly-log rate and constant soundness

Revisions: 1

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

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

#### Approximating the AND-OR Tree

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

TR13-024 | 7th February 2013
Valentine Kabanets, Antonina Kolokolova

#### Compression of Boolean Functions

We consider the problem of compression for easy'' Boolean functions: given the truth table of an $n$-variate Boolean function $f$ computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time $\poly(2^n)$ a circuit $C$ (no restriction on the type of $C$) computing $f$ so ... more >>>

TR13-025 | 6th February 2013
Xin Li

#### Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy

Revisions: 1

We study the problem of constructing explicit extractors for independent general weak random sources. Given weak sources on $n$ bits, the probabilistic method shows that there exists a deterministic extractor for two independent sources with min-entropy as small as $\log n+O(1)$. However, even to extract from a constant number of ... more >>>

TR13-026 | 11th February 2013
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

#### Arithmetic circuits: A chasm at depth three

Revisions: 1

We show that, over $\mathbb{C}$, if an $n$-variate polynomial of degree $d = n^{O(1)}$ is computable by an arithmetic circuit of size $s$ (respectively by an algebraic branching program of size $s$) then it can also be computed by a depth three circuit (i.e. a $\Sigma \Pi \Sigma$-circuit) of size ... more >>>

TR13-027 | 29th January 2013
Luke Friedman

#### A Framework for Proving Proof Complexity Lower Bounds on Random CNFs Using Encoding Techniques

Propositional proof complexity is an area of complexity theory that addresses the question of whether the class NP is closed under complement, and also provides a theoretical framework for studying practical applications such as SAT solving.
Some of the most well-studied contradictions are random $k$-CNF formulas where each clause of ... more >>>

TR13-028 | 14th February 2013
Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma

#### Arithmetic Circuit Lower Bounds via MaxRank

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove
super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results :

$\bullet$ As ... more >>>

TR13-029 | 19th February 2013
Deeparnab Chakrabarty, C. Seshadhri

#### A {\huge ${o(n)}$} monotonicity tester for Boolean functions over the hypercube

Revisions: 1

Given oracle access to a Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$, we design a randomized tester that takes as input a parameter $\eps>0$, and outputs {\sf Yes} if the function is monotone, and outputs {\sf No} with probability $>2/3$, if the function is $\eps$-far from monotone. That is, $f$ needs to ... more >>>

TR13-030 | 20th February 2013

#### Absolutely Sound Testing of Lifted Codes

In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of "affine-invariant'' codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes ... more >>>

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

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

Revisions: 2

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

In ... more >>>

TR13-032 | 26th February 2013
Mark Bun, Justin Thaler

#### Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Revisions: 2

The $\epsilon$-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 $\epsilon$ in the $\ell_\infty$ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an ... more >>>

TR13-033 | 1st March 2013
Michael Forbes, Amir Shpilka

#### Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

Revisions: 1

Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In ... more >>>

TR13-034 | 2nd March 2013
Louay Bazzi, Nagi Nahas

#### Small-bias is not enough to hit read-once CNF

Small-bias probability spaces have wide applications in pseudorandomness which naturally leads to the study of their limitations. Constructing a polynomial complexity hitting set for read-once CNF formulas is a basic open problem in pseudorandomness. We show in this paper that this goal is not achievable using small-bias spaces. Namely, we ... more >>>

TR13-035 | 6th March 2013
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

#### Direct product via round-preserving compression

Revisions: 1

We obtain a strong direct product theorem for two-party bounded round communication complexity.
Let suc_r(\mu,f,C) denote the maximum success probability of an r-round communication protocol that uses
at most C bits of communication in computing f(x,y) when (x,y)~\mu.
Jain et al. [JPY12] have recently showed that if
more >>>

TR13-036 | 13th March 2013
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

#### Lower Bounds for Testing Properties of Functions on Hypergrid Domains

Revisions: 1

We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.
Our lower bounds also apply to the more restricted setting ... more >>>

TR13-037 | 15th March 2013
Alexander Knop

#### Circuit Lower Bounds for Heuristic MA

Revisions: 2

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

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

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

Revisions: 1

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

TR13-039 | 18th March 2013
Arturs Backurs, Mohammad Bavarian

#### On the sum of $L1$ influences

Revisions: 2

For a multilinear polynomial $p(x_1,...x_n)$, over the reals, the $L1$-influence is defined to be $\sum_{i=1}^n E_x\left[\frac{|p(x)-p(x^i)|}{2} \right]$, where $x^i$ is $x$ with $i$-th bit swapped. If $p$ maps $\{-1,1\}^n$ to $[-1,1]$, we prove that the $L1$-influence of $p$ is upper bounded by a function of its degree (and independent of ... more >>>

TR13-040 | 11th March 2013
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie

#### The Algebraic Theory of Parikh Automata

Revisions: 2

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theory of typed monoids is used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh ... more >>>

TR13-041 | 14th March 2013
Igor Sergeev

#### On the complexity of parallel prefix circuits

It is shown that complexity of implementation of prefix sums of $m$ variables (i.e. functions $x_1 \cdot \ldots\cdot x_i$, $1\le i \le m$) by circuits of depth $\lceil \log_2 m \rceil$ in the case $m=2^n$ is exactly $$3.5\cdot2^n - (8.5+3.5(n \bmod 2))2^{\lfloor n/2\rfloor} + n + 5.$$ As a consequence, ... more >>>

TR13-042 | 25th March 2013
Siu Man Chan

#### Just a Pebble Game

The two-player pebble game of Dymond–Tompa is identified as a barrier for existing techniques to save space or to speed up parallel algorithms for evaluation problems.

Many combinatorial lower bounds to study L versus NL and NC versus P under different restricted settings scale in the same way as the ... more >>>

TR13-043 | 25th March 2013
Oded Goldreich, Avi Wigderson

#### On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Revisions: 1

We propose that multi-linear functions of relatively low degree
over GF(2) may be good candidates for obtaining exponential
lower bounds on the size of constant-depth Boolean circuits
(computing explicit functions).
Specifically, we propose to move gradually from linear functions
to multilinear ones, and conjecture that, for any $t\geq2$,
more >>>

TR13-044 | 25th March 2013
Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

#### Shared Randomness and Quantum Communication in the Multi-Party Model

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case.

First, we demonstrate a hierarchy of modes of shared ... more >>>

TR13-045 | 26th March 2013
Marek Karpinski, Michael Lampis, Richard Schmied

#### New Inapproximability Bounds for TSP

In this paper, we study the approximability of the metric Traveling Salesman Problem, one of the most widely studied problems in combinatorial optimization. Currently, the best known hardness of approximation bounds are 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and ... more >>>

TR13-046 | 27th March 2013
Venkatesan Guruswami, Chaoping Xing

#### Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets

We construct a new list-decodable family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. The function fields underlying these codes are constructed using class field theory, specifically Drinfeld modules of rank $1$, and designed to have an automorphism of large order that is used to fold" the AG code. ... more >>>

TR13-047 | 27th March 2013
Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek

#### Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

We investigate the autoreducibility and mitoticity of complete sets for several classes with respect to different polynomial-time and logarithmic-space reducibility notions.

Previous work in this area focused on polynomial-time reducibility notions. Here we obtain new mitoticity and autoreducibility results for the classes EXP and NEXP with respect to some restricted ... more >>>

TR13-048 | 27th March 2013
Jin-Yi Cai, Aaron Gorenstein

#### Matchgates Revisited

We study a collection of concepts and theorems that laid the foundation of matchgate computation. This includes the signature theory of planar matchgates, and the parallel theory of characters of not necessarily planar matchgates. Our aim is to present a unified and, whenever possible, simplified account of this challenging theory. ... more >>>

TR13-049 | 1st April 2013
Amir Shpilka, Ben Lee Volk, Avishay Tal

#### On the Structure of Boolean Functions with Small Spectral Norm

Revisions: 1

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of $f$ is $\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n\to \{0,1\}$ with $\|\hat{f}\|_1=A$.

1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant.

2. ... more >>>

TR13-050 | 1st April 2013
Venkatesan Guruswami, Patrick Xia

#### Polar Codes: Speed of polarization and polynomial gap to capacity

Revisions: 1

We prove that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within $\epsilon > 0$ of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a *polynomial* in $1/\epsilon$. Polar coding gives the *first known explicit construction* with rigorous ... more >>>

TR13-051 | 2nd April 2013
Eric Blais, Li-Yang Tan

#### Approximating Boolean functions with depth-2 circuits

We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function.
In the first direction, our main positive results are the first non-trivial universal upper bounds on ... more >>>

TR13-052 | 3rd April 2013
Sourav Chakraborty, Raghav Kulkarni, Satyanarayana V. Lokam, Nitin Saurabh

#### {Upper Bounds on Fourier Entropy

Revisions: 1

iven a function $f : \{0,1\}^n \to \reals$, its {\em Fourier Entropy} is defined to be $-\sum_S \fcsq{f}{S} \log \fcsq{f}{S}$, where $\fhat$ denotes the Fourier transform of $f$. This quantity arises in a number of applications, especially in the study of Boolean functions. An outstanding open question is a conjecture ... more >>>

TR13-053 | 4th April 2013
Alan Guo

#### High rate locally correctable codes via lifting

Revisions: 1

We present a general framework for constructing high rate error correcting codes that are locally correctable (and hence locally decodable if linear) with a sublinear number of queries, based on lifting codes with respect to functions on the coordinates. Our approach generalizes the lifting of affine-invariant codes of Guo, Kopparty, ... more >>>

TR13-054 | 4th April 2013
Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

#### Average Case Lower Bounds for Monotone Switching Networks

Revisions: 1

An approximate computation of a Boolean function by a circuit or switching network is a computation which computes the function correctly on the majority of the inputs (rather than on all inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many subareas ... more >>>

TR13-055 | 5th April 2013
David Gamarnik, Madhu Sudan

#### Limits of local algorithms over sparse random graphs

Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research ... more >>>

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

#### Common information and unique disjointness

Revisions: 5

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

TR13-057 | 5th April 2013
Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel, David Zuckerman

#### Mining Circuit Lower Bound Proofs for Meta-Algorithms

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an $n$-variate Boolean function $f$ computable by some unknown small circuit ... more >>>

TR13-058 | 5th April 2013
Ilan Komargodski, Ran Raz, Avishay Tal

#### Improved Average-Case Lower Bounds for DeMorgan Formula Size

Revisions: 2

We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every deMorgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013).

Our technical contributions include a theorem that shows that the expected ... more >>>

TR13-059 | 9th April 2013
Lior Gishboliner, Asaf Shapira

#### Deterministic vs Non-deterministic Graph Property Testing

A graph property P is said to be testable if one can check if a graph is close or far from satisfying P using few random local inspections. Property P is said to be non-deterministically testable if one can supply a "certificate" to the fact that a graph satisfies P ... more >>>

TR13-060 | 10th April 2013
Venkatesan Guruswami, Swastik Kopparty

#### Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf F}_q^m$ intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal ... more >>>

TR13-061 | 17th April 2013
Zeev Dvir, Guangda Hu

We prove new upper bounds on the size of families of vectors in $\Z_m^n$ with restricted modular inner products, when $m$ is a large integer. More formally, if $\vec{u}_1,\ldots,\vec{u}_t \in \Z_m^n$ and $\vec{v}_1,\ldots,\vec{v}_t \in \Z_m^n$ satisfy $\langle\vec{u}_i,\vec{v}_i\rangle\equiv0\pmod m$ and $\langle\vec{u}_i,\vec{v}_j\rangle\not\equiv0\pmod m$ for all $i\neq j\in[t]$, we prove that $t \leq ... more >>> TR13-062 | 18th April 2013 Deeparnab Chakrabarty, C. Seshadhri #### An optimal lower bound for monotonicity testing over hypergrids For positive integers$n, d$, consider the hypergrid$[n]^d$with the coordinate-wise product partial ordering denoted by$\prec$. A function$f: [n]^d \mapsto \mathbb{N}$is monotone if$\forall x \prec y$,$f(x) \leq f(y)$. A function$f$is$\varepsilon$-far from monotone if at least an$\varepsilon$-fraction of values must ... more >>> TR13-063 | 19th April 2013 Dung Nguyen, Alan Selman #### Non-autoreducible Sets for NEXP We investigate autoreducibility properties of complete sets for$\cNEXP$under different polynomial reductions. Specifically, we show under some polynomial reductions that there is are complete sets for$\cNEXP$that are not autoreducible. We obtain the following results: - There is a$\reduction{p}{tt}$-complete set for$\cNEXP$that is not$\reduction{p}{btt}$-autoreducible. more >>> TR13-064 | 22nd April 2013 Anat Ganor, Ran Raz #### Space Pseudorandom Generators by Communication Complexity Lower Bounds Revisions: 1 In 1989, Babai, Nisan and Szegedy [BNS92] gave a construction of a pseudorandom generator for logspace, based on lower bounds for multiparty communication complexity. The seed length of their pseudorandom generator was$2^{\Theta(\sqrt n)}\,\,\,$, because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for ... more >>> TR13-065 | 21st April 2013 Yijia Chen, Joerg Flum #### On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P$\ne$NP or NP$\ne$coNP no progress has been achieved using the games. We show that for these problems it is already hard to ... more >>> TR13-066 | 25th April 2013 Marek Karpinski, Richard Schmied #### Approximation Hardness of Graphic TSP on Cubic Graphs We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used ... more >>> TR13-067 | 2nd May 2013 Oded Goldreich #### On Multiple Input Problems in Property Testing Revisions: 1 We consider three types of multiple input problems in the context of property testing. Specifically, for a property$\Pi\subseteq\{0,1\}^n$, a proximity parameter$\epsilon$, and an integer$m$, we consider the following problems: \begin{enumerate} \item Direct$m$-Sum Problem for$\Pi$and$\epsilon$: Given a sequence of$m$inputs, output a sequence ... more >>> TR13-068 | 3rd May 2013 Mrinal Kumar, Shubhangi Saraf #### Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin We study the class of homogenous$\Sigma\Pi\Sigma\Pi(r)$circuits, which are depth 4 homogenous circuits with top fanin bounded by$r$. We show that any homogenous$\Sigma\Pi\Sigma\Pi(r)$circuit computing the permanent of an$n\times n$matrix must have size at least$\exp\left(n^{\Omega(1/r)}\right)$. In a recent result, Gupta, Kamath, Kayal and ... more >>> TR13-069 | 1st May 2013 Kousha Etessami, Alistair Stewart, Mihalis Yannakakis #### A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in product-of-exponentials notation, or equivalently, via arithmetic circuits using only multiplication and division gates, and integer inputs: Input instance: four lists of positive integers:$a_1, \ldots , a_n; \ b_1, \ldots ,b_n; \ ... more >>>

TR13-070 | 4th May 2013
Iddo Tzameret

#### On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation

Revisions: 1

We formalize a combinatorial principle, called the 3XOR principle, due to Feige, Kim and Ofek (2006), as a family of unsatisfiable propositional formulas for which refutations of small size in any propositional proof system that possesses the feasible interpolation property imply an efficient *deterministic* refutation algorithm for random 3SAT with ... more >>>

TR13-071 | 8th May 2013
Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket

#### Inapproximability of Minimum Vertex Cover on $k$-uniform $k$-partite Hypergraphs

We study the problem of computing the minimum vertex cover on $k$-uniform $k$-partite hypergraphs when the $k$-partition is given. On bipartite graphs ($k=2$), the minimum vertex cover can be computed in polynomial time. For $k \ge 3$, this problem is known to be NP-hard. For general $k$, the problem was ... more >>>

TR13-072 | 3rd May 2013
Jan Johannsen

#### Exponential Separations in a Hierarchy of Clause Learning Proof Systems

Resolution trees with lemmas ($\mathrm{RTL}$) are a resolution-based propositional proof system that is related to the DPLL algorithm with clause learning. Its fragments $\mathrm{RTL}(k)$ are related to clause learning algorithms where the width of learned clauses is bounded by $k$.

For every $k$ up to $O(\log n)$, an exponential separation ... more >>>

TR13-073 | 14th May 2013
Oded Goldreich

#### On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing

Revisions: 2

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity
of property testing via communication complexity. They provided a restricted formulation of their methodology
(via simple combining operators'')
and also hinted towards a more general formulation, which we spell ... more >>>

TR13-074 | 9th May 2013
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

#### Helly Circular-Arc Graph Isomorphism is in Logspace

We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Delta trees employed in McConnell's linear time representation algorithm for interval matrices ... more >>>

TR13-075 | 23rd May 2013
Subhash Khot, Madhur Tulsiani, Pratik Worah

#### A Characterization of Strong Approximation Resistance

For a predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|f^{-1}(1)|}{2^k}$, we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP$(f)$, it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range $[\rho(f)-\Omega(1), \rho(f)+\Omega(1)]$.

We present a characterization of ... more >>>

TR13-076 | 15th May 2013
Divesh Aggarwal, Chandan Dubey

#### Improved hardness results for unique shortest vector problem

Revisions: 1

We give several improvements on the known hardness of the unique shortest vector problem in lattices, i.e., the problem of finding a shortest vector in a given lattice given a promise that the shortest vector is unique upto a uniqueness factor $\gamma$.
We give a deterministic reduction from the ... more >>>

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

#### Circuit Lower Bounds in Bounded Arithmetics

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

TR13-078 | 28th May 2013
Tom Gur, Ron Rothblum

#### Non-Interactive Proofs of Proximity

Revisions: 1

We initiate a study of non-interactive proofs of proximity. These proof-systems consist of a verifier that wishes to ascertain the validity of a given statement, using a short (sublinear length) explicitly given proof, and a sublinear number of queries to its input. Since the verifier cannot even read the entire ... more >>>

TR13-079 | 2nd June 2013
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

#### Direct Sum Fails for Zero Error Average Communication

We show that in the model of zero error communication complexity, direct sum fails for average communication complexity as well as for external information cost. Our example also refutes a version of a conjecture by Braverman et al. that in the zero error case amortized communication complexity equals external information ... more >>>

TR13-080 | 4th June 2013
Dmitry Gavinsky, Shachar Lovett

#### En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations

We prove that several measures in communication complexity are equivalent, up to polynomial factors in the logarithm of the rank of the associated matrix: deterministic communication complexity, randomized communication complexity, information cost and zero-communication cost. This shows that in order to prove the log-rank conjecture, it suffices to show that ... more >>>

TR13-081 | 6th June 2013
Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett

#### Non-malleable Codes from Additive Combinatorics

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a ... more >>>

TR13-082 | 6th June 2013
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

#### Some properties are not even partially testable

For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $\epsilon$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, ... more >>>

TR13-083 | 7th June 2013
Miklos Ajtai

#### Lower Bounds for RAMs and Quantifier Elimination

For each natural number $d$ we consider a finite structure ${\bf M}_{d}$ whose universe is the set of all $0,1$-sequence of length $n=2^{d}$, each representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace$ in binary form. The operations included in the structure are the four constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>

TR13-084 | 8th June 2013
Shachar Lovett

#### Communication is bounded by root of rank

Revisions: 1

We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on ... more >>>

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

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

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

TR13-086 | 13th June 2013
Omer Reingold, Thomas Steinke, Salil Vadhan

#### Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

TR13-087 | 4th June 2013
Hamed Hatami, Shachar Lovett

#### Estimating the distance from testable affine-invariant properties

Let $\cal{P}$ be an affine invariant property of functions $\mathbb{F}_p^n \to [R]$ for fixed $p$ and $R$. We show that if $\cal{P}$ is locally testable with a constant number of queries, then one can estimate the distance of a function $f$ from $\cal{P}$ with a constant number of queries. This ... more >>>

TR13-088 | 16th June 2013
Zachary Remscrim, Michael Sipser

#### $AC^0$ Pseudorandomness of Natural Operations

A function $f:\Sigma^{*} \rightarrow \Sigma^{*}$ on strings is $AC^0$-pseudorandom if the pair $(x,\hat f(x))$ is $AC^0$-indistinguishable from a uniformly random pair $(y,z)$ when $x$ is chosen uniformly at random. Here $\hat f(x)$ is the string that is obtained from $f(x)$ by discarding some selected bits from $f(x)$.

It is shown ... more >>>

TR13-089 | 17th June 2013
Abhishek Bhrushundi

#### On testing bent functions

Revisions: 1

A bent function is a Boolean function all of whose Fourier coefficients are equal in absolute value. These functions have been extensively studied in cryptography and play an important role in cryptanalysis and design of cryptographic systems.
We study bent functions in the framework of property testing. In particular, we ... more >>>

TR13-090 | 18th June 2013
Elena Grigorescu, Karl Wimmer, Ning Xie

#### Tight Lower Bounds for Testing Linear Isomorphism

We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. A family of functions $P\subseteq \{\{0,1\}^n \rightarrow \{0,1\}\}$ is linear/affine invariant if for any $f\in P$, it is the case that $f\circ L\in P$ for any linear/affine transformation $L$ of the domain. Motivated by ... more >>>

TR13-091 | 17th June 2013
Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

#### A super-polynomial lower bound for regular arithmetic formulas.

We consider arithmetic formulas consisting of alternating layers of addition $(+)$ and multiplication $(\times)$ gates such that the fanin of all the gates in any fixed layer is the same. Such a formula $\Phi$ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree ... more >>>

TR13-092 | 19th June 2013
Pavel Pudlak, Arnold Beckmann, Neil Thapen

#### Parity Games and Propositional Proofs

Revisions: 1

A propositional proof system is \emph{weakly automatizable} if there
is a polynomial time algorithm which separates satisfiable formulas
from formulas which have a short refutation in the system, with
respect to a given length bound. We show that if the resolution
proof system is weakly automatizable, ... more >>>

TR13-093 | 21st June 2013
Anna Gal, Jing-Tang Jang

#### A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators

Spira showed that any Boolean formula of size $s$ can be simulated in depth $O(\log s)$. We generalize Spira's theorem and show that any Boolean circuit of size $s$ with segregators of size $f(s)$ can be simulated in depth $O(f(s)\log s)$. If the segregator size is at least $s^{\varepsilon}$ for ... more >>>

TR13-094 | 13th June 2013
Brendan Juba

#### On Non-automatizability in PAC-Semantics

We consider the proof search ("automatizability") problem for integrated learning and reasoning, a problem modeling certain kinds of data mining and common sense reasoning (Juba, 2013a). In such a problem, the approximate validity (i.e., under Valiant’s PAC-Semantics (Valiant, 2000)) of an input query formula over a background probability distribution is ... more >>>

TR13-095 | 24th June 2013
Uriel Feige, Rani Izsak

#### Welfare Maximization and the Supermodular Degree

Given a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items,
the welfare maximization problem requires that every item be allocated to exactly one player,
and one wishes to maximize the sum of values obtained by the players,
as computed ... more >>>

TR13-096 | 25th June 2013
Dana Ron, Rocco Servedio

#### Exponentially improved algorithms and lower bounds for testing signed majorities

A signed majority function is a linear threshold function $f : \{+1,1\}^n \to \{+1,1\}$ of the form
$f(x)={\rm sign}(\sum_{i=1}^n \sigma_i x_i)$ where each $\sigma_i \in \{+1,-1\}.$ Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form ${\rm ... more >>> TR13-097 | 25th June 2013 Mikolas Janota, Joao Marques-Silva #### On Propositional QBF Expansions and Q-Resolution Over the years, proof systems for propositional satisfiability (SAT) have been extensively studied. Recently, proof systems for quantified Boolean formulas (QBFs) have also been gaining attention. Q-resolution is a calculus enabling producing proofs from DPLL-based QBF solvers. While DPLL has become a dominating technique for SAT, QBF has been tackled ... more >>> TR13-098 | 28th June 2013 Benny Applebaum, Yoni Moses #### Locally Computable UOWHF with Linear Shrinkage We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs)$H:\{0,1\}^n \rightarrow \{0,1\}^m$. A construction with constant \emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this ... more >>> TR13-099 | 6th July 2013 Hamidreza Jahanjou, Eric Miles, Emanuele Viola #### Local reductions Revisions: 3 We reduce non-deterministic time$T \ge 2^n$to a 3SAT instance$\phi$of size$|\phi| = T \cdot \log^{O(1)} T$such that there is an explicit circuit$C$that on input an index$i$of$\log |\phi|$bits outputs the$i$th clause, and each output bit of$C$depends on ... more >>> TR13-100 | 15th July 2013 Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan #### Lower bounds for depth$4$formulas computing iterated matrix multiplication We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth$4$arithmetic formula computing the product of$d$generic matrices of size$n \times n$, IMM$_{n,d}$, has size$n^{\Omega(\sqrt{d})}$as long as$d \leq n^{1/10}$. This improves the result of Nisan and Wigderson (Computational ... more >>> TR13-101 | 12th July 2013 Colin Jia Zheng, Salil Vadhan #### A Uniform Min-Max Theorem with Applications in Cryptography Revisions: 2 We present a new, more constructive proof of von Neumann's Min-Max Theorem for two-player zero-sum game --- specifically, an algorithm that builds a near-optimal mixed strategy for the second player from several best-responses of the second player to mixed strategies of the first player. The algorithm extends previous work of ... more >>> TR13-102 | 17th July 2013 Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah #### Small Depth Proof Systems A proof system for a language$L$is a function$f$such that Range$(f)$is exactly$L$. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by ... more >>> TR13-103 | 24th July 2013 Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha #### Generalized Wong sequences and their applications to Edmonds' problems We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix$M$whose entries are homogeneous linear polynomials over the integers. Given a linear subspace$\mathcal{B}$of the$n \times n$matrices over some field$\mathbb{F}$, we consider ... more >>> TR13-104 | 20th July 2013 Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin #### Explicit Maximally Recoverable Codes with Locality Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, while other (heavy) parity symbols may depend on all data symbols. Local parities allow to quickly recover any single symbol when it is erased, while heavy parities provide tolerance to a large number of simultaneous ... more >>> TR13-105 | 29th July 2013 Raghu Meka, Avi Wigderson #### Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique Revisions: 1 Finding cliques in random graphs and the closely related planted'' clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for t = ... more >>> TR13-106 | 29th July 2013 Shay Moran, Amir Yehudayoff #### A note on average-case sorting Revisions: 2 This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize the expected number of comparisons. We generalize Fredman's algorithm which is a variant of insertion sort and provide a basically tight upper bound: If \mu is more >>> TR13-107 | 7th August 2013 Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum #### Efficient Multiparty Protocols via Log-Depth Threshold Formulae We put forward a new approach for the design of efficient multiparty protocols: 1. Design a protocol for a small number of parties (say, 3 or 4) which achieves security against a single corrupted party. Such protocols are typically easy to construct as they may employ techniques that do not ... more >>> TR13-108 | 9th August 2013 Rahul Santhanam, Ryan Williams #### New Algorithms for QBF Satisfiability and Implications for Circuit Complexity Revisions: 1 We revisit the complexity of the satisfiability problem for quantified Boolean formulas. We show that satisfiability of quantified CNFs of size$\poly(n)$on$n$variables with$O(1)$quantifier blocks can be solved in time$2^{n-n^{\Omega(1)}}$by zero-error randomized algorithms. This is the first known improvement over brute force search in ... more >>> TR13-109 | 11th August 2013 Oded Goldreich, Dana Ron #### On Sample-Based Testers Revisions: 1 The standard definition of property testing endows the tester with the ability to make arbitrary queries to elements'' of the tested object. In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object. While sample-based testers were defined by Goldreich, Goldwasser, and Ron ({\em JACM}\/ ... more >>> TR13-110 | 12th August 2013 Xiaoming Sun, Marcos Villagra #### Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity There are three different types of nondeterminism in quantum communication: i)$\nqp$-communication, ii)$\qma$-communication, and iii)$\qcma$-communication. In this \redout{paper} we show that multiparty$\nqp$-communication can be exponentially stronger than$\qcma$-communication. This also implies an exponential separation with respect to classical multiparty nondeterministic communication complexity. We argue that there exists ... more >>> TR13-111 | 17th August 2013 Gregory Valiant, Paul Valiant #### Instance-by-instance optimal identity testing We consider the problem of verifying the identity of a distribution: Given the description of a distribution over a discrete support$p=(p_1,p_2,\ldots,p_n)$, how many samples (independent draws) must one obtain from an unknown distribution,$q$, to distinguish, with high probability, the case that$p=q$from the case that the total ... more >>> TR13-112 | 12th August 2013 Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf #### Exact Perfect Matching in Complete Graphs A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges. We show that for complete and bipartite complete graphs, the exact perfect ... more >>> TR13-113 | 19th August 2013 Moritz Müller, Stefan Szeider #### Revisiting Space in Proof Complexity: Treewidth and Pathwidth So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations ... more >>> TR13-114 | 24th August 2013 Parikshit Gopalan, Salil Vadhan, Yuan Zhou #### Locally Testable Codes and Cayley Graphs Revisions: 1 We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over$\F_2^h$: \begin{enumerate} \item A locally testable code is equivalent to a Cayley graph over$\F_2^h$whose set of generators is significantly larger than$h$and has no short linear dependencies, but yields a ... more >>> TR13-115 | 27th August 2013 Daniele Micciancio #### Locally Dense Codes The Minimum Distance Problem (MDP), i.e., the computational task of evaluating (exactly or approximately) the minimum distance of a linear code, is a well known NP-hard problem in coding theory. A key element in essentially all known proofs that MDP is NP-hard is the construction of a combinatorial object that ... more >>> TR13-116 | 29th August 2013 Albert Atserias, Moritz Müller, Sergi Oliva #### Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle The relativized weak pigeonhole principle states that if at least$2n$out of$n^2$pigeons fly into$n$holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size$2^{(\log n)^{3/2-\epsilon}}$for every$\epsilon > 0$and every sufficiently ... more >>> TR13-117 | 1st September 2013 Igor Oliveira #### Algorithms versus Circuit Lower Bounds Different techniques have been used to prove several transference theorems of the form "nontrivial algorithms for a circuit class C yield circuit lower bounds against C". In this survey we revisit many of these results. We discuss how circuit lower bounds can be obtained from derandomization, compression, learning, and satisfiability ... more >>> TR13-118 | 2nd September 2013 Mahdi Cheraghchi, Venkatesan Guruswami #### Capacity of Non-Malleable Codes Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages$s$in a manner so that tampering the codeword causes the decoder to either output$s$or a message that is independent of$s$. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly ... more >>> TR13-119 | 2nd September 2013 Emanuele Viola #### Challenges in computational lower bounds We draw two incomplete, biased maps of challenges in computational complexity lower bounds. Our aim is to put these challenges in perspective, and to present some connections which do not seem widely known. more >>> TR13-120 | 4th September 2013 Zeyu Guo #### Randomness-efficient Curve Samplers Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the ... more >>> TR13-121 | 4th September 2013 Mahdi Cheraghchi, Venkatesan Guruswami #### Non-Malleable Coding Against Bit-wise and Split-State Tampering Revisions: 1 Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable ... more >>> TR13-122 | 5th September 2013 Irit Dinur, Venkatesan Guruswami #### PCPs via low-degree long code and hardness for constrained hypergraph coloring Revisions: 1 We develop new techniques to incorporate the recently proposed short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical Label Cover + Fourier Analysis'' framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs ... more >>> TR13-123 | 6th September 2013 Joshua Grochow, Youming Qiao #### Algorithms for group isomorphism via group extensions and cohomology The isomorphism problem for groups given by multiplication tables (GpI) is well-known to be solvable in n^O(log n) time, but only recently has there been significant progress towards polynomial time. For example, in 2012 Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. ... more >>> TR13-124 | 9th September 2013 Thomas Watson #### The Complexity of Deciding Statistical Properties of Samplable Distributions Revisions: 2 We consider the problems of deciding whether the joint distribution sampled by a given circuit satisfies certain statistical properties such as being i.i.d., being exchangeable, being pairwise independent, having two coordinates with identical marginals, having two uncorrelated coordinates, and many other variants. We give a proof that simultaneously shows all ... more >>> TR13-125 | 11th September 2013 Venkatesan Guruswami, Euiwoong Lee #### Complexity of approximating CSP with Balance / Hard Constraints We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>> TR13-126 | 11th September 2013 Arman Fazeli, Shachar Lovett, Alex Vardy #### Nontrivial t-designs over finite fields exist for all t A$t$-$(n,k,\lambda)$design over$\mathbb{F}_q$is a collection of$k$-dimensional subspaces of$\mathbb{F}_q^n$, ($k$-subspaces, for short), called blocks, such that each$t$-dimensional subspace of$\mathbb{F}_q^n$is contained in exactly$\lambda$blocks. Such$t$-designs over$\mathbb{F}_q$are the$q$-analogs of conventional combinatorial designs. Nontrivial$t$-$(n,k,\lambda)$designs over$\mathbb{F}_q$are currently known ... more >>> TR13-127 | 15th September 2013 Paul Beame, Raphael Clifford, Widad Machmouchi #### Element Distinctness, Frequency Moments, and Sliding Windows We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics, that are simple to calculate for sorted data. In particular, we develop a randomized algorithm for the element distinctness problem whose time$T$and space$S$... more >>> TR13-128 | 16th September 2013 Pavel Hrubes #### A note on semantic cutting planes We show that the semantic cutting planes proof system has feasible interpolation via monotone real circuits. This gives an exponential lower bound on proof length in the system. We also pose the following problem: can every multivariate non-decreasing function be expressed as a composition of non-decreasing functions in two ... more >>> TR13-129 | 17th September 2013 Adam Klivans, Pravesh Kothari, Igor Oliveira #### Constructing Hard Functions from Learning Algorithms Revisions: 1 Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class$\mathcal{C} \subseteq P/poly$of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then$EXP^{NP} \not \subseteq \mathcal{C}$(the class$EXP^{NP}$was subsequently improved to$P$by Hitchcock and ... more >>> TR13-130 | 17th September 2013 Mark Braverman, Ankit Garg #### Public vs private coin in bounded-round information Revisions: 1 We precisely characterize the role of private randomness in the ability of Alice to send a message to Bob while minimizing the amount of information revealed to him. We show that if using private randomness a message can be transmitted while revealing$I$bits of information, the transmission can be ... more >>> TR13-131 | 17th September 2013 Nikhil Balaji, Samir Datta #### Collapsing Exact Arithmetic Hierarchies Revisions: 1 We provide a uniform framework for proving the collapse of the hierarchy,$NC^1(\mathcal{C})$for an exact arithmetic class$\mathcal{C}$of polynomial degree. These hierarchies collapses all the way down to the third level of the${AC}^0$-hierarchy,${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes $\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.$ more >>> TR13-132 | 23rd September 2013 Michael Forbes, Ramprasad Saptharishi, Amir Shpilka #### Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the ... more >>> TR13-133 | 23rd September 2013 Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland #### A Structured View on Weighted Counting with Relations to Quantum Computation and Applications Revisions: 1 Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path and the goal is to compute the sum of the weights of all paths (instead of computing the number of accepting paths). We present a structured view on weighted counting by ... more >>> TR13-134 | 25th September 2013 Or Meir #### Combinatorial PCPs with Short Proofs The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the ... more >>> TR13-135 | 27th September 2013 Scott Aaronson #### BosonSampling Is Far From Uniform Revisions: 2 BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random ... more >>> TR13-136 | 27th September 2013 Paul Goldberg, Aaron Roth #### Bounds for the Query Complexity of Approximate Equilibria We analyze the number of payoff queries needed to compute approximate correlated equilibria. For multi-player, binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player's behavior must always be approximately optimal, in the ... more >>> TR13-137 | 29th September 2013 Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran #### On the Power of Public-key Encryption in Secure Computation We qualitatively separate semi-honest secure computation of non-trivial secure-function evaluation (SFE) functionalities from existence of key-agreement protocols. Technically, we show the existence of an oracle (namely, PKE-oracle) relative to which key-agreement protocols exist; but it is useless for semi-honest secure realization of symmetric 2-party (deterministic finite) SFE functionalities, i.e. any ... more >>> TR13-138 | 5th October 2013 Itai Benjamini, Gil Cohen, Igor Shinkar #### Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball Revisions: 1 We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even$n \in {\mathbb N}$there exists an explicit bijection$\psi \colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$such that for every ... more >>> TR13-139 | 7th October 2013 Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu #### Detecting Monomials with$k$Distinct Variables We study the complexity of detecting monomials with special properties in the sum-product expansion of a polynomial represented by an arithmetic circuit of size polynomial in the number of input variables and using only multiplication and addition. We focus on monomial properties expressed in terms of the number of distinct ... more >>> TR13-140 | 8th October 2013 Atri Rudra, Mary Wootters #### Every list-decodable code for high noise has abundant near-optimal rate puncturings We show that any$q$-ary code with sufficiently good distance can be randomly punctured to obtain, with high probability, a code that is list decodable up to radius$1 - 1/q - \epsilon$with near-optimal rate and list sizes. Our results imply that most" Reed-Solomon codes are list decodable ... more >>> TR13-141 | 8th October 2013 Leonid Gurvits #### Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications Revisions: 1 We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorthmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated with boolean matrices with prescribed row and (uniformly bounded) column sums within simply ... more >>> TR13-142 | 11th October 2013 Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni #### Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees Revisions: 2 In this paper, we study linear and quadratic Boolean functions in the context of property testing. We do this by observing that the query complexity of testing properties of linear and quadratic functions can be characterized in terms of the complexity in another model of computation called parity decision trees. ... more >>> TR13-143 | 19th October 2013 Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman #### Robust Pseudorandom Generators Let$G:\{0,1\}^n\to\{0,1\}^m$be a pseudorandom generator. We say that a circuit implementation of$G$is$(k,q)$-robust if for every set$S$of at most$k$wires anywhere in the circuit, there is a set$T$of at most$q|S|$outputs, such that conditioned on the values of$S$and$T$... more >>> TR13-144 | 8th October 2013 VyasRam Selvam #### The two queries assumption and Arthur-Merlin classes We explore the implications of the two queries assumption,$P^{NP[1]}=P_{||}^{NP[2]}$, with respect to the polynomial hierarchy and the classes$AM$and$MA$. We prove the following results: 1.$P^{NP[1]}=P_{||}^{NP[2]}\impliesAM = MA$2.$P^{NP[1]}=P_{||}^{NP[2]}\impliesPH \subset MA_{/1}$3.$\exists\;B\;P^{NP[1]^B}=P^{NP[2]^B}$and$NP^B \not\subseteq coMA^B$. 4.$P^{NP[1]}=P_{||}^{NP[2]}\impliesPH ... more >>>

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

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

Revisions: 1

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

TR13-146 | 20th October 2013
Subhash Khot, Madhur Tulsiani, Pratik Worah

#### A Characterization of Approximation Resistance

Revisions: 1

A predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|f^{-1}(1)|}{2^k}$ is called {\it approximation resistant} if given a near-satisfiable instance of CSP$(f)$, it is computationally hard to find an assignment that satisfies at least $\rho(f)+\Omega(1)$ fraction of the constraints.

We present a complete characterization of approximation resistant predicates under the ... more >>>

TR13-147 | 25th October 2013
Adam Bouland, Scott Aaronson

#### Any Beamsplitter Generates Universal Quantum Linear Optics

Revisions: 3

In 1994, Reck et al. showed how to realize any linear-optical unitary transformation using a product of beamsplitters and phaseshifters. Here we show that any single beamsplitter that nontrivially mixes two modes, also densely generates the set of m by m unitary transformations (or orthogonal transformations, in the real case) ... more >>>

TR13-148 | 26th October 2013
Irit Dinur, Igor Shinkar

#### On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors

For $3 \leq q < Q$ we consider the $\text{ApproxColoring}(q,Q)$ problem of deciding for a given graph $G$ whether $\chi(G) \leq q$ or $\chi(G) \geq Q$. It was show in [DMR06] that the problem $\text{ApproxColoring}(q,Q)$ is NP-hard for $q=3,4$ and arbitrary large constant $Q$ under variants of the Unique Games ... more >>>

TR13-149 | 28th October 2013
Albert Atserias, Neil Thapen

#### The Ordering Principle in a Fragment of Approximate Counting

The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk ... more >>>

TR13-150 | 4th November 2013
Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

#### An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas

We give a deterministic #SAT algorithm for de Morgan formulas of size up to $n^{2.63}$, which runs in time $2^{n-n^{\Omega(1)}}$. This improves upon the deterministic #SAT algorithm of \cite{CKKSZ13}, which has similar running time but works only for formulas of size less than $n^{2.5}$.

Our new algorithm is based on ... more >>>

TR13-151 | 7th November 2013
Mark Bun, Justin Thaler

#### Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

Revisions: 3

We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit ... more >>>

TR13-152 | 7th November 2013
Oded Goldreich, Avi Wigderson

#### On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

{\em Does derandomization of probabilistic algorithms become easier when the number of bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ... more >>>

TR13-153 | 8th November 2013
Mrinal Kumar, Shubhangi Saraf

#### The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of {\it depth reduction} developed in the works of Agrawal-Vinay [AV08], Koiran [Koi12] and Tavenas [Tav13], and the use of the shifted partial derivative complexity measure ... more >>>

TR13-154 | 29th October 2013
Martin Schwarz, Maarten Van den Nest

#### Simulating Quantum Circuits with Sparse Output Distributions

We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained ... more >>>

TR13-155 | 10th November 2013
Gil Cohen, Amnon Ta-Shma

#### Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Revisions: 2

Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, ... more >>>

TR13-156 | 15th November 2013
Jan Krajicek

#### A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems

Revisions: 2

We give a general reduction of lengths-of-proofs lower bounds for
constant depth Frege systems in DeMorgan language augmented by
a connective counting modulo a prime $p$
(the so called $AC^0[p]$ Frege systems)
to computational complexity
lower bounds for search tasks involving search trees branching upon
values of linear maps on ... more >>>

TR13-157 | 11th November 2013
Bin Fu

#### Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP

Revisions: 1 , Comments: 1

We show that
derandomizing polynomial identity testing over an arbitrary finite
field implies that NEXP does not have polynomial size boolean
circuits. In other words, for any finite field F(q) of size q,
$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where
$PIT_q$ is the polynomial identity testing problem over F(q), and
NSUBEXP is ... more >>>

TR13-158 | 18th November 2013
Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta

#### Information-theoretic approximations of the nonnegative rank

Revisions: 3

Common information was introduced by Wyner as a measure of dependence of two
random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such
as communication ... more >>>

TR13-159 | 20th November 2013
Per Austrin, Venkatesan Guruswami, Johan Håstad

#### $(2+\epsilon)$-SAT is NP-hard

Revisions: 2

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find ... more >>>

TR13-160 | 20th November 2013
Zeev Dvir, Shubhangi Saraf, Avi Wigderson

#### Breaking the quadratic barrier for 3-LCCs over the Reals

We prove that 3-query linear locally correctable codes over the Reals of dimension $d$ require block length $n>d^{2+\lambda}$ for some fixed, positive $\lambda >0$. Geometrically, this means that if $n$ vectors in $R^d$ are such that each vector is spanned by a linear number of disjoint triples of others, then ... more >>>

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

#### The Frequent Paucity of Trivial Strings

Revisions: 1

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

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

#### The Firefighter Problem: A Structural Analysis

Revisions: 1

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

TR13-163 | 28th November 2013
Russell Impagliazzo, Valentine Kabanets

#### Fourier Concentration from Shrinkage

Revisions: 2

For Boolean functions computed by de Morgan formulas of subquadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on small-degree'' coefficients. For a Boolean function $f:\{0,1\}^n\to\{1,-1\}$ computable by a de Morgan formula of size $s$, we show that
$\sum_{A\subseteq [n]\; :\; |A|>s^{1/\Gamma ... more >>> TR13-164 | 28th November 2013 Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian #### Weak Parity We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that ... more >>> TR13-165 | 28th November 2013 Michael Walfish, Andrew Blumberg #### Verifying computations without reexecuting them: from theoretical possibility to near-practicality Revisions: 3 How can we trust results computed by a third party, or the integrity of data stored by such a party? This is a classic question in systems security, and it is particularly relevant in the context of cloud computing. Various solutions have been proposed that make assumptions about the class ... more >>> TR13-166 | 28th November 2013 Arnab Bhattacharyya #### On testing affine-invariant properties An affine-invariant property over a finite field is a property of functions over F_p^n that is closed under all affine transformations of the domain. This class of properties includes such well-known beasts as low-degree polynomials, polynomials that nontrivially factor, and functions of low spectral norm. The last few years has ... more >>> TR13-167 | 28th November 2013 Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma #### Super-polylogarithmic hypergraph coloring hardness via low-degree long codes We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the “short code” of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results. In particular, we prove quasi-NP-hardness of the following problems on ... more >>> TR13-168 | 29th November 2013 Raghav Kulkarni, Avishay Tal #### On Fractional Block Sensitivity Revisions: 1 , Comments: 1 In this paper we study the fractional block sensitivityof Boolean functions. Recently, Tal (ITCS, 2013) and Gilmer, Saks, and Srinivasan (CCC, 2013) independently introduced this complexity measure, denoted by fbs(f), and showed that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by RC(f), which ... more >>> TR13-169 | 2nd December 2013 Benjamin Rossman #### Formulas vs. Circuits for Small Distance Connectivity We give the first super-polynomial separation in the power of bounded-depth boolean formulas vs. circuits. Specifically, we consider the problem Distance k(n) Connectivity, which asks whether two specified nodes in a graph of size n are connected by a path of length at most k(n). This problem is solvable (by ... more >>> TR13-170 | 2nd December 2013 Venkatesan Guruswami, Carol Wang #### Explicit rank-metric codes list-decodable with optimal redundancy We construct an explicit family of linear rank-metric codes over any field {\mathbb F}_h that enables efficient list decoding up to a fraction \rho of errors in the rank metric with a rate of 1-\rho-\epsilon, for any desired \rho \in (0,1) and \epsilon > 0. Previously, a Monte Carlo construction ... more >>> TR13-171 | 1st December 2013 Anindya De, Ilias Diakonikolas, Rocco Servedio #### Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions Let g: \{-1,1\}^k \to \{-1,1\} be any Boolean function and q_1,\dots,q_k be any degree-2 polynomials over \{-1,1\}^n. We give a \emph{deterministic} algorithm which, given as input explicit descriptions of g,q_1,\dots,q_k and an accuracy parameter \eps>0, approximates \[ \Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1]$
to within an additive $\pm \eps$. For any constant ... more >>>

TR13-172 | 1st December 2013
Anindya De, Ilias Diakonikolas, Rocco Servedio

#### Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates
$\Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0]$
to within an additive $\pm \eps$ in ... more >>>

TR13-173 | 28th November 2013
Anindya De, Rocco Servedio

#### Efficient deterministic approximate counting for low degree polynomial threshold functions

We give a deterministic algorithm for
approximately counting satisfying assignments of a degree-$d$ polynomial threshold function
(PTF).
Given a degree-$d$ input polynomial $p(x_1,\dots,x_n)$ over $\mathbb{R}^n$
and a parameter $\epsilon > 0$, our algorithm approximates
$\mathbf{P}_{x \sim \{-1,1\}^n}[p(x) \geq 0]$
to within an additive $\pm \epsilon$ in time $O_{d,\epsilon}(1)\cdot ... more >>> TR13-174 | 6th December 2013 Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena #### Hitting-sets for low-distance multilinear depth-$3$The depth-$3$model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known exponential lower bounds but no nontrivial blackbox identity tests. In this paper we take a step towards designing such hitting-sets. We define a notion of ... more >>> TR13-175 | 6th December 2013 Venkatesan Guruswami, Chaoping Xing #### Hitting Sets for Low-Degree Polynomials with Optimal Density Revisions: 1 We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding$n$-variate degree-$d$polynomials over${\mathbb F}_q$with$q \ge \Omega(d/\delta)$, we present an explicit (multi)-set$S \subseteq {\mathbb F}_q^n$of size$N=\mathrm{poly}(n^d/\delta)$such that every nonzero polynomial vanishes on at most ... more >>> TR13-176 | 8th December 2013 Daniel Kane, Osamu Watanabe #### A Short Implicant of CNFs with Relatively Many Satisfying Assignments Revisions: 1 , Comments: 1 Consider any Boolean function$F(X_1,\ldots,X_N)$that has more than$2^{-N^{d}}$satisfying assignments and that can be expressed by a CNF formula with at most$N^{1+e}$clauses for some$d>0$and$e>0$such that$d+e$is less than$1$(*). Then how many variables do we need to fix in order ... more >>> TR13-177 | 10th December 2013 Eric Allender, Nikhil Balaji, Samir Datta #### Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs Revisions: 1 We present improved uniform TC$^0$circuits for division, matrix powering, and related problems, where the improvement is in terms of majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>> TR13-178 | 14th December 2013 Nikolay Vereshchagin #### Randomized communication complexity of appropximating Kolmogorov complexity Revisions: 2 The paper [Harry Buhrman, Michal Koucky, Nikolay Vereshchagin. Randomized Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331] considered communication complexity of the following problem. Alice has a binary string$x$and Bob a binary string$y$, both of length$n$, and they want to compute or approximate more >>> TR13-179 | 15th December 2013 Irit Dinur, David Steurer #### Direct Product Testing A direct product is a function of the form$g(x_1,\ldots,x_k)=(g_1(x_1),\ldots,g_k(x_k))$. We show that the direct product property is locally testable with$2$queries, that is, a canonical two-query test distinguishes between direct products and functions that are from direct products with constant probability. This local testing question comes up ... more >>> TR13-180 | 17th December 2013 Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian #### On Interactivity in Arthur-Merlin Communication and Stream Computation Revisions: 1 We introduce {\em online interactive proofs} (OIP), which are a hierarchy of communication complexity models that involve both randomness and nondeterminism (thus, they belong to the Arthur--Merlin family), but are {\em online} in the sense that the basic communication flows from Alice to Bob alone. The complexity classes defined by ... more >>> TR13-181 | 20th December 2013 Mrinal Kumar, Shubhangi Saraf #### Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits In this paper, we prove superpolynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. We give an explicit polynomial in VNP of degree$n$in$n^2$variables such that any homogeneous depth 4 arithmetic circuit computing it must have size$n^{\Omega(\log \log n)}$. Our results extend ... more >>> TR13-182 | 20th December 2013 Boaz Barak #### Structure vs Combinatorics in Computational Complexity Some computational problems seem to have a certain "structure" that is manifested in non-trivial algorithmic properties, while others are more "unstructured" in the sense that they are either "very easy" or "very hard". I survey some of the known results and open questions about this classification and its connections to ... more >>> TR13-183 | 22nd December 2013 Yael Tauman Kalai, Ran Raz, Ron Rothblum #### How to Delegate Computations: The Power of No-Signaling Proofs Revisions: 1 We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n*polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. ... more >>> TR13-184 | 23rd December 2013 Boaz Barak, Jonathan Kelner, David Steurer #### Rounding Sum-of-Squares Relaxations We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly ... more >>> TR13-185 | 24th December 2013 Fu Li, Iddo Tzameret #### Generating Matrix Identities and Proof Complexity Lower Bounds Revisions: 3 Motivated by the fundamental lower bounds questions in proof complexity, we investigate the complexity of generating identities of matrix rings, and related problems. Specifically, for a field$\mathbb{F}$let$A$be a non-commutative (associative)$\mathbb{F}$-algebra (e.g., the algebra Mat$_d(\mathbb{F})\;$of$d\times d$matrices over$\mathbb{F}$). We say that a non-commutative ... more >>> TR13-186 | 27th December 2013 Nitin Saxena #### Progress on Polynomial Identity Testing - II We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years. more >>> TR13-187 | 27th December 2013 Peyman Afshani, Kevin Matulef, Bryan Wilkinson #### Property Testing on Linked Lists Revisions: 1 We define a new property testing model for algorithms that do not have arbitrary query access to the input, but must instead traverse it in a manner that respects the underlying data structure in which it is stored. In particular, we consider the case when the underlying data structure is ... more >>> TR13-188 | 13th December 2013 Christian Glaßer, Maximilian Witek #### Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain: - For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible. - For P, the delta-levels of ... more >>> TR13-189 | 21st December 2013 Periklis Papakonstantinou, Dominik Scheder, Hao Song #### Overlays and Limited Memory Communication Mode(l)s We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models. We introduce the notion of rectangle overlay complexity of a function$f: \{0,1\}^n\times \{0,1\}^n\to\{0,1\}$. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in ... more >>> TR13-190 | 28th December 2013 Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson #### Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture Revisions: 10 One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e.,$\mathbf{P}\not\subseteq\mathbf{NC}_1~\$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the ... more >>>

TR13-191 | 26th December 2013
Petr Savicky

#### Boolean functions with a vertex-transitive group of automorphisms

Revisions: 2 , Comments: 1

A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. Several constructions of vertex-transitive functions and some of their properties are presented.

more >>>

ISSN 1433-8092 | Imprint