REPORTS > 2017:
All reports in year 2017:
TR17-053 | 22nd March 2017
Mika Göös, Toniann Pitassi, Thomas Watson

#### Query-to-Communication Lifting for BPP

For any $n$-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f\circ g^n$, where $g$ is an index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs.\ ... more >>>

TR17-052 | 19th March 2017
Dieter van Melkebeek, Gautam Prakriya

#### Derandomizing Isolation in Space-Bounded Settings

We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance ... more >>>

TR17-051 | 16th March 2017
Mark Bun, Justin Thaler

#### A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by ... more >>>

TR17-050 | 15th March 2017
Joe Boninger, Joshua Brody, Owen Kephart

#### Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this ... more >>>

TR17-049 | 14th March 2017
Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

#### Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

We study the problem of testing unateness of functions $f:\{0,1\}^d \to \mathbb{R}.$ We give a $O(\frac{d}{\epsilon} \cdot \log\frac{d}{\epsilon})$-query nonadaptive tester and a $O(\frac{d}{\epsilon})$-query adaptive tester and show that both testers are optimal for a fixed distance parameter $\epsilon$. Previously known unateness testers worked only for Boolean functions, and their query ... more >>>

TR17-048 | 14th March 2017
Pavel Hrubes, Pavel Pudlak

#### A note on monotone real circuits

We show that if a Boolean function $f:\{0,1\}^n\to \{0,1\}$ can be computed by a monotone real circuit of size $s$ using $k$-ary monotone gates then $f$ can be computed by a monotone real circuit of size $O(sn^{k-2})$ which uses unary or binary monotone gates only. This partially solves an open ... more >>>

TR17-047 | 10th March 2017
Kasper Green Larsen, Omri Weinstein, Huacheng Yu

#### Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\log^{1.5} ... more >>> TR17-046 | 8th March 2017 Sebastian Berndt, Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk #### Learning Residual Alternating Automata Residuality plays an essential role for learning finite automata. While residual deterministic and nondeterministic automata have been understood quite well, fundamental questions concerning alternating automata (AFA) remain open. Recently, Angluin, Eisenstat, and Fisman have initiated a systematic study of residual AFAs and proposed an algorithm called AL* -an extension of ... more >>> TR17-045 | 7th March 2017 Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere #### Random CNFs are Hard for Cutting Planes Revisions: 1 The random k-SAT model is the most important and well-studied distribution over k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for satisfiablity algorithms, and lastly average-case hardness over this distribution has also been linked to hardness of approximation via Feige’s hypothesis. In this ... more >>> TR17-044 | 21st February 2017 Olaf Beyersdorff, Luke Hinde, Ján Pich #### Reasons for Hardness in QBF Proof Systems We aim to understand inherent reasons for lower bounds for QBF proof systems and revisit and compare two previous approaches in this direction. The first of these relates size lower bounds for strong QBF Frege systems to circuit lower bounds via strategy extraction (Beyersdorff & Pich, LICS'16). Here we ... more >>> TR17-043 | 3rd March 2017 Alexey Milovanov, Nikolay Vereshchagin #### Stochasticity in Algorithmic Statistics for Polynomial Time A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for$x$if it looks likely that$x$was drawn at random with respect to that distribution. In this paper, we ... more >>> TR17-042 | 6th March 2017 Pavel Hrubes, Pavel Pudlak #### Random formulas, monotone circuits, and interpolation We prove new lower bounds on the sizes of proofs in the Cutting Plane proof system, using a concept that we call "unsatisfiability certificate". This approach is, essentially, equivalent to the well-known feasible interpolation method, but is applicable to CNF formulas that do not seem suitable for interpolation. Specifically, we ... more >>> TR17-041 | 6th March 2017 Amnon Ta-Shma #### Explicit, almost optimal, epsilon-balanced codes The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance$\frac{1-\epsilon}{2}$and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an ... more >>> TR17-040 | 4th March 2017 Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao #### Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers Revisions: 2 We prove new cell-probe lower bounds for data structures that maintain a subset of$\{1,2,...,n\}$, and compute the median of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of ... more >>> TR17-039 | 28th February 2017 Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan #### Average-Case Fine-Grained Hardness We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., ... more >>> TR17-038 | 23rd February 2017 Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan #### Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations Revisions: 1 In the \emph{conditional disclosure of secrets} problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold inputs$x$and$y$respectively, wish to release a common secret$s$to Carol (who knows both$x$and$y$) if only if the input$(x,y)$satisfies some predefined predicate ... more >>> TR17-037 | 25th February 2017 Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla #### Understanding Cutting Planes for QBFs We define a cutting planes system CP+$\forall$red for quantified Boolean formulas (QBF) and analyse the proof-theoretic strength of this new calculus. While in the propositional case, Cutting Planes is of intermediate strength between resolution and Frege, our findings here show that the situation in QBF is slightly more complex: while ... more >>> TR17-036 | 22nd February 2017 Dean Doron, Francois Le Gall, Amnon Ta-Shma #### Probabilistic logarithmic-space algorithms for Laplacian solvers A recent series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system$L x=b$, where$L$is the normalized Laplacian of an undirected graph. In this paper we study the space complexity of the problem. more >>> TR17-035 | 23rd February 2017 Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena #### Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth-$4$circuits, which would ... more >>> TR17-034 | 21st February 2017 Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam #### On algebraic branching programs of small width In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>> TR17-033 | 19th February 2017 Daniel Kane, Shachar Lovett, Sankeerth Rao #### Labeling the complete bipartite graph with no zero cycles Assume that the edges of the complete bipartite graph$K_{n,n}$are labeled with elements of$\mathbb{F}_2^d$, such that the sum over any simple cycle is nonzero. What is the smallest possible value of$d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ... more >>> TR17-032 | 17th February 2017 Olaf Beyersdorff, Joshua Blinkhorn #### Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds We devise a new technique to prove lower bounds for the proof size in resolution-type calculi for quantified Boolean formulas (QBF). The new technique applies to the strong expansion system IR-calc and thereby also to the most studied QBF system Q-Resolution. Our technique exploits a clear semantic paradigm, showing the ... more >>> TR17-031 | 15th February 2017 Thomas Watson #### Quadratic Simulations of Merlin-Arthur Games The known proofs of$\text{MA}\subseteq\text{PP}$incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which$\text{MA-TIME}(t)\not\subseteq\text{P-TIME}(o(t^2))$. We also show that 2-sided-error Merlin--Arthur games can be simulated by 1-sided-error Arthur--Merlin games with quadratic ... more >>> TR17-030 | 15th February 2017 Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari #### An Improved Dictatorship Test with Perfect Completeness A Boolean function$f:\{0,1\}^n\rightarrow \{0,1\}$is called a dictator if it depends on exactly one variable i.e$f(x_1, x_2, \ldots, x_n) = x_i$for some$i\in [n]$. In this work, we study a$k$-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems. ... more >>> TR17-029 | 18th February 2017 Clement Canonne, Tom Gur #### An Adaptivity Hierarchy Theorem for Property Testing Revisions: 1 Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all ... more >>> TR17-028 | 17th February 2017 Mrinal Kumar #### A quadratic lower bound for homogeneous algebraic branching programs Revisions: 1 An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex$s$, and end vertex$t$and each edge having a weight which is an affine form in$\F[x_1, x_2, \ldots, x_n]$. An ABP computes a polynomial in a natural way, as the sum of weights of ... more >>> TR17-027 | 16th February 2017 Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma #### A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate We show a reduction from the existence of explicit t-non-malleable extractors with a small seed length, to the construction of explicit two-source extractors with small error for sources with arbitrarily small constant rate. Previously, such a reduction was known either when one source had entropy rate above half [Raz05] or ... more >>> TR17-026 | 17th February 2017 Valentine Kabanets, Daniel Kane, Zhenjian Lu #### A Polynomial Restriction Lemma with Applications A polynomial threshold function (PTF) of degree$d$is a boolean function of the form$f=\mathrm{sgn}(p)$, where$p$is a degree-$d$polynomial, and$\mathrm{sgn}$is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is ... more >>> TR17-025 | 16th February 2017 Pooya Hatami, Avishay Tal #### Pseudorandom Generators for Low-Sensitivity Functions A Boolean function is said to have maximal sensitivity$s$if$s$is the largest number of Hamming neighbors of a point which differ from it in function value. We construct a pseudorandom generator with seed-length$2^{O(\sqrt{s})} \cdot \log(n)$that fools Boolean functions on$n$variables with maximal sensitivity at ... more >>> TR17-024 | 16th February 2017 Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson #### Query-to-Communication Lifting for P^NP We prove that the$\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function$f$is quadratically related to the$\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of$f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to ... more >>> TR17-023 | 15th February 2017 Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich #### The Power of Natural Properties as Oracles We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We obtain new circuit lower bounds, as well as some hardness results for the relativized version ... more >>> TR17-022 | 13th February 2017 Benjamin Rossman, Srikanth Srinivasan #### Separation of AC$^0[\oplus]$Formulas and Circuits This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the$\mathrm{AC}^0[\oplus]$basis (unbounded fan-in AND, OR, NOT and MOD$_2$gates). We show, for all$d(n) \le O(\frac{\log n}{\log\log n})$, that there exist {\em polynomial-size depth-$d$circuits} that are not equivalent ... more >>> TR17-021 | 11th February 2017 Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas #### Reconstruction of full rank Algebraic Branching Programs An algebraic branching program (ABP) A can be modelled as a product expression$X_1\cdot X_2\cdot \dots \cdot X_d$, where$X_1$and$X_d$are$1 \times w$and$w \times 1$matrices respectively, and every other$X_k$is a$w \times w$matrix; the entries of these matrices are linear forms ... more >>> TR17-020 | 12th February 2017 Ran Raz #### A Time-Space Lower Bound for a Large Class of Learning Problems We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples. Our result is stated in terms of the norm ... more >>> TR17-019 | 8th February 2017 Andreas Krebs, Nutan Limaye, Michael Ludwig #### A Unified Method for Placing Problems in Polylogarithmic Depth Revisions: 1 In this work we consider the term evaluation problem which involves, given a term over some algebra and a valid input to the term, computing the value of the term on that input. This is a classical problem studied under many names such as formula evaluation problem, formula value problem ... more >>> TR17-018 | 6th February 2017 Oded Goldreich, Guy Rothblum #### Simple doubly-efficient interactive proof systems for locally-characterizable sets Revisions: 2 A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time. We present direct constructions of doubly-efficient interactive proof systems for problems in$\cal P$that are believed to have relatively high complexity. Specifically, such ... more >>> TR17-017 | 5th February 2017 Michal Moshkovitz, Dana Moshkovitz #### Mixing Implies Lower Bounds for Space Bounded Learning One can learn any hypothesis class$H$with$O(\log|H|)$labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires$|X|^{O(\log|H|)}$memory states, where$X$is the set of all labeled examples. A question that arises is how many labeled examples are needed in ... more >>> TR17-016 | 31st January 2017 Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena #### Irreducibility and deterministic r-th root finding over finite fields Constructing$r$-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree$r^e$(where$r$is a prime) over a given finite field$\F_q$of characteristic$p$(equivalently, constructing the bigger field$\F_{q^{r^e}}$). Both these problems have famous randomized ... more >>> TR17-015 | 4th February 2017 Ilan Komargodski, Moni Naor, Eylon Yogev #### White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so ... more >>> TR17-014 | 23rd January 2017 Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay #### Composition and Simulation Theorems via Pseudo-random Properties We prove a randomized communication-complexity lower bound for a composed OrderedSearch$\circ$IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>> TR17-013 | 23rd January 2017 Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan #### On polynomial approximations over$\mathbb{Z}/2^k\mathbb{Z}$We study approximation of Boolean functions by low-degree polynomials over the ring$\mathbb{Z}/2^k\mathbb{Z}$. More precisely, given a Boolean function F$:\{0,1\}^n \rightarrow \{0,1\}$, define its$k$-lift to be F$_k:\{0,1\}^n \rightarrow \{0,2^{k-1}\}$by$F_k(x) = 2^{k-F(x)}$(mod$2^k$). We consider the fractional agreement (which we refer to as$\gamma_{d,k}(F)$) of$F_k$with ... more >>> TR17-012 | 17th January 2017 Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau #### Emptiness Problems for Integer Circuits We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, ... more >>> TR17-011 | 22nd January 2017 Boaz Barak, Pravesh Kothari, David Steurer #### Quantum entanglement, sum of squares, and the log rank conjecture For every constant$\epsilon>0$, we give an$\exp(\tilde{O}(\sqrt{n}))$-time algorithm for the$1$vs$1-\epsilon$Best Separable State (BSS) problem of distinguishing, given an$n^2\times n^2$matrix$M$corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state$\rho$that$M$accepts with probability$1$, ... more >>> TR17-010 | 18th January 2017 Xiaodi Wu, Penghui Yao, Henry Yuen #### Raz-McKenzie simulation with the inner product gadget Revisions: 1 In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions$f$composed with the Inner Product gadget$g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$of logarithmic size. In other words, given a function$f: ... more >>>

