Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2018:
All reports in year 2018:
TR18-001 | 2nd January 2018
Tim Roughgarden

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

Revisions: 2

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

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-003 | 2nd January 2018
Roei Tell

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

Revisions: 5

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-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-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-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-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-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-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-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-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-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-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-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-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-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-017 | 26th January 2018
Venkatesan Guruswami, Nicolas Resch, Chaoping Xing

2^{-a}$. We prove two lemmas: - Forbidden-set lemma: There exists$B \subseteq [N]$of size ... 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-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-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-065 | 8th April 2018 Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma #### Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends Revisions: 1 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-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-067 | 9th April 2018
Alessandro Chiesa, Peter Manohar, Igor Shinkar

#### Testing Linearity against Non-Signaling Strategies

Revisions: 1

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-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-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-070 | 13th April 2018

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

Revisions: 3

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-071 | 15th April 2018
Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak

#### Computational Two-Party Correlation

Revisions: 1

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-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-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-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-075 | 23rd April 2018
Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha

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

Revisions: 2

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-076 | 22nd April 2018
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao Karingula

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

Revisions: 2

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-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-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-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-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-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-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-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-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-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-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-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-088 | 24th April 2018
Ilya Volkovich

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

Revisions: 1

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-089 | 27th April 2018
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

#### Half-duplex communication complexity

Revisions: 6

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-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-091 | 4th May 2018
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

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

Revisions: 1

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-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-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-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-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-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-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-098 | 17th May 2018 Oded Goldreich #### Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity Revisions: 1 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-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-100 | 18th May 2018 Eshan Chattopadhyay, Anindya De, Rocco Servedio #### Simple and efficient pseudorandom generators from Gaussian processes Revisions: 1 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-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-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-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-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-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-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-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-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-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-110 | 4th June 2018 Fu Li, David Zuckerman #### Improved Extractors for Recognizable and Algebraic Sources Revisions: 1 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-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-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-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-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-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-116 | 18th June 2018 Xue Chen, David Zuckerman #### Existence of Simple Extractors Revisions: 1 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-117 | 23rd June 2018
Fedor Part, Iddo Tzameret

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

Revisions: 2

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-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-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-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-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-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-123 | 3rd July 2018
Alessandro Chiesa, Peter Manohar, Igor Shinkar

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

Revisions: 1

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-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-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-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-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-128 | 11th July 2018
Ewin Tang

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

Revisions: 3

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-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-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-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-132 | 17th July 2018
Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

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

Revisions: 2

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-133 | 26th July 2018
Emanuele Viola

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

Revisions: 1

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-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-135 | 31st July 2018

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

Revisions: 1

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-136 | 1st August 2018
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

#### List Decoding with Double Samplers

Revisions: 1

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-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-138 | 10th August 2018
Shuichi Hirahara

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

Revisions: 1

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-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-140 | 11th August 2018
Ilan Komargodski, Ran Raz, Yael Tauman Kalai

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

Revisions: 1

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-141 | 6th August 2018
Sandip Sinha, Omri Weinstein

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

Revisions: 1

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-142 | 17th August 2018
Kaave Hosseini, Shachar Lovett

#### A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds

The Bogolyubov-Ruzsa lemma, in particular the quantitative bounds obtained by Sanders, plays a central role
in obtaining effective bounds for the inverse $U^3$ theorem for the Gowers norms. Recently, Gowers and Mili\'cevi\'c
applied a bilinear Bogolyubov-Ruzsa lemma as part of a proof of the inverse $U^4$ theorem
with effective bounds.
more >>>

TR18-143 | 16th August 2018
Mark Bun, Justin Thaler

#### The Large-Error Approximate Degree of AC$^0$

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight $\tilde{\Omega}(n^{1/2})$ lower bound on the threshold degree of the Surjectivity function on $n$ variables. This matches the best known threshold degree bound for any AC$^0$ ... more >>>

TR18-144 | 18th August 2018
Mert Saglam

#### Near log-convexity of measured heat in (discrete) time and consequences

