Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2018:
All reports in year 2018:
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

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

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: 1 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 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, Yang Liu, Ron D. Rothblum #### 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 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 Eshan Chattopadhyay, Xin Li #### 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 #### Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error$\varepsilon$for$n$-bit sources having min-entropy$poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is$poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a$poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any$k ... more >>>

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

#### Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends

A code $\mathcal{C}$ is $(1-\tau,L)$ erasure list-decodable if for every codeword $w$, after erasing any $1-\tau$ fraction of the symbols of $w$,
the remaining $\tau$-fraction of its symbols have at most $L$ possible completions into codewords of $\mathcal{C}$.
Non-explicitly, there exist binary $(1-\tau,L)$ erasure list-decodable codes having rate $O(\tau)$ and ... more >>>

TR18-064 | 3rd April 2018
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

#### Generalized Matrix Completion and Algebraic Natural Proofs

Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing (STOC), pages {653--664}, 2017) and independently by Grochow, Kumar, Saks and Saraf~(CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich's famous barrier result (J. Comput. ... more >>>

TR18-063 | 5th April 2018
William Hoza, David Zuckerman

#### Simple Optimal Hitting Sets for Small-Success $\mathbf{RL}$

Revisions: 1

We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order. Our generator has seed length $O\left(\frac{\log(wr) \log r}{\max\{1, \log \log w - \log \log r\}} + \log(1/\varepsilon)\right)$. This seed length improves on recent work by Braverman, Cohen, and ... more >>>

TR18-062 | 7th April 2018
Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

#### A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth $\Delta+1$ to one of product-depth $\Delta$ in the multilinear setting.

We show that for every positive $\Delta = \Delta(n) = o(\log n/\log \log n),$ there is an explicit multilinear polynomial $P^{(\Delta)}$ on $n$ variables that ... more >>>

TR18-061 | 6th April 2018
Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

#### Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs

Revisions: 4

We study how well can $q$-query decision trees distinguish between the
following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.
variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge 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

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

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

#### 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 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: 1

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

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

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

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 Revisions: 1 , Comments: 1 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 John Hitchcock, Adewale Sekoni #### 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 John Hitchcock, Hadi Shafei #### 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 C. Seshadhri, Deeparnab Chakrabarty #### Adaptive Boolean Monotonicity Testing in Total Influence Time The problem of testing monotonicity of a Boolean function$f:\{0,1\}^n \to \{0,1\}$has received much attention recently. Denoting the proximity parameter by$\varepsilon$, the best tester is the non-adaptive$\widetilde{O}(\sqrt{n}/\varepsilon^2)$tester of Khot-Minzer-Safra (FOCS 2015). Let$I(f)$denote the total influence of$f$. We give an adaptive tester whose running ... more >>> 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