TR17-009 | 19th January 2017
Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

#### Towards an algebraic natural proofs barrier via polynomial identity testing

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>

TR17-008 | 14th January 2017
Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan

#### Low-Complexity Cryptographic Hash Functions

Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is {\em collision resistant} hash functions (CRH), which prevent an efficient attacker from finding ... more >>>

TR17-007 | 19th January 2017
Michael Forbes, Amir Shpilka, Ben Lee Volk

#### Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds

We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been ... more >>>

TR17-006 | 15th December 2016
Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath

#### Testing Ising Models

Given samples from an unknown multivariate distribution $p$, is it possible to distinguish whether $p$ is the product of its marginals versus $p$ being far from every product distribution? Similarly, is it possible to distinguish whether $p$ equals a given distribution $q$ versus $p$ and $q$ being far from each ... more >>>

TR17-005 | 10th January 2017
Nir Bitansky

#### Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs

Revisions: 3

Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function's value $y$ at any point $x$, can also generate a non-interactive proof $\pi$ that $y$ is correct (relative to so), without compromising pseudorandomness at other points. Being a natural primitive with ... more >>>

TR17-004 | 8th January 2017
Scott Aaronson

#### P=?NP

In 1955, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science. Here I survey the status of this problem in 2017, ... more >>>

TR17-003 | 24th November 2016
Yi Deng