Let $u,v \in \mathbb{R}^\Omega_+$ be positive unit vectors and $S\in\mathbb{R}^{\Omega\times\Omega}_+$ be a symmetric substochastic matrix. For an integer $t\ge 0$, let $m_t = \smash{\left\langle v,S^tu\right\rangle}$, which we view as the heat measured by $v$ after an initial heat configuration $u$ is let to diffuse for $t$ time steps according to ... more >>>

TR18-145 | 13th August 2018
Ryan O'Donnell, Rocco Servedio, Li-Yang Tan

#### Fooling Polytopes

We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \log n$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any $\{0,1\}$-integer program.

more >>>

TR18-146 | 18th August 2018
Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

#### Shortest path length with bounded-alternation $(\min, +)$ formulas

We study bounded depth $(\min, +)$ formulas computing the shortest path polynomial. For depth $2d$ with $d \geq 2$, we obtain lower bounds parametrized by certain fan-in restrictions on all $+$ gates except those at the bottom level. For depth $4$, in two regimes of the parameter, the bounds are ... more >>>

TR18-147 | 19th August 2018
Michael Forbes, Zander Kelley

#### Pseudorandom Generators for Read-Once Branching Programs, in any Order

A central question in derandomization is whether randomized logspace (RL) equals deterministic logspace (L). To show that RL=L, it suffices to construct explicit pseudorandom generators (PRGs) that fool polynomial-size read-once (oblivious) branching programs (roBPs). Starting with the work of Nisan, pseudorandom generators with seed-length $O(\log^2 n)$ were constructed. Unfortunately, ... more >>>

TR18-148 | 25th August 2018
Akash Kumar, C. Seshadhri, Andrew Stolman

#### Finding forbidden minors in sublinear time: a $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-149 | 25th August 2018
Craig Gentry, Charanjit Jutla

#### Obfuscation using Tensor Products

We describe obfuscation schemes for matrix-product branching programs that are purely algebraic and employ matrix algebra and tensor algebra over a finite field. In contrast to the obfuscation schemes of Garg et al (SICOM 2016) which were based on multilinear maps, these schemes do not use noisy encodings. We prove ... more >>>

TR18-150 | 27th August 2018

#### Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation

We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ with the pairs $(X_1,Y_1)$, $(X_2, Y_2)$, $\dots$ being drawn independently from some known probability distribution $\mu$. They ... more >>>

TR18-151 | 29th August 2018
Ankit Garg, Rafael Oliveira

#### Recent progress on scaling algorithms and applications

Scaling problems have a rich and diverse history, and thereby have found numerous
applications in several fields of science and engineering. For instance, the matrix scaling problem
has had applications ranging from theoretical computer science to telephone forecasting,
economics, statistics, optimization, among many other fields. Recently, a generalization of matrix
more >>>

TR18-152 | 30th August 2018
Krishnamoorthy Dinesh, Jayalal Sarma

#### Sensitivity, Affine Transforms and Quantum Communication Complexity

Revisions: 1

In this paper, we study the Boolean function parameters sensitivity ($\mathbf{s}$), block sensitivity ($\mathbf{bs}$), and alternation ($\mathbf{alt}$) under specially designed affine transforms and show several applications. For a function $f:\mathbb{F}_2^n \to \{0,1\}$, and $A = Mx+b$ for $M \in \mathbb{F}_2^{n \times n}$ and $b \in \mathbb{F}_2^n$, the result of the ... more >>>

TR18-153 | 22nd August 2018
Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma

#### New Bounds for Energy Complexity of Boolean Functions

Revisions: 1

For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\cal{B}$, the energy complexity of $C$ (denoted by $\mathbf{EC}_{{\cal B}}(C)$) is the maximum over all inputs $\{0,1\}^n$ the numbers of gates of the circuit $C$ (excluding the inputs) that output a one. Energy Complexity ... more >>>

TR18-154 | 7th September 2018
Stasys Jukna, Andrzej Lingas

#### Lower Bounds for Circuits of Bounded Negation Width

