Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2018:
All reports in year 2018:
TR18-141 | 6th August 2018
Sandip Sinha, Omri Weinstein

#### Local Decodability of the Burrows-Wheeler Transform

The Burrows-Wheeler Transform (BWT) is among the most influential discoveries in text compression and DNA storage. It is a \emph{reversible} preprocessing step that rearranges an $n$-letter string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings, and is the basis for the ubiquitous \texttt{bzip} program. ... more >>>

TR18-140 | 11th August 2018
Ilan Komargodski, Ran Raz, Yael Tauman Kalai

#### A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols

In 1985, Ben-Or and Linial (Advances in Computing Research '89) introduced the collective coin-flipping problem, where $n$ parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party ... more >>>

TR18-139 | 10th August 2018
Igor Carboni Oliveira, Rahul Santhanam

#### Hardness Magnification for Natural Problems

We show that for several natural problems of interest, complexity lower bounds that are barely non-trivial imply super-polynomial or even exponential lower bounds in strong computational models. We term this phenomenon "hardness magnification". Our examples of hardness magnification include:

1. Let MCSP$[s]$ be the decision problem whose YES instances are ... more >>>

TR18-138 | 10th August 2018
Shuichi Hirahara

#### Non-black-box Worst-case to Average-case Reductions within NP

There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP: Several results suggest that black-box worst-case to average-case reductions are not likely to be used for reducing any worst-case problem outside coNP to a distributional NP problem.

This paper overcomes the barrier. We ... more >>>

TR18-137 | 7th August 2018
Scott Aaronson

#### Quantum Lower Bound for Approximate Counting Via Laurent Polynomials

We consider the following problem: estimate the size of a nonempty set $S\subseteq\left[ N\right]$, given both quantum queries to a membership oracle for $S$, and a device that generates equal superpositions $\left\vert S\right\rangle$ over $S$ elements. We show that, if $\left\vert S\right\vert$ is neither too large nor ... more >>>

TR18-136 | 1st August 2018
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

#### List Decoding with Double Samplers

We develop the notion of double samplers, first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders.

We show how double samplers give a generic way of amplifying distance in a way that enables ... more >>>

TR18-135 | 31st July 2018

#### Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2016). We consider three different variants of graph homomorphisms, namely injective ... more >>>

TR18-134 | 24th July 2018
Tali Kaufman, David Mass

#### Cosystolic Expanders over any Abelian Group

In this work we show a general reduction from high dimensional complexes to their links based on the spectral properties of the links. We use this reduction to show that if a certain property is testable in the links, then it is also testable in the complex. In particular, we ... more >>>

TR18-133 | 26th July 2018
Emanuele Viola

#### Constant-error pseudorandomness proofs from hardness require majority

Research in the 80's and 90's showed how to construct a pseudorandom
generator from a function that is hard to compute on more than $99\%$
of the inputs. A more recent line of works showed however that if
the generator has small error, then the proof of correctness cannot
be ... more >>>

TR18-132 | 17th July 2018
Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

#### Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ ... more >>>

TR18-131 | 17th July 2018
Gautam Kamath, Christos Tzamos

#### Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing

In the conditional sampling model, the algorithm is given the following access to a distribution: it submits a query set $S$ to an oracle, which returns a sample from the distribution conditioned on being from $S$.
In the non-adaptive setting, ... more >>>

TR18-130 | 16th July 2018
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

#### Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ is a polynomial with $s$ monomials, with individual degrees of its variables bounded by $d$, then $f$ can be deterministically factored in time $s^{\poly(d) \log n}$. Prior to our ... more >>>

TR18-129 | 13th July 2018
Jelani Nelson, Huacheng Yu

#### Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Revisions: 1

We show optimal lower bounds for spanning forest computation in two different models:

* One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the ... more >>>

TR18-128 | 11th July 2018
Ewin Tang

#### A quantum-inspired classical algorithm for recommendation systems

A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an $m\times n$ matrix of small rank $k$. We give the first classical algorithm to produce a recommendation in $O(\text{poly}(k)\text{polylog}(m,n))$ time, which is an exponential improvement on previous ... more >>>

TR18-127 | 9th July 2018
Stasys Jukna, Hannes Seiwert

#### Approximation Limitations of Tropical Circuits

We develop general lower bound arguments for approximating tropical
(min,+) and (max,+) circuits, and use them to prove the
first non-trivial, even super-polynomial, lower bounds on the size
of such circuits approximating some explicit optimization
problems. In particular, these bounds show that the approximation
powers of pure dynamic programming algorithms ... more >>>

TR18-126 | 24th June 2018
Pravesh Kothari, Ruta Mehta

#### Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium

Several works have shown unconditional hardness (via integrality gaps) of computing equilibria using strong hierarchies of convex relaxations. Such results however only apply to the problem of computing equilibria that optimize a certain objective function and not to the (arguably more fundamental) task of finding \emph{any} equilibrium.

We present ... more >>>

TR18-125 | 7th July 2018
Zvika Brakerski

#### Fundamentals of Fully Homomorphic Encryption – A Survey

A homomorphic encryption scheme is one that allows computing on encrypted data without decrypting it first. In fully homomorphic encryption it is possible to apply any efficiently computable function to encrypted data. We provide a survey on the origins, definitions, properties, constructions and uses of fully homomorphic encryption.

more >>>

TR18-124 | 6th July 2018
Amir Yehudayoff

#### Separating Monotone VP and VNP

This work is about the monotone versions of the algebraic complexity classes VP and VNP. The main result is that monotone VNP is strictly stronger than monotone VP.

more >>>

TR18-123 | 3rd July 2018
Alessandro Chiesa, Peter Manohar, Igor Shinkar

#### Probabilistic Checking against Non-Signaling Strategies from Linearity Testing

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is ... more >>>

TR18-122 | 3rd July 2018
Igor Carboni Oliveira, Rahul Santhanam

#### Pseudo-derandomizing learning and approximation

We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser
[GG11]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed
output with high probability. We explore pseudo-determinism in the settings of learning and ap-
proximation. Our goal is to simulate known randomized algorithms in these settings ... more >>>

TR18-121 | 20th June 2018
Justin Holmgren, Lisa Yang

#### Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem

Non-signaling games are an important object of study in the theory of computation, for their role both in quantum information and in (classical) cryptography. In this work, we study the behavior of these games under parallel repetition.

We show that, unlike the situation both for classical games and for two-player ... more >>>

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

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

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

TR18-119 | 21st June 2018
YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang

#### A Tight Lower Bound for Entropy Flattening

Revisions: 1

We study \emph{entropy flattening}: Given a circuit $\mathcal{C}_X$ implicitly describing an $n$-bit source $X$ (namely, $X$ is the output of $\mathcal{C}_X$ on a uniform random input), construct another circuit $\mathcal{C}_Y$ describing a source $Y$ such that (1) source $Y$ is nearly \emph{flat} (uniform on its support), and (2) the Shannon ... more >>>

TR18-118 | 20th June 2018
Alexander Durgin, Brendan Juba

#### Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs

We consider several closely related variants of PAC-learning in which false-positive and false-negative errors are treated differently. In these models we seek to guarantee a given, low rate of false-positive errors and as few false-negative errors as possible given that we meet the false-positive constraint. Bshouty and Burroughs first observed ... more >>>

TR18-117 | 23rd June 2018
Fedor Part, Iddo Tzameret

#### Resolution with Counting: Lower Bounds over Different Moduli

Resolution over linear equations (introduced in [RT08]) emerged recently as an important object of study. This refutation system, denoted Res(lin$_R$), operates with disjunction of linear equations over a ring $R$. On the one hand, the system captures a natural minimal'' extension of resolution in which efficient counting can be achieved; ... more >>>

TR18-116 | 18th June 2018
Xue Chen, David Zuckerman

We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if $Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$ is a strong $(k,\epsilon)$-extractor, then for at least 99% of choices of $\tilde{O}(n ... more >>> TR18-115 | 11th June 2018 Valentine Kabanets, Zhenjian Lu #### Satisfiability and Derandomization for Small Polynomial Threshold Circuits A polynomial threshold function (PTF) is defined as the sign of a polynomial$p\colon\bool^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth. Satisfiability (#SAT). We give the first zero-error randomized algorithm ... more >>> TR18-114 | 6th June 2018 Paul Beame, Shayan Oveis Gharan, Xin Yang #### Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials We develop an extension of recent analytic methods for obtaining time-space tradeoff lower bounds for problems of learning from uniformly random labelled examples. With our methods we can obtain bounds for learning concept classes of finite functions from random evaluations even when the sample space of random inputs can be ... more >>> TR18-113 | 30th May 2018 Dominik Scheder #### PPSZ for$k \geq 5$: More Is Better We show that for$k \geq 5$, the PPSZ algorithm for$k$-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every$k\geq 5$, there is a strictly increasing function$f: [0,1] \rightarrow \mathbb{R}$with$f(0) = 0$that has the ... more >>> TR18-112 | 5th June 2018 Raghu Meka, Omer Reingold, Avishay Tal #### Pseudorandom Generators for Width-3 Branching Programs Revisions: 1 We construct pseudorandom generators of seed length$\tilde{O}(\log(n)\cdot \log(1/\epsilon))$that$\epsilon$-fool ordered read-once branching programs (ROBPs) of width$3$and length$n$. For unordered ROBPs, we construct pseudorandom generators with seed length$\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width$3$ROBPs since the work ... more >>> TR18-111 | 4th June 2018 Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay #### Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits Comments: 1 Let$C$be a depth-3$\Sigma\Pi\Sigma$arithmetic circuit of size$s$, computing a polynomial$f \in \mathbb{F}[x_1,\ldots, x_n]$(where$\mathbb{F}$=$\mathbb{Q}$or$\mathbb{C}$) with fan-in of product gates bounded by$d$. We give a deterministic time$2^d \text{poly}(n,s)$polynomial identity testing algorithm to check whether$f \equiv 0$or ... more >>> TR18-110 | 4th June 2018 Fu Li, David Zuckerman #### Improved Extractors for Recognizable and Algebraic Sources We study the task of seedless randomness extraction from recognizable sources, which are uniform distributions over sets of the form {x : f(x) = v} for functions f in some specified class C. We give two simple methods for constructing seedless extractors for C-recognizable sources. Our first method shows that ... more >>> TR18-109 | 29th May 2018 Kasper Green Larsen, Jesper Buus Nielsen #### Yes, There is an Oblivious RAM Lower Bound! An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky [JACM'96] is a (possibly randomized) RAM, for which the memory access pattern reveals no information about the operations performed. The main performance metric of an ORAM is the bandwidth overhead, i.e., the multiplicative factor extra memory blocks that must be accessed ... more >>> TR18-108 | 1st June 2018 Andrzej Lingas #### Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth We consider normalized Boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized Boolean circuits computing Boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., ... more >>> TR18-107 | 31st May 2018 Ran Raz, Avishay Tal #### Oracle Separation of BQP and PH We present a distribution$D$over inputs in$\{-1,1\}^{2N}$, such that: (1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time$O(\log N)$, that distinguishes between$D$and the uniform distribution with advantage$\Omega(1/\log N)$. (2) No Boolean circuit of$\mathrm{quasipoly}(N)$... more >>> TR18-106 | 30th May 2018 Chetan Gupta, Vimalraj Sharma, Raghunath Tewari #### Reachability in$O(\log n)$Genus Graphs is in Unambiguous Revisions: 1 Given the polygonal schema embedding of an$O(log n)$genus graph$G$and two vertices$s$and$t$in$G$, we show that deciding if there is a path from$s$to$t$in$G$is in unambiguous logarithmic space. more >>> TR18-105 | 30th May 2018 Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen #### Quantum proof systems for iterated exponential time, and beyond We show that any language in nondeterministic time$\exp(\exp(\cdots\exp(n)))$, where the number of iterated exponentials is an arbitrary function$R(n)$, can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness$1$and soundness$1 - \exp(-C\exp(\cdots\exp(n)))$, ... more >>> TR18-104 | 29th May 2018 Oded Goldreich #### Flexible models for testing graph properties Revisions: 1 The standard models of testing graph properties postulate that the vertex-set consists of$\{1,2,...,n\}$, where$n$is a natural number that is given explicitly to the tester. Here we suggest more flexible models by postulating that the tester is given access to samples the arbitrary vertex-set; that is, the vertex-set ... more >>> TR18-103 | 30th April 2018 Zhao Song, David Woodruff, Peilin Zhong #### Relative Error Tensor Low Rank Approximation We consider relative error low rank approximation of tensors with respect to the Frobenius norm. Namely, given an order-$q$tensor$A \in \mathbb{R}^{\prod_{i=1}^q n_i}$, output a rank-$k$tensor$B$for which$\|A-B\|_F^2 \leq (1+\epsilon) {\rm OPT}$, where${\rm OPT} = \inf_{\textrm{rank-}k~A'} \|A-A'\|_F^2$. Despite much success on obtaining relative error low ... more >>> TR18-102 | 15th May 2018 Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan #### Short Proofs in QBF Expansion For quantified Boolean formulas (QBF) there are two main different approaches to solving: QCDCL and expansion solving. In this paper we compare the underlying proof systems and show that expansion systems admit strictly shorter proofs than CDCL systems for formulas of bounded quantifier complexity, thus pointing towards potential advantages of ... more >>> TR18-101 | 20th May 2018 Akash Kumar, C. Seshadhri, Andrew Stolman #### Finding forbidden minors in sublinear time: a$O(n^{1/2+o(1)})$-query one-sided tester for minor closed properties on bounded degree graphs Let$G$be an undirected, bounded degree graph with$n$vertices. Fix a finite graph$H$, and suppose one must remove$\varepsilon n$edges from$G$to make it$H$-minor free (for some small constant$\varepsilon > 0$). We give an$n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ... more >>> TR18-100 | 18th May 2018 Eshan Chattopadhyay, Anindya De, Rocco Servedio #### Simple and efficient pseudorandom generators from Gaussian processes We show that a very simple pseudorandom generator fools intersections of$k$linear threshold functions (LTFs) and arbitrary functions of$k$LTFs over$n$-dimensional Gaussian space. The two analyses of our PRG (for intersections versus arbitrary functions of LTFs) are quite different from each other and from previous analyses of ... more >>> TR18-099 | 19th May 2018 Scott Aaronson #### PDQP/qpoly = ALL We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable ... more >>> TR18-098 | 17th May 2018 Oded Goldreich #### Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity Focusing on property testing tasks that have query complexity that is independent of the size of the tested object (i.e., depends on the proximity parameter only), we prove the existence of a rich hierarchy of the corresponding complexity classes. That is, for essentially any function$q:(0,1]\to\N$, we prove the existence ... more >>> TR18-097 | 15th May 2018 Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani #### Approximating Operator Norms via Generalized Krivine Rounding We consider the$(\ell_p,\ell_r)$-Grothendieck problem, which seeks to maximize the bilinear form$y^T A x$for an input matrix$A \in {\mathbb R}^{m \times n}$over vectors$x,y$with$\|x\|_p=\|y\|_r=1$. The problem is equivalent to computing the$p \to r^\ast$operator norm of$A$, where$\ell_{r^*}$is the dual norm ... more >>> TR18-096 | 13th May 2018 Venkatesan Guruswami, Andrii Riazanov #### Beating Fredman-Komlós for perfect$k$-hashing We say a subset$C \subseteq \{1,2,\dots,k\}^n$is a$k$-hash code (also called$k$-separated) if for every subset of$k$codewords from$C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as$(\log_2 |C|)/n$, of a$k$-hash code is ... more >>> TR18-095 | 11th May 2018 Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin #### Hardness Amplification for Non-Commutative Arithmetic Circuits We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire. This is part of a recent ... more >>> TR18-094 | 2nd May 2018 Amit Levi, Erik Waingarten #### Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of$n$-nodes graphs using rejection sampling queries requires complexity$\widetilde{\Omega}(n^2)$. Via reductions from the rejection sampling model, we give three new lower bounds for tolerant testing of Boolean functions ... more >>> TR18-093 | 10th May 2018 Irit Dinur, Pasin Manurangsi #### ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph$G = (V, E)$, an alphabet set$\Sigma$and, for each edge$\{u, v\} \in E$, a constraint$C_{uv} \subseteq \Sigma \times \Sigma$, the goal is to find an assignment$\sigma: V ... more >>>

TR18-092 | 4th May 2018
Marco Carmosino, Russell Impagliazzo, Manuel Sabin

#### Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires $n^{\epsilon k}$ time, for some constant $\epsilon > 1/2$, to count (note that these conjectures are significantly ... more >>>

TR18-091 | 4th May 2018
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

#### Improved decoding of Folded Reed-Solomon and Multiplicity Codes

In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions ... more >>>

TR18-090 | 4th May 2018
Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

#### Worst-case to average case reductions for the distance to a code

Revisions: 1

Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions $u=(u_1,\ldots, u_k)$, given as oracles, from a linear error correcting code $V$. The soundness of such systems relies on methods that act locally'' on $u$ and map it to a single function $u^*$ ... more >>>

TR18-089 | 27th April 2018
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

#### Half-duplex communication complexity

Revisions: 2

Suppose Alice and Bob are communicating bits to each other in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends bit and the other ... more >>>

TR18-088 | 24th April 2018
Ilya Volkovich

#### A story of AM and Unique-SAT

In the seminal work of \cite{Babai85}, Babai have introduced \emph{Arthur-Merlin Protocols} and in particular the complexity classes $MA$ and $AM$ as randomized extensions of the class $NP$. While it is easy to see that $NP \subseteq MA \subseteq AM$, it has been a long standing open question whether these classes ... more >>>

TR18-087 | 20th April 2018
Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang

#### Quantum Lov{\'a}sz Local Lemma: Shearer's Bound is Tight

Lov{\'a}sz Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all bad" events under some weakly dependent" condition. Over the last decades, the algorithmic aspect of LLL has also attracted lots of attention in theoretical computer science \cite{moser2010constructive, kolipaka2011moser, harvey2015algorithmic}. ... more >>>

TR18-086 | 23rd April 2018
Joseph Swernofsky

#### Tensor Rank is Hard to Approximate

Revisions: 1

We prove that approximating the rank of a 3-tensor to within a factor of $1 + 1/1852 - \delta$, for any $\delta > 0$, is NP-hard over any finite field. We do this via reduction from bounded occurrence 2-SAT.

more >>>

TR18-085 | 26th April 2018
Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan

#### XOR Codes and Sparse Random Linear Equations with Noise

A $k$-LIN instance is a system of $m$ equations over $n$ variables of the form $s_{i[1]} + \dots + s_{i[k]} =$ 0 or 1 modulo 2 (each involving $k$ variables). We consider two distributions on instances in which the variables are chosen independently and uniformly but the right-hand sides are ... more >>>

TR18-084 | 24th April 2018
Iftach Haitner, Nikolaos Makriyannis, Eran Omri

#### On the Complexity of Fair Coin Flipping

A two-party coin-flipping protocol is $\varepsilon$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $\varepsilon$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript '85] ... more >>>

TR18-083 | 25th April 2018
Tom Gur, Ron D. Rothblum, Yang P. Liu

#### An Exponential Separation Between MA and AM Proofs of Proximity

Revisions: 2

Non-interactive proofs of proximity allow a sublinear-time verifier to check that
a given input is close to the language, given access to a short proof. Two natural
variants of such proof systems are MA-proofs of Proximity (MAP), in which the proof
is a function of the input only, and AM-proofs ... more >>>

TR18-082 | 21st April 2018
Xin Li, Shachar Lovett, Jiapeng Zhang

#### Sunflowers and Quasi-sunflowers from Randomness Extractors

The Erdos-Rado sunflower theorem (Journal of Lond. Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding sunflower conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which ... more >>>

TR18-081 | 20th April 2018
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

#### On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1

In this paper, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random $d$-linear ... more >>>

TR18-080 | 6th March 2018
Moritz Gobbert

#### Edge Hop: A Framework to Show NP-Hardness of Combinatorial Games

The topic of this paper is a game on graphs called Edge Hop. The game's goal is to move a marked token from a specific starting node to a specific target node. Further, there are other tokens on some nodes which can be moved by the player under suitable conditions. ... more >>>

TR18-079 | 19th April 2018
Jayadev Acharya, Clement Canonne, Himanshu Tyagi

#### Distributed Simulation and Distributed Inference

Revisions: 1

Independent samples from an unknown probability distribution $\mathbf{p}$ on a domain of size $k$ are distributed across $n$ players, with each player holding one sample. Each player can communicate $\ell$ bits to a central referee in a simultaneous message passing (SMP) model of communication to help the referee infer a ... more >>>

TR18-078 | 23rd April 2018
Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

#### Small Set Expansion in The Johnson Graph

This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers
t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if
their intersection is of size t. The Johnson graph arises often ... more >>>

TR18-077 | 23rd April 2018
Boaz Barak, Pravesh Kothari, David Steurer

#### Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture

Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khot's 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain Grassmanian agreement tester''.
In this work, we show that the hypothesis of Dinur et al follows from a ... more >>>

TR18-076 | 22nd April 2018
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao

#### Torus polynomials: an algebraic approach to ACC lower bounds

Revisions: 1

We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, ... more >>>

TR18-075 | 23rd April 2018
Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

#### Boolean function analysis on high-dimensional expanders

Revisions: 1

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders.

Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse ... more >>>

TR18-074 | 23rd April 2018
Daniel Kane, Shachar Lovett, Shay Moran

#### Generalized comparison trees for point-location problems

Let $H$ be an arbitrary family of hyper-planes in $d$-dimensions. We show that the point-location problem for $H$
can be solved by a linear decision tree that only uses a special type of queries called \emph{generalized comparison queries}. These queries correspond to hyperplanes that can be written as a linear ... more >>>

TR18-073 | 21st April 2018
Amey Bhangale

#### NP-hardness of coloring $2$-colorable hypergraph with poly-logarithmically many colors

We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,

(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.
(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.

In terms of ... more >>>

TR18-072 | 19th April 2018
Avi Wigderson

#### On the nature of the Theory of Computation (ToC)

[ This paper is a (self contained) chapter in a new book on computational complexity theory, called Mathematics and Computation, available at https://www.math.ias.edu/avi/book ].

I attempt to give here a panoramic view of the Theory of Computation, that demonstrates its place as a revolutionary, disruptive science, and as a central, ... more >>>

TR18-071 | 15th April 2018
Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak

#### Computational Two-Party Correlation

Let $\pi$ be an efficient two-party protocol that given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ appears'' to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions:

\begin{itemize}
\item We develop new tools to ... more >>>

TR18-070 | 13th April 2018

#### Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More

We present explicit constructions of non-malleable codes with respect to the following tampering classes. (i) Linear functions composed with split-state adversaries: In this model, the codeword is first tampered by a split-state adversary, and then the whole tampered codeword is further tampered by a linear function. (ii) Interleaved split-state adversary: ... more >>>

TR18-069 | 14th April 2018
Oded Goldreich, Guy Rothblum

#### Constant-round interactive proof systems for AC0[2] and NC1

Revisions: 1

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.
Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than
the work of Reingold, Rothblum, and Rothblum (STOC, 2016).
Our proof system for AC0[2] supports a more ... more >>>

TR18-068 | 8th April 2018
Mrinal Kumar

#### On top fan-in vs formal degree for depth-3 arithmetic circuits

Revisions: 1

We show that over the field of complex numbers, every homogeneous polynomial of degree $d$ can be approximated (in the border complexity sense) by a depth-$3$ arithmetic circuit of top fan-in at most $d+1$. This is quite surprising since there exist homogeneous polynomials $P$ on $n$ variables of degree $2$, ... more >>>

TR18-067 | 9th April 2018
Alessandro Chiesa, Peter Manohar, Igor Shinkar

#### Testing Linearity against Non-Signaling Strategies

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.

We ... more >>>

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

2^{-a}$. We prove two lemmas: - Forbidden-set lemma: There exists$B \subseteq [N]$of size ... more >>> TR18-060 | 6th April 2018 Emanuele Viola #### Sampling lower bounds: boolean average-case and permutations We show that for every small AC$^{0}$circuit$C:\{0,1\}^{\ell}\to\{0,1\}^{m}$there exists a multiset$S$of$2^{m-m^{\Omega(1)}}$restrictions that preserve the output distribution of$C$and moreover \emph{polarize min-entropy: }the restriction of$C$to any$r\in S$either is constant or has polynomial min-entropy. This structural result is then applied to ... more >>> TR18-059 | 6th April 2018 Joshua Brakensiek, Venkatesan Guruswami #### Combining LPs and Ring Equations via Structured Polymorphisms Revisions: 1 Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, ... more >>> TR18-058 | 5th April 2018 Thomas Watson #### Amplification with One NP Oracle Query We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, one-sided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our ... more >>> TR18-057 | 26th March 2018 Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi #### Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH The$k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over$\mathbb F_2$, which can be stated as follows: given a generator matrix$\mathbf A$and an integer$k$, determine whether the code generated by$\mathbf A$has distance at most$k$. Here,$k$... more >>> TR18-056 | 20th March 2018 Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs #### Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing We present a worst case decoding problem whose hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst case hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The ... more >>> TR18-055 | 26th March 2018 Titus Dose #### Balance Problems for Integer Circuits Revisions: 5 We investigate the computational complexity of balance problems for$\{-,\cdot\}$-circuits computing finite sets of natural numbers. These problems naturally build on problems for integer expressions and integer circuits studied by Stockmeyer and Meyer (1973), McKenzie and Wagner (2007), and Glaßer et al (2010). Our work shows that the ... more >>> TR18-054 | 24th March 2018 Klim Efremenko, Elad Haramaty, Yael Kalai #### Interactive Coding with Constant Round and Communication Blowup Revisions: 1 The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since ... more >>> TR18-053 | 19th March 2018 Nader Bshouty #### Lower Bound for Non-Adaptive Estimate the Number of Defective Items We prove that to estimate within a constant factor the number of defective items in a non-adaptive group testing algorithm we need at least$\tilde\Omega((\log n)(\log(1/\delta)))$tests. This solves the open problem posed by Damaschke and Sheikh Muhammad. more >>> TR18-052 | 16th March 2018 Chi-Ning Chou, Mrinal Kumar, Noam Solomon #### Some Closure Results for Polynomial Factorization and Applications In a sequence of fundamental results in the 80's, Kaltofen showed that factors of multivariate polynomials with small arithmetic circuits have small arithmetic circuits. In other words, the complexity class$VP$is closed under taking factors. A natural question in this context is to understand if other natural classes of ... more >>> TR18-051 | 15th March 2018 Stasys Jukna #### Derandomizing Dynamic Programming and Beyond We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. We show that such circuits can be simulated by deterministic circuits with an only polynomial blowup in size. An algorithmic consequence is that randomization cannot substantially speed up dynamic programming. ... more >>> TR18-050 | 15th March 2018 Irit Dinur, Oded Goldreich, Tom Gur #### Every set in P is strongly testable under a suitable encoding We show that every set in$\cal P$is strongly testable under a suitable encoding. By strongly testable'' we mean having a (proximity oblivious) tester that makes a constant number of queries and rejects with probability that is proportional to the distance of the tested object from the property. By ... more >>> TR18-049 | 14th March 2018 Stasys Jukna, Hannes Seiwert #### Greedy can also beat pure dynamic programming Revisions: 1 Many dynamic programming algorithms are pure'' in that they only use min or max and addition operations in their recursion equations. The well known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on$n$-vertex graphs using only$O(n^2\log n)$operations. We prove that any pure DP algorithm ... more >>> TR18-048 | 11th March 2018 Ofer Grossman, Yang P. Liu #### Reproducibility and Pseudo-Determinism in Log-Space A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the results of a randomized log space computation without storing the output or randomness verbatim? Running the algorithm again with new random bits ... more >>> TR18-047 | 7th March 2018 Shachar Lovett #### A proof of the GM-MDS conjecture Revisions: 1 The GM-MDS conjecture of Dau et al. (ISIT 2014) speculates that the MDS condition, which guarantees the existence of MDS matrices with a prescribed set of zeros over large fields, is in fact sufficient for existence of such matrices over small fields. We prove this conjecture. more >>> TR18-046 | 9th March 2018 Oded Goldreich, Guy Rothblum #### Counting$t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems Revisions: 2 We present two main results regarding the complexity of counting the number of$t$-cliques in a graph. \begin{enumerate} \item{\em A worst-case to average-case reduction}: We reduce counting$t$-cliques in any$n$-vertex graph to counting$t$-cliques in typical$n$-vertex graphs that are drawn from a simple distribution of min-entropy${\widetilde\Omega}(n^2)$. For ... more >>> TR18-045 | 6th March 2018 Oded Goldreich, Dana Ron #### The Subgraph Testing Model We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph. The tester is given free access to a base graph$G=([\n],E)$, and oracle access to a function$f:E\to\{0,1\}$that represents a subgraph of$G$. The tester is ... more >>> TR18-044 | 5th March 2018 Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner #### Spatial Isolation Implies Zero Knowledge Even in a Quantum World Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, ... more >>> TR18-043 | 22nd February 2018 Andrei Romashchenko, Marius Zimand #### An operational characterization of mutual information in algorithmic information theory We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings$x$and$y$is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties, one having$x$and the complexity profile of the pair and the ... more >>> TR18-042 | 1st March 2018 Stasys Jukna #### Incremental versus Non-Incremental Dynamic Programming Many dynamic programming algorithms for discrete optimization problems are "pure" in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even "incremental" in that one of the inputs to the addition operations is a variable. We ... more >>> TR18-041 | 26th February 2018 Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov #### Reordering Rule Makes OBDD Proof Systems Stronger Atserias, Kolaitis, and Vardi [AKV04] showed that the proof system of Ordered Binary Decision Diagrams with conjunction and weakening, OBDD($\land$, weakening), simulates CP* (Cutting Planes with unary coefficients). We show that OBDD($\land$, weakening) can give exponentially shorter proofs than dag-like cutting planes. This is proved by showing that the Clique-Coloring ... more >>> TR18-040 | 21st February 2018 Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan #### Non-Malleable Codes for Small-Depth Circuits We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$tampering functions), our codes have codeword length$n = k^{1+o(1)}$for a$k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay ... more >>> TR18-039 | 23rd February 2018 Md Lutfar Rahman, Thomas Watson #### Complexity of Unordered CNF Games The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study ... more >>> TR18-038 | 21st February 2018 Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann #### Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees This paper studies lower bounds for arithmetic circuits computing (non-commutative) polynomials. Our conceptual contribution is an exact correspondence between circuits and weighted automata: algebraic branching programs are captured by weighted automata over words, and circuits with unique parse trees by weighted automata over trees. The key notion for understanding the ... more >>> TR18-037 | 21st February 2018 Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani #### Inapproximability of Matrix$p \rightarrow q$Norms We study the problem of computing the$p\rightarrow q$norm of a matrix$A \in R^{m \times n}$, defined as $\|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p}$ This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$,$q=1$), and has been ... more >>> TR18-036 | 21st February 2018 Michael Forbes, Sumanta Ghosh, Nitin Saxena #### Towards blackbox identity testing of log-variate circuits Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few ... more >>> TR18-035 | 21st February 2018 Manindra Agrawal, Sumanta Ghosh, Nitin Saxena #### Bootstrapping variables in algebraic circuits We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-$s$degree-$s$circuits that depend on the first$\log^{\circ c} s$variables (where$c$is a constant and we are ... more >>> TR18-034 | 15th February 2018 Young Kun Ko #### On Symmetric Parallel Repetition : Towards Equivalence of MAX-CUT and UG Unique Games Conjecture (UGC), proposed by [Khot02], lies in the center of many inapproximability results. At the heart of UGC lies approximability of MAX-CUT, which is a special instance of Unique Game.[KhotKMO04, MosselOO05] showed that assuming Unique Games Conjecture, it is NP-hard to distinguish between MAX-CUT instance that has a ... more >>> TR18-033 | 16th February 2018 Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz #### The Communication Complexity of Private Simultaneous Messages, Revisited Private Simultaneous Message (PSM) protocols were introduced by Feige, Kilian and Naor (STOC '94) as a minimal non-interactive model for information-theoretic three-party secure computation. While it is known that every function$f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$admits a PSM protocol with exponential communication of$2^{k/2}$(Beimel et al., TCC '14), the ... more >>> TR18-032 | 14th February 2018 Gil Cohen, Bernhard Haeupler, Leonard Schulman #### Explicit Binary Tree Codes with Polylogarithmic Size Alphabet This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. For every constant$\delta < 1$we give an explicit binary tree code with distance$\delta$and alphabet size$(\log{n})^{O(1)}$, where$n$is the depth of the tree. This ... more >>> TR18-031 | 15th February 2018 Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff #### On the Communication Complexity of Key-Agreement Protocols Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of ... more >>> TR18-030 | 9th February 2018 Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam #### NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have ... more >>> TR18-029 | 9th February 2018 Neeraj Kayal, vineet nair, Chandan Saha #### Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs Revisions: 1 Let us call a matrix$X$as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix$F$as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to ... more >>> TR18-028 | 7th February 2018 Xin Li #### Pseudorandom Correlation Breakers, Independence Preserving Mergers and their Applications Revisions: 1 The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in the following five seemingly different topics: seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey ... more >>> TR18-027 | 8th February 2018 Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan #### General Strong Polarization Ar\i kan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix$M$, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the$\textit{polarization}$of an associated$[0,1]$-bounded martingale, ... more >>> TR18-026 | 7th February 2018 Lijie Chen #### On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product Revisions: 1 In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets$A$and$B$of vectors, and the goal is to find$a \in A$and$b \in B$maximizing inner product$a \cdot b$. Max-IP is very basic and serves ... more >>> TR18-025 | 1st February 2018 Olaf Beyersdorff, Judith Clymo #### More on Size and Width in QBF Resolution In their influential paper `Short proofs are narrow -- resolution made simple', Ben-Sasson and Wigderson introduced a crucial tool for proving lower bounds on the lengths of proofs in the resolution calculus. Over a decade later their technique for showing lower bounds on the size of proofs, by examining the ... more >>> TR18-024 | 1st February 2018 Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin #### The Riis Complexity Gap for QBF Resolution We give an analogue of the Riis Complexity Gap Theorem for Quanti fied Boolean Formulas (QBFs). Every fi rst-order sentence$\phi$without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like Q-Resolution are either of polynomial size (if$\phi$has no models) or at least ... more >>> TR18-023 | 4th February 2018 Eran Iceland, Alex Samorodnitsky #### On coset leader graphs of structured linear codes Revisions: 1 We suggest a new approach to obtain bounds on locally correctable and some locally testable binary linear codes, by arguing that their coset leader graphs have high discrete Ricci curvature. The bounds we obtain for locally correctable codes are worse than the best known bounds obtained using quantum information theory, ... more >>> TR18-022 | 1st February 2018 Omer Reingold, Guy Rothblum, Ron Rothblum #### Efficient Batch Verification for UP Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by ... more >>> TR18-021 | 30th January 2018 Omri Ben-Eliezer, Eldar Fischer #### Earthmover Resilience and Testing in Ordered Structures One of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and hypergraphs this task has been mostly settled. However, for ordered structures such as strings, images, and ordered graphs, the characterization problem ... more >>> TR18-020 | 30th January 2018 Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari #### Computing the maximum using$(\min, +)$formulas Comments: 1 We study computation by formulas over$(min, +)$. We consider the computation of$\max\{x_1,\ldots,x_n\}$over$\mathbb{N}$as a difference of$(\min, +)$formulas, and show that size$n + n \log n$is sufficient and necessary. Our proof also shows that any$(\min, +)$formula computing the minimum of all ... more >>> TR18-019 | 28th January 2018 Zeyu Guo, Nitin Saxena, Amit Sinhababu #### Algebraic dependencies and PSPACE algorithms in approximative complexity Revisions: 1 Testing whether a set$\mathbf{f}$of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). The best complexity known is NP$^{\#\rm P}$(Mittmann, Saxena, Scheiblechner, Trans.AMS'14). ... more >>> TR18-018 | 22nd January 2018 John Hitchcock, Adewale Sekoni, Hadi Shafei #### Polynomial-Time Random Oracles and Separating Complexity Classes Bennett and Gill (1981) showed that P^A != NP^A != coNP^A for a random oracle A, with probability 1. We investigate whether this result extends to individual polynomial-time random oracles. We consider two notions of random oracles: p-random oracles in the sense of martingales and resource-bounded measure (Lutz, 1992; Ambos-Spies ... more >>> TR18-017 | 26th January 2018 Venkatesan Guruswami, Nicolas Resch, Chaoping Xing #### Lossless dimension expanders via linearized polynomials and subspace designs For a vector space$\mathbb{F}^n$over a field$\mathbb{F}$, an$(\eta,\beta)$-dimension expander of degree$d$is a collection of$d$linear maps$\Gamma_j : \mathbb{F}^n \to \mathbb{F}^n$such that for every subspace$U$of$\mathbb{F}^n$of dimension at most$\eta n$, the image of$U$under all the maps,$\sum_{j=1}^d ... more >>>

TR18-016 | 25th January 2018
Naomi Kirshner, Alex Samorodnitsky

#### On $\ell_4$ : $\ell_2$ ratio of functions with restricted Fourier support

Revisions: 1

Given a subset $A\subseteq \{0,1\}^n$, let $\mu(A)$ be the maximal ratio between $\ell_4$ and $\ell_2$ norms of a function whose Fourier support is a subset of $A$. We make some simple observations about the connections between $\mu(A)$ and the additive properties of $A$ on one hand, and between $\mu(A)$ and ... more >>>

TR18-015 | 25th January 2018
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

#### Pseudorandom Generators from Polarizing Random Walks

We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that ... more >>>

TR18-014 | 10th January 2018
Swagato Sanyal

#### A Composition Theorem via Conflict Complexity

Let $\R(\cdot)$ stand for the bounded-error randomized query complexity. We show that for any relation $f \subseteq \{0,1\}^n \times \mathcal{S}$ and partial Boolean function $g \subseteq \{0,1\}^n \times \{0,1\}$, $\R_{1/3}(f \circ g^n) = \Omega(\R_{4/9}(f) \cdot \sqrt{\R_{1/3}(g)})$. Independently of us, Gavinsky, Lee and Santha \cite{newcomp} proved this result. By an example ... more >>>

TR18-013 | 18th January 2018

#### Nondeterminisic Sublinear Time Has Measure 0 in P

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. ... more >>>

TR18-012 | 20th January 2018
Valentine Kabanets, Zhenjian Lu

#### Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates

We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree $d$ on $n$ inputs, our PRG for error $\epsilon$ has the seed ... more >>>

TR18-011 | 18th January 2018

#### Nonuniform Reductions and NP-Completeness

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for ... more >>>

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

#### Algorithmic polynomials

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

TR18-009 | 9th January 2018
Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

#### Non-Interactive Delegation for Low-Space Non-Deterministic Computation

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifi cally, letting $n$ denote the input length, we construct a delegation scheme for any language veri fiable in non-deterministic time and space $(T(n);S(n))$ with communication complexity $poly(S(n))$, verifi er ... more >>>

TR18-008 | 10th January 2018
Tom Gur, Igor Shinkar

#### An Entropy Lower Bound for Non-Malleable Extractors

A (k,\eps)-non-malleable extractor is a function nmExt : {0,1}^n x {0,1}^d -> {0,1} that takes two inputs, a weak source X~{0,1}^n of min-entropy k and an independent uniform seed s in {0,1}^d, and outputs a bit nmExt(X, s) that is \eps-close to uniform, even given the seed s and the ... more >>>

TR18-007 | 9th January 2018
Lior Gishboliner, Asaf Shapira

#### A Generalized Turan Problem and its Applications

Our first theorem in this papers is a hierarchy theorem for the query complexity of testing graph properties with $1$-sided error; more precisely, we show that for every super-polynomial $f$, there is a graph property whose 1-sided-error query complexity is $f(\Theta(1/\varepsilon))$. No result of this type was previously known for ... more >>>

TR18-006 | 10th January 2018
Subhash Khot, Dor Minzer, Muli Safra

#### Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

Revisions: 2

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes
the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a
contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves ... more >>>

TR18-005 | 9th January 2018

#### Adaptive Boolean Monotonicity Testing in Total Influence Time

The problem of testing monotonicity
of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ has received much attention
recently. Denoting the proximity parameter by $\varepsilon$, the best tester is the non-adaptive $\widetilde{O}(\sqrt{n}/\varepsilon^2)$ tester
of Khot-Minzer-Safra (FOCS 2015). Let $I(f)$ denote the total influence
of $f$. We give an adaptive tester whose running ... more >>>

TR18-004 | 3rd January 2018
Aayush Ojha, Raghunath Tewari

#### Circuit Complexity of Bounded Planar Cutwidth Graph Matching

Recently, perfect matching in bounded planar cutwidth bipartite graphs
$BGGM$ was shown to be in ACC$^0$ by Hansen et al.. They also conjectured that
the problem is in AC$^0$.
In this paper, we disprove their conjecture by showing that the problem is
not in AC$^0[p^{\alpha}]$ for every prime $p$. ... more >>>

TR18-003 | 2nd January 2018
Roei Tell

#### Proving that prBPP=prP is as hard as "almost" proving that P \ne NP

Revisions: 2

We show that any proof that $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$ necessitates proving circuit lower bounds that almost yield that $\mathcal{P}\ne\mathcal{NP}$. More accurately, we show that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then for essentially any super-constant function $f(n)=\omega(1)$ it holds that $NTIME[n^{f(n)}]\not\subseteq\mathcal{P}/\mathrm{poly}$. The conclusion of the foregoing conditional statement cannot be improved (to conclude that $\mathcal{NP}\not\subseteq\mathcal{P}/\mathrm{poly}$) without ... more >>>

TR18-002 | 31st December 2017
Constantinos Daskalakis, Gautam Kamath, John Wright

#### Which Distribution Distances are Sublinearly Testable?

Given samples from an unknown distribution $p$ and a description of a distribution $q$, are $p$ and $q$ close or far? This question of "identity testing" has received significant attention in the case of testing whether $p$ and $q$ are equal or far in total variation distance. However, in recent ... more >>>

TR18-001 | 2nd January 2018
Tim Roughgarden

#### Complexity Theory, Game Theory, and Economics

This document collects the lecture notes from my mini-course "Complexity Theory, Game Theory, and Economics," taught at the Bellairs Research Institute of McGill University, Holetown, Barbados, February 19-23, 2017, as the 29th McGill Invitational Workshop on Computational Complexity.

The goal of this mini-course is twofold: (i) to explain how complexity ... more >>>

ISSN 1433-8092 | Imprint