#### Magic Adversaries Versus Individual Reduction: Science Wins Either Way

Revisions: 1

We prove that \emph{at least} one of the following statements is true:

-- (Infinitely-often) Public-key encryption and key agreement can be based on injective one-way functions;
-- For every inverse polynomial $\epsilon$, the 4-round protocol from [Feige and Shamir, STOC 90] is distributional concurrent zero knowledge for any ... more >>>

TR17-002 | 6th January 2017
Frantisek Duris

#### Some notes on two lower bound methods for communication complexity

We compare two methods for proving lower bounds on standard two-party model of communication complexity, the Rank method and Fooling set method. We present bounds on the number of functions $f(x,y)$, $x,y\in\{0,1\}^n$, with rank of size $k$ and fooling set of size at least k, $k\in [1,2^n]$. Using these bounds ... more >>>

TR17-001 | 6th January 2017
Stephen Cook, Bruce Kapron

#### A Survey of Classes of Primitive Recursive Functions

This paper is a transcription of mimeographed course notes titled A Survey of Classes of Primitive Recursive Functions", by S.A. Cook, for the University of California Berkeley course Math 290, Sect. 14, January 1967. The notes present a survey of subrecursive function
classes (and classes of relations based on these ... more >>>

ISSN 1433-8092 | Imprint