We consider Boolean circuits over $\{\lor,\land,\neg\}$ with negations applied only to input variables. To measure the amount of negation'' in such circuits, we introduce the concept of their negation width.'' In particular, a circuit computing a monotone Boolean function $f(x_1,\ldots,x_n)$ has negation width $w$ if no nonzero term produced (purely ... more >>>

TR18-155 | 8th September 2018
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal

#### Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates

A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design ... more >>>

TR18-156 | 8th September 2018
Mark Bun, Robin Kothari, Justin Thaler

#### Quantum algorithms and approximating polynomials for composed functions with shared inputs

Revisions: 1

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give ... more >>>

TR18-157 | 10th September 2018
Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

#### The Coin Problem in Constant Depth: Sample Complexity and Parity gates

Revisions: 2

The $\delta$-Coin Problem is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem in the model of constant-depth Boolean circuits and prove the following results.

1. Upper ... more >>>

TR18-158 | 11th September 2018
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam

#### Hardness magnification near state-of-the-art lower bounds

Revisions: 1

This work continues the development of hardness magnification. The latter proposes a strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful.

We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs ... more >>>

TR18-159 | 11th September 2018
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell

#### Expander-Based Cryptography Meets Natural Proofs

Revisions: 1

We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich's pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander's neighbor function and/or of the local predicate. Our two key conceptual contributions are:

* The security of Goldreich's PRG and OWF ... more >>>

TR18-160 | 12th September 2018
Anna Gal, Avishay Tal, Adrian Trejo Nuñez

#### Cubic Formula Size Lower Bounds Based on Compositions with Majority

We define new functions based on the Andreev function and prove that they require $n^{3}/polylog(n)$ formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the ... more >>>

TR18-161 | 13th September 2018
Justin Holmgren, Ron Rothblum

#### Delegating Computations with (almost) Minimal Time and Space Overhead

The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as ... more >>>

TR18-162 | 16th September 2018
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

#### A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit $C$ made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to $C$ in significantly better than ... more >>>

TR18-163 | 18th September 2018
Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

#### Adventures in Monotone Complexity and TFNP

$\mathbf{Separations:}$ We introduce a monotone variant of XOR-SAT and show it has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite ... more >>>

TR18-164 | 18th September 2018
Nikhil Gupta, Chandan Saha

#### On the symmetries of design polynomials

Revisions: 1

In a Nisan-Wigderson design polynomial (in short, a design polynomial), the gcd of every pair of monomials has a low degree. A useful example of such a polynomial is the following:
$$\text{NW}_{d,k}(\mathbf{x}) = \sum_{h \in \mathbb{F}_d[z], ~\deg(h) \leq k}{~~~~\prod_{i = 0}^{d-1}{x_{i, h(i)}}},$$
where $d$ is a prime, $\mathbb{F}_d$ is the ... more >>>

TR18-165 | 20th September 2018
Stefan Dantchev, Nicola Galesi, Barnaby Martin

#### Resolution and the binary encoding of combinatorial principles

We investigate the size complexity of proofs in $RES(s)$ -- an extension of Resolution working on $s$-DNFs instead of clauses -- for families of contradictions given in the {\em unusual binary} encoding. A motivation of our work is size lower bounds of refutations in Resolution for families of contradictions in ... more >>>

TR18-166 | 18th September 2018
Tayfun Pay, James Cox

#### An overview of some semantic and syntactic complexity classes

We review some semantic and syntactic complexity classes that were introduced to better understand the relationship between complexity classes P and NP. We also define several new complexity classes, some of which are associated with Mersenne numbers, and show their location in the complexity hierarchy.

more >>>

TR18-167 | 25th September 2018
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf

#### Improved bounds on Fourier entropy and Min-entropy

Given a Boolean function $f: \{-1,1\}^n\rightarrow \{-1,1\}$, define the Fourier distribution to be the distribution on subsets of $[n]$, where each $S\subseteq [n]$ is sampled with probability $\widehat{f}(S)^2$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures associated with the Fourier distribution: does ... more >>>

TR18-168 | 25th September 2018
Alex Samorodnitsky

#### An upper bound on $\ell_q$ norms of noisy functions

Revisions: 1

Let $T_{\epsilon}$ be the noise operator acting on functions on the boolean cube $\{0,1\}^n$. Let $f$ be a nonnegative function on $\{0,1\}^n$ and let $q \ge 1$. We upper bound the $\ell_q$ norm of $T_{\epsilon} f$ by the average $\ell_q$ norm of conditional expectations of $f$, given sets of roughly ... more >>>

TR18-169 | 18th September 2018
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev

#### Optimality of Linear Sketching under Modular Updates

We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in $n$ dimensions,
the existence of efficient streaming algorithms which can process $\Omega(n^2)$ updates implies efficient linear sketching algorithms with comparable cost.
This improves upon the previous work ... more >>>

TR18-170 | 4th October 2018
Nicola Galesi, Navid Talebanfard, Jacobo Toran

#### Cops-Robber games and the resolution of Tseitin formulas

We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed ... more >>>

TR18-171 | 10th October 2018
Oded Goldreich

#### Testing Graphs in Vertex-Distribution-Free Models

Revisions: 1

Prior studies of testing graph properties presume that the tester can obtain uniformly distributed vertices in the tested graph (in addition to obtaining answers to the some type of graph-queries).
Here we envision settings in which it is only feasible to obtain random vertices drawn according to an arbitrary distribution ... more >>>

TR18-172 | 11th October 2018
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

#### Building Strategies into QBF Proofs

Strategy extraction is of paramount importance for quantified Boolean formulas (QBF), both in solving and proof complexity. It extracts (counter)models for a QBF from a run of the solver resp. the proof of the QBF, thereby allowing to certify the solver's answer resp. establish soundness of the system. So far ... more >>>

TR18-173 | 17th October 2018
Eric Allender, Rahul Ilango, Neekon Vafa

#### The Non-Hardness of Approximating Circuit Size

Revisions: 1

The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under “local” reductions computable in TIME($n^{0.49}$). The question of whether MCSP is NP-hard (or indeed, hard even for small subclasses of P) ... more >>>

TR18-174 | 19th October 2018

#### Parity Decision Tree Complexity is Greater Than Granularity

Revisions: 2

We prove a new lower bound on the parity decision tree complexity $D_{\oplus}(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$. We show that $D_{\oplus}(f)\geq k+1$.

This lower bound is ... more >>>

TR18-175 | 23rd October 2018

#### Lifting Theorems for Equality

Revisions: 2

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ EQ_n$ where the inner function (the gadget) is Equality on $n$ bits. When $f$ is a total function on $p$ bits, it is easy to show via a rank argument that the communication complexity of $f\circ EQ_n$ ... more >>>

TR18-176 | 26th October 2018

#### The Log-Approximate-Rank Conjecture is False

We construct a simple and total XOR function $F$ on $2n$ variables that has only $O(\sqrt{n})$ spectral norm, $O(n^2)$ approximate rank and $n^{O(\log n)}$ approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of $\Omega(\sqrt{n})$. This yields the first exponential gap between the logarithm of the ... more >>>

TR18-177 | 1st October 2018
Alexander Knop

#### The Diptych of Communication Complexity Classes in the Best-partition Model and the Fixed-partition Model

Most of the research in communication complexity theory is focused on the
fixed-partition model (in this model the partition of the input between
Alice and Bob is fixed). Nonetheless, the best-partition model (the model
that allows Alice and Bob to choose the partition) has a lot of
more >>>

TR18-178 | 9th October 2018
Leroy Chew

#### Hardness and Optimality in QBF Proof Systems Modulo NP

Quantified Boolean Formulas (QBFs) extend propositional formulas with Boolean quantifiers. Working with QBF differs from propositional logic in its quantifier handling, but as propositional satisfiability (SAT) is a subproblem of QBF, all SAT hardness in solving and proof complexity transfers to QBF. This makes it difficult to analyse efforts dealing ... more >>>

TR18-179 | 31st October 2018
Dominik Scheder

#### PPSZ on CSP Instances with Multiple Solutions

We study the success probability of the PPSZ algorithm on $(d,k)$-CSP formulas. We greatly simplify the analysis of Hertli, Hurbain, Millius, Moser, Szedlak, and myself for the notoriously difficult case that the input formula has more than one satisfying assignment.

more >>>

TR18-180 | 3rd November 2018
Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre

#### Lower bounds for arithmetic circuits via the Hankel matrix

We study the complexity of representing polynomials by arithmetic circuits in both the commutative and the non-commutative settings. Our approach goes through a precise understanding of the more restricted setting where multiplication is not associative, meaning that we distinguish $(xy)z$ from $x(yz)$.

Our first and main conceptual result is a ... more >>>

TR18-181 | 30th October 2018
Giuseppe Persiano, Kevin Yeo

#### Lower Bounds for Differentially Private RAMs

In this work, we study privacy-preserving storage primitives that are suitable for use in data analysis on outsourced databases within the differential privacy framework. The goal in differentially private data analysis is to disclose global properties of a group without compromising any individual’s privacy. Typically, differentially private adversaries only ever ... more >>>

TR18-182 | 31st October 2018
Henry Corrigan-Gibbs, Dmitry Kogan

#### The Function-Inversion Problem: Barriers and Opportunities

Revisions: 1

We study preprocessing algorithms for the function-inversion problem. In this problem, an algorithm gets oracle access to a function $f\colon[N] \to [N]$ and takes as input $S$ bits of auxiliary information about $f$, along with a point $y \in [N]$. After running for time $T$, the algorithm must output an ... more >>>

TR18-183 | 5th November 2018
Dean Doron, Pooya Hatami, William Hoza

#### Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Revisions: 2

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... more >>>

TR18-184 | 5th November 2018
Iddo Tzameret, Stephen Cook

#### Uniform, Integral and Feasible Proofs for the Determinant Identities

Revisions: 1

Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over $GF(2)$ in Hrubes-Tzameret [SICOMP'15]. Specifically, we show that the multiplicativity of the determinant function and the ... more >>>

TR18-185 | 6th November 2018
Yonatan Nakar, Dana Ron

#### On the Testability of Graph Partition Properties

In this work we study the testability of a family of graph partition properties that generalizes a family previously studied by Goldreich, Goldwasser, and Ron (Journal of the ACM, 1998). While the family studied by Goldreich et al. includes a variety of natural properties, such as k-colorability and containing a ... more >>>

TR18-186 | 6th November 2018
Emanuele Viola

#### Lower bounds for data structures with space close to maximum imply circuit lower bounds

Revisions: 1

Let $f:\{0,1\}^{n}\to\{0,1\}^{m}$ be a function computable by a circuit with
unbounded fan-in, arbitrary gates, $w$ wires and depth $d$. With
a very simple argument we show that the $m$-query problem corresponding
to $f$ has data structures with space $s=n+r$ and time $(w/r)^{d}$,
for any $r$. As a consequence, in the ... more >>>

TR18-187 | 4th November 2018

#### Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids

Revisions: 4

Testing monotonicity of Boolean functions over the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic problem in property testing. When the range is real-valued, there are $\Theta(d\log n)$-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:
(1) Independence of $n$: There are testers ... more >>>

TR18-188 | 7th November 2018
Zeev Dvir, Alexander Golovnev, Omri Weinstein

#### Static Data Structure Lower Bounds Imply Rigidity

Revisions: 2

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of $t \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>>

TR18-189 | 8th November 2018
Ilias Diakonikolas, Daniel Kane

#### Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)

The degree-$d$ Chow parameters of a Boolean function $f: \bn \to \R$ are its degree at most $d$ Fourier coefficients.
It is well-known that degree-$d$ Chow parameters uniquely characterize degree-$d$ polynomial threshold functions
(PTFs)
within the space of all bounded functions. In this paper, we prove a robust ... more >>>

TR18-190 | 5th November 2018
Shachar Lovett, Jiapeng Zhang

#### DNF sparsification beyond sunflowers

There are two natural complexity measures associated with DNFs: their size, which is the number of clauses; and their width, which is the maximal number of variables in a clause. It is a folklore result that DNFs of small size can be approximated by DNFs of small width (logarithmic in ... more >>>

TR18-191 | 10th November 2018
Neeraj Kayal, Chandan Saha

#### Reconstruction of non-degenerate homogeneous depth three circuits

A homogeneous depth three circuit $C$ computes a polynomial
$$f = T_1 + T_2 + ... + T_s ,$$ where each $T_i$ is a product of $d$ linear forms in $n$ variables over some underlying field $\mathbb{F}$. Given black-box access to $f$, can we efficiently reconstruct (i.e. proper learn) a ... more >>>

TR18-192 | 12th November 2018
Alexander Golovnev, Alexander Kulikov

#### Circuit Depth Reductions

Revisions: 3

The best known circuit lower bounds against unrestricted circuits remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than $5n$. In this work, we suggest a first non-gate-elimination approach for ... more >>>

TR18-193 | 14th November 2018
Nicollas Sdroievski, Murilo Silva, André Vignatti

#### The Hidden Subgroup Problem and MKTP

We show that the Hidden Subgroup Problem for black-box groups is in $\mathrm{BPP}^\mathrm{MKTP}$ (where $\mathrm{MKTP}$ is the Minimum $\mathrm{KT}$ Problem) using the techniques of Allender et al (2018). We also show that the problem is in $\mathrm{ZPP}^\mathrm{MKTP}$ provided that there is a \emph{pac overestimator} computable in $\mathrm{ZPP}^\mathrm{MKTP}$ for the logarithm ... more >>>

TR18-194 | 15th November 2018
Amir Yehudayoff

#### Anti-concentration in most directions

Revisions: 5

We prove anti-concentration for the inner product of two independent random vectors in the discrete cube. Our results imply Chakrabarti and Regev's lower bound on the randomized communication complexity of the gap-hamming problem. They are also meaningful in the context of randomness extraction. The proof provides a framework for establishing ... more >>>

TR18-195 | 18th November 2018
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

#### Erasures versus Errors in Local Decoding and Property Testing

Revisions: 1

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.

Motivated by ... more >>>

TR18-196 | 19th November 2018
Omri Ben-Eliezer

#### Testing local properties of arrays

We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of $d$-dimensional arrays $f:[n]^d \to \Sigma$ is $k$-local if it can be defined by a family of $k \times \ldots \times k$ forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and ... more >>>

TR18-197 | 22nd November 2018
Andrej Bogdanov

#### Approximate degree of AND via Fourier analysis

Revisions: 1

We give a new proof that the approximate degree of the AND function over $n$ inputs is $\Omega(\sqrt{n})$. Our proof extends to the notion of weighted degree, resolving a conjecture of Kamath and Vasudevan. As a consequence we confirm that the approximate degree of any read-once depth-2 De Morgan formula ... more >>>

TR18-198 | 22nd November 2018
Irit Dinur, Tali Kaufman, Noga Ron-Zewi

#### From Local to Robust Testing via Agreement Testing

Revisions: 2

A local tester for an error-correcting code is a probabilistic procedure that queries a small subset of coordinates, accepts codewords with probability one, and rejects non-codewords with probability proportional to their distance from the code. The local tester is {\em robust} if for non-codewords it satisfies the stronger property that ... more >>>

TR18-199 | 24th November 2018
Lijie Chen, Roei Tell

#### Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds

The best-known lower bounds for the circuit class $\mathcal{TC}^0$ are only slightly super-linear. Similarly, the best-known algorithm for derandomization of this class is an algorithm for quantified derandomization (i.e., a weak type of derandomization) of circuits of slightly super-linear size. In this paper we show that even very mild quantitative ... more >>>

TR18-200 | 29th November 2018
Ashutosh Kumar, Raghu Meka, Amit Sahai

#### Leakage-Resilient Secret Sharing

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against a powerful adaptive adversary who may learn some leaked'' information about all the shares. We say that a secret sharing scheme is $p$-party leakage-resilient, if the secret remains statistically hidden even after an ... more >>>

TR18-201 | 30th November 2018
Anurag Anshu, Naresh Boddu, Dave Touchette

#### Quantum Log-Approximate-Rank Conjecture is also False

In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function $f$, hence refuting the log approximate rank conjecture of Lee and Shraibman [2009]. We provide an alternate proof of their randomized communication ... more >>>

TR18-202 | 1st December 2018
Xinyu Wu

#### A stochastic calculus approach to the oracle separation of BQP and PH

After presentations of the oracle separation of BQP and PH result by Raz and Tal [ECCC TR18-107], several people
(e.g. Ryan O’Donnell, James Lee, Avishay Tal) suggested that the proof may be simplified by
stochastic calculus. In this short note, we describe such a simplification.

more >>>

TR18-203 | 1st December 2018
Yael Kalai, Dakshita Khurana

#### Non-Interactive Non-Malleability from Quantum Supremacy

We construct non-interactive non-malleable commitments with respect to replacement, without setup in the plain model, under well-studied assumptions.

First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon>0$, under the following assumptions:

- Sub-exponential hardness of factoring or discrete ... more >>>

TR18-204 | 30th November 2018
Makrand Sinha, Ronald de Wolf

#### Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total
Boolean function, the sink function, that has polynomial approximate rank and
polynomial randomized communication complexity. This gives an exponential
separation between randomized communication complexity and logarithm of the
approximate rank, refuting the log-approximate-rank conjecture. We show that ... more >>>

TR18-205 | 3rd December 2018
Siddhesh Chaubal, Anna Gal

#### New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a ... more >>>

TR18-206 | 3rd December 2018

#### Equality Alone Does Not Simulate Randomness

Revisions: 1

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is Equality'. In this work, we show that even allowing access to an `Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function ... more >>>

TR18-207 | 5th December 2018
Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

#### On the Probabilistic Degree of OR over the Reals

We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $\epsilon$ in (0,1/3), the $\epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials ... more >>>

TR18-208 | 27th November 2018
Benny Applebaum, Prashant Nalini Vasudevan

#### Placing Conditional Disclosure of Secrets in the Communication Complexity Universe

Revisions: 2

In the *Conditional Disclosure of Secrets* (CDS) problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold $n$-bit inputs $x$ and $y$ respectively, wish to release a common secret $z$ to Carol (who knows both $x$ and $y$) if and only if the input $(x,y)$ satisfies ... more >>>

TR18-209 | 8th December 2018
Emanuele Viola

#### AC0 unpredictability

We prove that for every distribution $D$ on $n$ bits with Shannon
entropy $\ge n-a$ at most $O(2^{d}a\log^{d+1}g)/\gamma{}^{5}$ of
the bits $D_{i}$ can be predicted with advantage $\gamma$ by an
AC$^{0}$ circuit of size $g$ and depth $d$ that is a function of
all the bits of $D$ except $D_{i}$. ... more >>>

TR18-210 | 30th November 2018
Karthik C. S., Pasin Manurangsi

#### On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

Given a set of $n$ points in $\mathbb R^d$, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the $\ell_p$-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when ... more >>>

TR18-211 | 3rd December 2018

#### Parametric Shortest Paths in Planar Graphs

Revisions: 1

We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ ... more >>>

TR18-212 | 26th December 2018

#### Constructing Faithful Homomorphisms over Fields of Finite Characteristic

We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena (Information and Computing, 2013), and exploited by them, and Agrawal, Saha, Saptharishi and Saxena (Journal of Computing, 2016) to design algebraic independence based identity tests ... more >>>

TR18-213 | 28th December 2018
Moni Naor, Merav Parter, Eylon Yogev

#### The Power of Distributed Verifiers in Interactive Proofs

Revisions: 1

We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of $n$ nodes and a graph $G$ that defines their communication pattern. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the ... more >>>

ISSN 1433-8092 | Imprint