Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > O:
A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

O
TR14-071 | 7th May 2014
Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem

We show an O(sqrt(n))-space and polynomial-time algorithm for solving the planar directed graph reachability problem. Imai et al. showed in CCC 2013 that the problem is solvable in O(n^{1/2+eps})-space and polynomial-time by using separators for planar graphs, and it has been open whether the space bound can be improved to ... 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 >>>

TR10-028 | 4th March 2010
Miklos Ajtai

Oblivious RAMs without Cryptographic Assumptions

Revisions: 1

Abstract. We show that oblivious on-line simulation with only
polylogarithmic increase in the time and space requirements is possible
on a probabilistic (coin flipping) RAM without using any cryptographic
assumptions. The simulation will fail with a negligible probability.
If $n$ memory locations are used, then the probability of failure is ... more >>>

TR17-118 | 20th July 2017
Xiaotie Deng, Zhe Feng, Rucha Kulkarni

Octahedral Tucker is PPA-Complete

Revisions: 1

The Octahedral Tucker problem considers an n-dimensional hypergrid of side length two, centered at the origin, triangulated by connecting the origin to all outside vertices (applied recursively on each of the lower dimensional hypergrids passing through their origins at the corresponding reduced dimensions). Each vertex is assigned a color in ... more >>>

TR09-139 | 17th December 2009

On the Power of Randomized Reductions and the Checkability of SAT

Revisions: 3

The closure of complexity classes is a elicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions ... more >>>

TR14-004 | 30th November 2013

On $r$-Simple $k$-Path

An $r$-simple $k$-path is a {path} in the graph of length $k$ that
passes through each vertex at most $r$ times. The \simpath{r}{k}
problem, given a graph $G$ as input, asks whether there exists an
$r$-simple $k$-path in $G$. We first show that this problem is
NP-Complete. We then show ... 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 >>>

TR19-034 | 5th March 2019
Pavel Hrubes

Revisions: 1

We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then $(x_1+\dots+x_n+1)^d+\epsilon ... more >>> TR22-001 | 28th December 2021 Yogesh Dahiya, Meena Mahajan On (Simple) Decision Tree Rank Revisions: 1 In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure ... more >>> TR05-077 | 15th July 2005 Zenon Sadowski On a D-N-optimal acceptor for TAUT The notion of an optimal acceptor for TAUT (the optimality property is stated only for input strings from TAUT) comes from the line of research aimed at resolving the question of whether optimal propositional proof systems exist. In this paper we introduce two new types of optimal acceptors, a D-N-optimal ... more >>> TR11-130 | 25th September 2011 Sergei Lozhkin, Alexander Shiganov On a Modification of Lupanov's Method with More Uniform Distribution of Fan-out In this paper we suggest a modification of classical Lupanov's method [Lupanov1958] that allows building circuits over the basis$\{\&,\vee,\neg\}$for Boolean functions of$n$variables with size at most $$\frac{2^n}{n}\left(1+\frac{3\log n + O(1)}{n}\right),$$ and with more uniform distribution of outgoing arcs by circuit gates. For almost all ... more >>> TR10-024 | 21st February 2010 Henning Wunderlich, Stefan Arnold On a singular value method in quantum communication complexity Comments: 1 We introduce a new lower bound method for bounded-error quantum communication complexity, the \emph{singular value method (svm)}, based on sums of squared singular values of the communication matrix, and we compare it with existing methods. The first finding is a constant factor improvement of lower bounds based on the spectral ... more >>> TR12-144 | 6th November 2012 Rocco Servedio, Emanuele Viola On a special case of rigidity We highlight the special case of Valiant's rigidity problem in which the low-rank matrices are truth-tables of sparse polynomials. We show that progress on this special case entails that Inner Product is not computable by small$\acz$circuits with one layer of parity gates close to the inputs. We then ... more >>> TR06-014 | 20th December 2005 Argimiro Arratia, Carlos E. Ortiz On a syntactic approximation to logics that capture complexity classes We formulate a formal syntax of approximate formulas for the logic with counting quantifiers,$\mathcal{SOLP}$, studied by us in \cite{aaco06}, where we showed the following facts:$(i)$In the presence of a built--in (linear) order,$\mathcal{SOLP}$can describe {\bf NP}--complete problems and fragments of it capture classes like {\bf P} ... more >>> TR10-086 | 17th May 2010 Henning Wunderlich On a Theorem of Razborov In an unpublished Russian manuscript Razborov proved that a matrix family with high rigidity over a finite field would yield a language outside the polynomial hierarchy in communication complexity. We present an alternative proof that strengthens the original result in several ways. In particular, we replace rigidity by the strictly ... more >>> TR17-034 | 21st February 2017 Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam On algebraic branching programs of small width Revisions: 1 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 >>> TR02-046 | 16th July 2002 Marek Karpinski On Approximability of Minimum Bisection Problem We survey some recent results on the complexity of computing approximate solutions for instances of the Minimum Bisection problem and formulate some intriguing and still open questions about the approximability status of that problem. Some connections to other optimization problems are also indicated. more >>> TR22-061 | 30th April 2022 Amey Bhangale, Subhash Khot, Dor Minzer On Approximability of Satisfiable$k$-CSPs: I We consider the$P$-CSP problem for$3$-ary predicates$P$on satisfiable instances. We show that under certain conditions on$P$and a$(1,s)$integrality gap instance of the$P$-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness$s+\varepsilon$, for every constant$\varepsilon>0$. ... more >>> TR95-016 | 2nd February 1995 U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern On approximately fair cost allocation in Euclidean TSP games We consider the problem of fair cost allocation for traveling salesman games for which the triangle inequality holds. We give examples showing that the core of such games may be empty, even for the case of Euclidean distances. On the positive side, we develop an LP-based ... more >>> TR99-039 | 24th September 1999 Johan Håstad On approximating CSP-B We prove that any constraint satisfaction problem where each variable appears a bounded number of times admits a nontrivial polynomial time approximation algorithm. more >>> TR07-011 | 19th December 2006 Bodo Manthey On Approximating Restricted Cycle Covers A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. The weight of a cycle cover of an edge-weighted graph ... more >>> TR16-120 | 1st August 2016 Dean Doron, Amir Sarid, Amnon Ta-Shma On approximating the eigenvalues of stochastic matrices in probabilistic logspace Revisions: 1 Approximating the eigenvalues of a Hermitian operator can be solved by a quantum logspace algorithm. We introduce the problem of approximating the eigenvalues of a given matrix in the context of classical space-bounded computation. We show that: - Approximating the second eigenvalue of stochastic operators (in a certain range of ... more >>> TR10-160 | 28th October 2010 Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan On Approximating the Entropy of Polynomial Mappings We investigate the complexity of the following computational problem: Polynomial Entropy Approximation (PEA): Given a low-degree polynomial mapping$p : F^n\rightarrow F^m$, where$F$is a finite field, approximate the output entropy$H(p(U_n))$, where$U_n$is the uniform distribution on$F^n$and$H$may be any of several entropy measures. ... more >>> TR05-094 | 9th August 2005 Michal Parnas, Dana Ron On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms Revisions: 1 We consider the problem of estimating the size,$VC(G)$, of a minimum vertex cover of a graph$G$, in sublinear time, by querying the incidence relation of the graph. We say that an algorithm is an$(\alpha,\eps)$-approximation algorithm if it outputs with high probability an estimate$\widehat{VC}$such that ... more >>> TR11-078 | 9th May 2011 Dana Ron, Gilad Tsur On Approximating the Number of Relevant Variables in a Function In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of the problem. In particular, we consider relaxations in which we have a ... more >>> TR98-024 | 28th April 1998 Wenceslas Fernandez de la Vega, Marek Karpinski On Approximation Hardness of Dense TSP and other Path Problems TSP(1,2), the Traveling Salesman Problem with distances 1 and 2, is the problem of finding a tour of minimum length in a complete weighted graph where each edge has length 1 or 2. Let$d_o$satisfy$0<d_o<1/2$. We show that TSP(1,2) has no PTAS on the set ... more >>> TR97-041 | 18th September 1997 Marek Karpinski, Juergen Wirtgen On Approximation Hardness of the Bandwidth Problem The bandwidth problem is the problem of enumerating the vertices of a given graph$G$such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications and is ... more >>> TR98-014 | 6th February 1998 Gunter Blache, Marek Karpinski, Juergen Wirtgen On Approximation Intractability of the Bandwidth Problem The bandwidth problem is the problem of enumerating the vertices of a given graph$G$such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications. There was not ... more >>> TR12-008 | 30th January 2012 Marek Karpinski, Richard Schmied On Approximation Lower Bounds for TSP with Bounded Metrics Revisions: 1 We develop a new method for proving explicit approximation lower bounds for TSP problems with bounded metrics improving on the best up to now known bounds. They almost match the best known bounds for unbounded metric TSP problems. In particular, we prove the best known lower bound for TSP with ... more >>> TR04-039 | 21st April 2004 Andrzej Lingas, Martin Wahlén On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems We consider the minor'' and homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest$h$such that the input graph has a minor isomorphic to$K_h$or a subgraph homeomorphic to$K_h,$respectively.We show the former to be approximable within$O(\sqrt {n} \log^{1.5} n)$by ... more >>> TR06-066 | 5th May 2006 Vitaly Feldman On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions Revisions: 1 We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over$\{0,1\}^n$. We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem ... more >>> TR17-110 | 22nd June 2017 Alessandro Chiesa, Peter Manohar, Igor Shinkar On Axis-Parallel Tests for Tensor Product Codes Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests. In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>> TR06-015 | 1st February 2006 Tomas Feder, Carlos Subi On Barnette's conjecture Barnette's conjecture is the statement that every 3-connected cubic planar bipartite graph is Hamiltonian. Goodey showed that the conjecture holds when all faces of the graph have either 4 or 6 sides. We generalize Goodey's result by showing that when the faces of such a graph are 3-colored, with adjacent ... more >>> TR20-095 | 24th June 2020 Mikito Nanashima On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions Revisions: 1 A black-box (BB) reduction is a central proof technique in theoretical computer science. However, the limitations on BB reductions have been revealed for several decades, and the series of previous work gives strong evidence that we should avoid a nonadaptive BB reduction to base cryptography on NP-hardness (e.g., Akavia et ... more >>> TR14-108 | 10th August 2014 Andrej Bogdanov, Christina Brzuska On Basing Size-Verifiable One-Way Functions on NP-Hardness Revisions: 1 We prove that if the hardness of inverting a size-verifiable one-way function can be based on NP-hardness via a general (adaptive) reduction, then coAM is contained in NP. This claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but was later retracted (STOC 2010). more >>> TR09-006 | 19th January 2009 David Xiao On basing ZK != BPP on the hardness of PAC learning Learning is a central task in computer science, and there are various formalisms for capturing the notion. One important model studied in computational learning theory is the PAC model of Valiant (CACM 1984). On the other hand, in cryptography the notion of learning nothing'' is often modelled by the simulation ... more >>> TR10-186 | 2nd December 2010 Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola On beating the hybrid argument The {\em hybrid argument} allows one to relate the {\em distinguishability} of a distribution (from uniform) to the {\em predictability} of individual bits given a prefix. The argument incurs a loss of a factor$k$equal to the bit-length of the distributions:$\epsilon$-distinguishability implies only$\epsilon/k$-predictability. ... more >>> TR15-072 | 23rd April 2015 Roei Tell On Being Far from Far and on Dual Problems in Property Testing Revisions: 4 For a set$\Pi$in a metric space and$\delta>0$, denote by$\mathcal{F}_\delta(\Pi)$the set of elements that are$\delta$-far from$\Pi$. In property testing, a$\delta$-tester for$\Pi$is required to accept inputs from$\Pi$and reject inputs from$\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of$\delta$-testing ... more >>> TR07-019 | 10th March 2007 Jin-Yi Cai, Pinyan Lu On Block-wise Symmetric Signatures for Matchgates We give a classification of block-wise symmetric signatures in the theory of matchgate computations. The main proof technique is matchgate identities, a.k.a. useful Grassmann-Pl\"{u}cker identities. more >>> TR22-137 | 26th September 2022 Daniel Avraham , Amir Yehudayoff On blocky ranks of matrices A matrix is blocky if it is a blowup of a permutation matrix. The blocky rank of a matrix M is the minimum number of blocky matrices that linearly span M. Hambardzumyan, Hatami and Hatami defined blocky rank and showed that it is connected to communication complexity and operator theory. ... more >>> TR98-030 | 9th June 1998 Stasys Jukna, Stanislav Zak On Branching Programs With Bounded Uncertainty We propose an information-theoretic approach to proving lower bounds on the size of branching programs (b.p.). The argument is based on Kraft-McMillan type inequalities for the average amount of uncertainty about (or entropy of) a given input during various stages of the computation. ... more >>> TR03-041 | 29th May 2003 Albert Atserias, Maria Luisa Bonet, Jordi Levy On Chvatal Rank and Cutting Planes Proofs We study the Chv\'atal rank of polytopes as a complexity measure of unsatisfiable sets of clauses. Our first result establishes a connection between the Chv\'atal rank and the minimum refutation length in the cutting planes proof system. The result implies that length lower bounds for cutting planes, or even for ... 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 >>> TR04-024 | 26th March 2004 Thomas Thierauf, Thanh Minh Hoang On Closure Properties of GapL Revisions: 1 , Comments: 1 We show necessary and sufficient conditions that certain algebraic functions like the rank or the signature of an integer matrix can be computed in GapL. more >>> TR17-177 | 16th November 2017 Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff On Communication Complexity of Classification Problems Revisions: 1 This work introduces a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of ... more >>> TR05-051 | 18th March 2005 Predrag Tosic On Complexity of Counting Fixed Points in Certain Classes of Graph Automata Revisions: 2 We study the computational complexity of counting the fixed point configurations in certain discrete dynamical systems. We prove that both exact and approximate counting in Sequential and Synchronous Dynamical Systems (SDSs and SyDS, respectrively) is computationally intractable, even when each node is required to update according to a symmetric Boolean ... more >>> TR05-074 | 8th June 2005 Li-Sha Huang, Xiaotie Deng On Complexity of Market Equilibria with Maximum Social Welfare We consider the computational complexity of the market equilibrium problem by exploring the structural properties of the Leontief exchange economy. We prove that, for economies guaranteed to have a market equilibrium, finding one with maximum social welfare or maximum individual welfare is NP-hard. In addition, we prove that counting the ... more >>> TR08-085 | 19th June 2008 Farid Ablayev, Airat Khasianov, Alexander Vasiliev On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions Revisions: 1 We consider Generalized Equality, the Hidden Subgroup, and related problems in the context of quantum Ordered Binary Decision Diagrams. For the decision versions of considered problems we show polynomial upper bounds in terms of quantum OBDD width. We apply a new modification of the fingerprinting technique and present the algorithms ... more >>> TR99-044 | 30th September 1999 Farid Ablayev On Complexity of Regular$(1,+k)$-Branching Programs A regular$(1,+k)$-branching program ($(1,+k)$-ReBP) is an ordinary branching program with the following restrictions: (i) along every consistent path at most$k$variables are tested more than once, (ii) for each node$v$on all paths from the source to$v$the same set$X(v)\subseteq X$of variables is ... more >>> TR00-038 | 24th May 2000 On Computation with Pulses We explore the computational power of formal models for computation with pulses. Such models are motivated by realistic models for biological neurons, and by related new types of VLSI (pulse stream VLSI''). In preceding work it was shown that the computational power of formal models for computation with pulses is ... more >>> TR11-107 | 22nd July 2011 Pavol Duris On Computational Power of Partially Blind Automata In this paper we deal with 1-way multihead finite automata, in which the symbol under only one head (called read head) controls its move and other heads cannot distinguish the input symbols, they can only distinguish the end-marker from the other input symbols and they are called the blind head. ... more >>> TR20-032 | 12th March 2020 Suryajith Chillara On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits Revisions: 2 In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of$r$(referred to as multi-$r$-ic circuits). The goal of this study is to make progress towards proving ... more >>> TR17-193 | 31st December 2017 Oded Goldreich, Avishay Tal On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions We consider new complexity measures for the model of multilinear circuits with general multilinear gates introduced by Goldreich and Wigderson (ECCC, 2013). These complexity measures are related to the size of canonical constant-depth Boolean circuits, which extend the definition of canonical depth-three Boolean circuits. We obtain matching lower and upper ... more >>> TR95-029 | 15th June 1995 Oded Goldreich, Leonid Levin, Noam Nisan On Constructing 1-1 One-Way Functions We show how to construct length-preserving 1-1 one-way functions based on popular intractability assumptions (e.g., RSA, DLP). Such 1-1 functions should not be confused with (infinite) families of (finite) one-way permutations. What we want and obtain is a single (infinite) 1-1 one-way function. more >>> TR03-017 | 27th March 2003 Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener On Converting CNF to DNF The best-known representations of boolean functions f are those of disjunctions of terms (DNFs) and as conjuctions of clauses (CNFs). It is convenient to define the DNF size of f as the minimal number of terms in a DNF representing f and the CNF size as the minimal number of ... more >>> TR09-040 | 20th April 2009 Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak On convex complexity measures Khrapchenko's classical lower bound$n^2$on the formula size of the parity function~$f$can be interpreted as designing a suitable measure of subrectangles of the combinatorial rectangle$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we arrived at the concept of \emph{convex measures}. We prove the more >>> TR22-092 | 2nd July 2022 Peter Ivanov, Liam Pavlovic, Emanuele Viola On correlation bounds against polynomials We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over$\mathbb{F}_{2}$. Our main contributions include: 1. In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their ... more >>> TR18-023 | 4th February 2018 Eran Iceland, Alex Samorodnitsky On coset leader graphs of structured linear codes Revisions: 1 We suggest a new approach to obtain bounds on locally correctable and some locally testable binary linear codes, by arguing that their coset leader graphs have high discrete Ricci curvature. The bounds we obtain for locally correctable codes are worse than the best known bounds obtained using quantum information theory, ... more >>> TR98-020 | 10th April 1998 Andris Ambainis, David Mix Barrington, Huong LeThanh On Counting$AC^0$Circuits with Negative Constants Continuing the study of the relationship between$TC^0$,$AC^0$and arithmetic circuits, started by Agrawal et al. (IEEE Conference on Computational Complexity'97), we answer a few questions left open in this paper. Our main result is that the classes Diff$AC^0$and Gap$AC^0$... more >>> TR20-104 | 12th July 2020 Oded Goldreich On Counting$t$-Cliques Mod 2 Revisions: 3 For a constant integer$t$, we consider the problem of counting the number of$t$-cliques$\bmod 2$in a given graph. We show that this problem is not easier than determining whether a given graph contains a$t$-clique, and present a simple worst-case to average-case reduction for it. The ... more >>> TR05-121 | 17th October 2005 Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson On counting homomorphisms to directed acyclic graphs We give a dichotomy theorem for the problem of counting homomorphisms to directed acyclic graphs.$H$is a fixed directed acyclic graph. The problem is, given an input digraph$G$, how many homomorphisms are there from$G$to$H$. We give a graph-theoretic classification, showing that for some digraphs$H$, ... more >>> TR95-062 | 14th December 1995 Amir M. Ben-Amram, Zvi Galil On Data Structure Tradeoffs and an Application to Union-Find Comments: 1 Consider a problem involving updates and queries of a data structure. Assume that there exists a family of algorithms which exhibit a tradeoff between query and update time. We demonstrate a general technique of constructing from such a family a single algorithm with best amortized time. We indicate some ... more >>> TR06-113 | 25th August 2006 Peter Buergisser On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity Let$\tau(n)$denote the minimum number of arithmetic operations sufficient to build the integer$n$from the constant~$1$. We prove that if there are arithmetic circuits for computing the permanent of$n$by$n$matrices having size polynomial in$n$, then$\tau(n!)$is polynomially bounded in$\log n$. Under the ... more >>> TR17-146 | 1st October 2017 Or Meir On Derandomized Composition of Boolean Functions Revisions: 4 The composition of two Boolean functions$f:\left\{0,1\right\}^{m}\to\left\{0,1\right\}$,$g:\left\{0,1\right\}^{n}\to\left\{0,1\right\}$is the function$f \diamond g$that takes as inputs$m$strings$x_{1},\ldots,x_{m}\in\left\{0,1\right\}^{n}$and computes $(f \diamond g)(x_{1},\ldots,x_{m})=f\left(g(x_{1}),\ldots,g(x_{m})\right).$ This operation has been used several times for amplifying different hardness measures of$f$and$g$. This comes at a cost: the ... more >>> TR13-152 | 7th November 2013 Oded Goldreich, Avi Wigderson On Derandomizing Algorithms that Err Extremely Rarely Revisions: 2 {\em Does derandomization of probabilistic algorithms become easier when the number of bad'' random inputs is extremely small?} In relation to the above question, we put forward the following {\em quantified derandomization challenge}: For a class of circuits$\cal C$(e.g., P/poly or$AC^0,AC^0[2]$) and a bounding function$B:\N\to\N$(e.g., ... more >>> TR02-009 | 17th January 2002 Petr Savicky On determinism versus unambiquous nondeterminism for decision trees Let$f$be a Boolean function. Let$N(f)=\dnf(f)+\dnf(\neg f)$be the sum of the minimum number of monomials in a disjunctive normal form for$f$and$\neg f$. Let$p(f)$be the minimum size of a partition of the Boolean cube into disjoint subcubes such that$f$is constant on more >>> TR22-173 | 3rd December 2022 Paul Beame, Sajin Koroth On Disperser/Lifting Properties of the Index and Inner-Product Functions Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated lifted' function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. Several important complexity ... more >>> TR05-064 | 26th June 2005 Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani On earthmover distance, metric labeling, and 0-extension We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, ... more >>> TR22-022 | 18th February 2022 Vikraman Arvind, Pushkar Joglekar On Efficient Noncommutative Polynomial Factorization via Higman Linearization Revisions: 3 In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result: Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where ... more >>> TR15-086 | 28th May 2015 Jop Briet On Embeddings of$\ell_1^k$from Locally Decodable Codes We show that any$q$-query locally decodable code (LDC) gives a copy of$\ell_1^k$with small distortion in the Banach space of$q$-linear forms on$\ell_{p_1}^N\times\cdots\times\ell_{p_q}^N$, provided$1/p_1 + \cdots + 1/p_q \leq 1$and where$k$,$N$, and the distortion are simple functions of the code parameters. We exhibit ... more >>> TR16-066 | 19th April 2016 Oded Goldreich, Maya Leshkowitz On Emulating Interactive Proofs with Public Coins The known emulation of interactive proof systems by public-coins interactive proof systems proceeds by selecting, at each round, a message such that each message is selected with probability that is at most polynomially larger than its probability in the original protocol. Specifically, the possible messages are essentially clustered according to ... more >>> TR03-043 | 14th May 2003 Elchanan Mossel, Amir Shpilka, Luca Trevisan On epsilon-Biased Generators in NC0 Cryan and Miltersen recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator such that every bit of the output depends on a constant number k of bits of the seed. They show that for k=3 there is always a distinguisher; ... more >>> TR04-013 | 10th February 2004 Oded Goldreich, Dana Ron On Estimating the Average Degree of a Graph. Following Feige, we consider the problem of estimating the average degree of a graph. Using neighbor queries'' as well as degree queries'', we show that the average degree can be approximated arbitrarily well in sublinear time, unless the graph is extremely sparse (e.g., unless the graph has a sublinear ... more >>> TR97-013 | 13th February 1997 Bernd Borchert, Dietrich Kuske, Frank Stephan On Existentially First-Order Definable Languages and their Relation to NP Pin & Weil [PW95] characterized the automata of existentially first-order definable languages. We will use this result for the following characterization of the complexity class NP. Assume that the Polynomial-Time Hierarchy does not collapse. Then a regular language L characterizes NP as an unbalanced polynomial-time leaf language if and ... more >>> TR06-028 | 21st February 2006 Jonathan Katz, Chiu-Yuen Koo On Expected Constant-Round Protocols for Byzantine Agreement In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e.,$t < n/2$), and relying only on the ... more >>> TR06-099 | 17th August 2006 Oded Goldreich On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits Revisions: 1 This paper concerns the possibility of developing a coherent theory of security when feasibility is associated with expected probabilistic polynomial-time (expected PPT). The source of difficulty is that the known definitions of expected PPT strategies (i.e., expected PPT interactive machines) do not support natural results of the ... more >>> TR19-169 | 21st November 2019 Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds Revisions: 2 The Exponential-Time Hypothesis ($ETH$) is a strengthening of the$\mathcal{P} \neq \mathcal{NP}$conjecture, stating that$3\text{-}SAT$on$n$variables cannot be solved in time$2^{\epsilon\cdot n}$, for some$\epsilon>0$. In recent years, analogous hypotheses that are exponentially-strong'' forms of other classical complexity conjectures (such as$\mathcal{NP}\not\subseteq\mathcal{BPP}$or$co\text{-}\mathcal{NP}\not\subseteq \mathcal{NP}$) have ... more >>> TR17-174 | 13th November 2017 Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao On Expressing Majority as a Majority of Majorities If$k<n$, can one express the majority of$n$bits as the majority of at most$k$majorities, each of at most$k$bits? We prove that such an expression is possible only if$k = \Omega(n^{4/5})$. This improves on a bound proved by Kulikov and Podolskii, who showed that ... more >>> TR95-058 | 20th November 1995 Amnon Ta-Shma On Extracting Randomness From Weak Random Sources We deal with the problem of extracting as much randomness as possible from a defective random source. We devise a new tool, a merger'', which is a function that accepts d strings, one of which is uniformly distributed, and outputs a single string that is guaranteed ... more >>> TR22-009 | 17th January 2022 C. Ramya, Anamay Tengse On Finer Separations between Subclasses of Read-once Oblivious ABPs Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials ... more >>> TR15-069 | 21st April 2015 Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat On Fortification of General Games Revisions: 1 A recent result of Moshkovitz~\cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel ... more >>> TR13-168 | 29th November 2013 Raghav Kulkarni, Avishay Tal On Fractional Block Sensitivity Revisions: 1 , Comments: 1 In this paper we study the fractional block sensitivityof Boolean functions. Recently, Tal (ITCS, 2013) and Gilmer, Saks, and Srinivasan (CCC, 2013) independently introduced this complexity measure, denoted by$fbs(f)$, and showed that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by$RC(f)$, which ... more >>> TR98-061 | 29th September 1998 Robert H. Sloan, Ken Takata, György Turán On frequent sets of Boolean matrices Given a Boolean matrix and a threshold t, a subset of the columns is frequent if there are at least t rows having a 1 entry in each corresponding position. This concept is used in the algorithmic, combinatorial approach to knowledge discovery and data mining. We consider the complexity aspects ... more >>> TR04-005 | 19th January 2004 Stasys Jukna On Graph Complexity Revisions: 1 , Comments: 1 A boolean circuit$f(x_1,\ldots,x_n)$\emph{represents} a graph$G$on$n$vertices if for every input vector$a\in\{0,1\}^n$with precisely two$1$'s in, say, positions$i$and$j$,$f(a)=1$precisely when$i$and$j$are adjacent in$G$; on inputs with more or less than two ... more >>> TR21-153 | 9th November 2021 Ronen Shaltiel, Emanuele Viola On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization The hardness vs.~randomness paradigm aims to explicitly construct pseudorandom generators$G:\{0,1\}^r \to \{0,1\}^m$that fool circuits of size$m$, assuming the existence of explicit hard functions. A high-end PRG'' with seed length$r=O(\log m)$(implying BPP=P) was achieved in a seminal work of Impagliazzo and Wigderson (STOC 1997), assuming \textsc{the ... more >>> TR15-013 | 28th January 2015 Subhash Khot, Igor Shinkar On Hardness of Approximating the Parameterized Clique Problem In the$Gap-clique(k, \frac{k}{2})$problem, the input is an$n$-vertex graph$G$, and the goal is to decide whether$G$contains a clique of size$k$or contains no clique of size$\frac{k}{2}$. It is an open question in the study of fixed parameterized tractability whether the$Gap-clique(k, \frac{k}{2})$problem ... more >>> TR15-067 | 21st April 2015 Pavel Hrubes On hardness of multilinearization, and VNP completeness in characteristics two For a boolean function$f:\{0,1\}^n\rightarrow \{0,1\}$, let$\hat{f}$be the unique multilinear polynomial such that$f(x)=\hat{f}(x)$holds for every$x\in \{0,1\}^n$. We show that, assuming$\hbox{VP}\not=\hbox{VNP}$, there exists a polynomial-time computable$f$such that$\hat{f}$requires super-polynomial arithmetic circuits. In fact, this$f$can be taken as a monotone 2-CNF, ... more >>> TR22-106 | 21st July 2022 Suryajith Chillara, Coral Grichener, Amir Shpilka On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts We say that two given polynomials$f, g \in R[x_1, \ldots, x_n]$, over a ring$R$, are equivalent under shifts if there exists a vector$(a_1, \ldots, a_n)\in R^n$such that$f(x_1+a_1, \ldots, x_n+a_n) = g(x_1, \ldots, x_n)$. This is a special variant of the polynomial projection problem in Algebraic ... more >>> TR06-131 | 6th October 2006 Konstantin Pervyshev On Heuristic Time Hierarchies We study the existence of time hierarchies for heuristic (average-case) algorithms. We prove that a time hierarchy exists for heuristics algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Earlier, Fortnow and Santhanam (FOCS'04) proved the existence of a time hierarchy for ... more >>> TR19-119 | 9th September 2019 Dean Doron, Amnon Ta-Shma, Roei Tell On Hitting-Set Generators for Polynomials that Vanish Rarely Revisions: 1 We study the following question: Is it easier to construct a hitting-set generator for polynomials$p:\mathbb{F}^n\rightarrow\mathbb{F}$of degree$d$if we are guaranteed that the polynomial vanishes on at most an$\epsilon>0$fraction of its inputs? We will specifically be interested in tiny values of$\epsilon\ll d/|\mathbb{F}|$. This question was ... more >>> TR11-147 | 2nd November 2011 Michael Forbes, Amir Shpilka On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This class of circuits has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but has no known such black-box algorithm. We recast this problem as ... more >>> TR16-124 | 12th August 2016 Subhash Khot On Independent Sets,$2$-to-$2$Games and Grassmann Graphs Revisions: 1 , Comments: 1 We present a candidate reduction from the$3$-Lin problem to the$2$-to-$2$Games problem and present a combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in a certain non-standard sense. A reduction that is sound in this non-standard sense implies that ... more >>> TR22-124 | 9th September 2022 Oded Goldreich, Guy Rothblum, Tal Skverer On Interactive Proofs of Proximity with Proof-Oblivious Queries Revisions: 3 Interactive proofs of proximity (IPPs) offer ultra-fast approximate verification of assertions regarding their input, where ultra-fast means that only a small portion of the input is read and approximate verification is analogous to the notion of approximate decision that underlies property testing. Specifically, in an IPP, the prover can make ... more >>> TR01-046 | 2nd July 2001 Oded Goldreich, Salil Vadhan, Avi Wigderson On Interactive Proofs with a Laconic Prover We continue the investigation of interactive proofs with bounded communication, as initiated by Goldreich and Hastad (IPL 1998). Let$L$be a language that has an interactive proof in which the prover sends few (say$b$) bits to the verifier. We prove that the complement$\bar L$has ... more >>> TR13-180 | 17th December 2013 Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian On Interactivity in Arthur-Merlin Communication and Stream Computation Revisions: 1 We introduce {\em online interactive proofs} (OIP), which are a hierarchy of communication complexity models that involve both randomness and nondeterminism (thus, they belong to the Arthur--Merlin family), but are {\em online} in the sense that the basic communication flows from Alice to Bob alone. The complexity classes defined by ... more >>> TR15-164 | 13th October 2015 Pavel Hrubes, Amir Yehudayoff On isoperimetric profiles and computational complexity The isoperimetric profile of a graph is a function that measures, for an integer$k$, the size of the smallest edge boundary over all sets of vertices of size$k$. We observe a connection between isoperimetric profiles and computational complexity. We illustrate this connection by an example from communication complexity, ... more >>> TR08-077 | 23rd May 2008 Felix Brandt, Felix Fischer, Markus Holzer On Iterated Dominance, Matrix Elimination, and Matched Paths We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>> TR05-023 | 16th February 2005 Robert H. Sloan, Balázs Szörényi, György Turán On k-term DNF with largest number of prime implicants It is known that a k-term DNF can have at most 2^k ? 1 prime implicants and this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a non-repeating ... more >>> TR14-029 | 4th March 2014 Oded Goldreich, Dana Ron On Learning and Testing Dynamic Environments Revisions: 3 We initiate a study of learning and testing dynamic environments, focusing on environment that evolve according to a fixed local rule. The (proper) learning task consists of obtaining the initial configuration of the environment, whereas for non-proper learning it suffices to predict its future values. The testing task consists of ... more >>> TR96-009 | 17th January 1996 Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio On Learning Branching Programs and Small Depth Circuits This paper studies the learnability of branching programs and small depth circuits with modular and threshold gates in both the exact and PAC learning models with and without membership queries. Some of the results extend earlier works in [GG95,ERR95,BTW95]. The main results are as follows. For branching programs we ... more >>> TR01-098 | 19th November 2001 Ke Yang On Learning Correlated Boolean Functions Using Statistical Query In this paper, we study the problem of using statistical query (SQ) to learn highly correlated boolean functions, namely, a class of functions where any pair agree on significantly more than a fraction 1/2 of the inputs. We give a limit on how well ... more >>> TR00-066 | 14th July 2000 Peter Auer On Learning from Ambiguous Information We investigate a variant of the Probably Almost Correct learning model where the learner has to learn from ambiguous information. The ambiguity is introduced by assuming that the learner does not receive single instances with their correct labels as training data, but that the learner receives ... more >>> TR01-006 | 18th October 2000 Rocco Servedio On Learning Monotone DNF under Product Distributions We show that the class of monotone$2^{O(\sqrt{\log n})}$-term DNF formulae can be PAC learned in polynomial time under the uniform distribution. This is an exponential improvement over previous algorithms in this model, which could learn monotone$o(\log^2 n)$-term DNF, and is the first efficient algorithm for ... more >>> TR00-014 | 16th February 2000 Matthias Krause, Stefan Lucks On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators \begin{abstract} A set$F$of$n$-ary Boolean functions is called a pseudorandom function generator (PRFG) if communicating with a randomly chosen secret function from$F$cannot be efficiently distinguished from communicating with a truly random function. We ask for the minimal hardware complexity of a PRFG. This question ... more >>> TR14-058 | 20th April 2014 Ilya Volkovich On Learning, Lower Bounds and (un)Keeping Promises We extend the line of research initiated by Fortnow and Klivans \cite{FortnowKlivans09} that studies the relationship between efficient learning algorithms and circuit lower bounds. In \cite{FortnowKlivans09}, it was shown that if a Boolean circuit class$\mathcal{C}$has an efficient \emph{deterministic} exact learning algorithm, (i.e. an algorithm that uses membership and ... more >>> TR13-065 | 21st April 2013 Yijia Chen, Joerg Flum On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P$\ne$NP or NP$\ne$coNP no progress has been achieved using the games. We show that for these problems it is already hard to ... more >>> TR22-012 | 2nd February 2022 Anup Rao, Oscar Sprumont On List Decoding Transitive Codes From Random Errors We study the error resilience of transitive linear codes over$F_2$. We give tight bounds on the weight distribution of every such code$C$, and we show how these bounds can be used to infer bounds on the error rates that$C$can tolerate on the binary symmetric channel. Using ... more >>> TR19-080 | 1st June 2019 Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas On List Recovery of High-Rate Tensor Codes We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>> TR19-070 | 14th May 2019 Alessandro Chiesa, Peter Manohar, Igor Shinkar On Local Testability in the Non-Signaling Setting Revisions: 1 Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions. We present general results about the local testability of linear codes in the non-signaling ... more >>> TR97-012 | 19th March 1997 Luca Trevisan On Local versus Global Satisfiability We prove an extremal combinatorial result regarding the fraction of satisfiable clauses in boolean CNF formulae enjoying a locally checkable property, thus solving a problem that has been open for several years. We then generalize the problem to arbitrary constraint satisfaction ... more >>> TR09-073 | 6th September 2009 Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan On Lower Bounds for Constant Width Arithmetic Circuits The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following. 1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit ... more >>> TR22-111 | 1st August 2022 Robert Andrews On Matrix Multiplication and Polynomial Identity Testing We show that lower bounds on the border rank of matrix multiplication can be used to non-trivially derandomize polynomial identity testing for small algebraic circuits. Letting$\underline{R}(n)$denote the border rank of$n \times n \times n$matrix multiplication, we construct a hitting set generator with seed length$O(\sqrt{n} \cdot ... more >>>

TR09-134 | 10th December 2009
Zeev Dvir

On matrix rigidity and locally self-correctable codes

Revisions: 1

We describe a new approach for the problem of finding {\rm rigid} matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and ... more >>>

TR05-070 | 6th July 2005
Mahdi Cheraghchi

On Matrix Rigidity and the Complexity of Linear Forms

The rigidity function of a matrix is defined as the minimum number of its entries that need to be changed in order to reduce the rank of the matrix to below a given parameter. Proving a strong enough lower bound on the rigidity of a matrix implies a nontrivial lower ... more >>>

TR17-183 | 28th November 2017
Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin

On Maximally Recoverable Local Reconstruction Codes

In recent years the explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the codes of choice for these applications. An $(n,r,h,a,q)$-LRC is a $q$-ary code, where encoding is as a ... more >>>

TR09-100 | 16th October 2009
Jakob Nordström, Alexander Razborov

On Minimal Unsatisfiability and Time-Space Trade-offs for $k$-DNF Resolution

In the context of proving lower bounds on proof space in $k$-DNF
resolution, [Ben-Sasson and Nordstr&ouml;m 2009] introduced the concept of
minimally unsatisfiable sets of $k$-DNF formulas and proved that a
minimally unsatisfiable $k$-DNF set with $m$ formulas can have at most
$O((mk)^{k+1})$ variables. They also gave an example of ... more >>>

TR20-079 | 15th May 2020
Hermann Gruber , Markus Holzer, Simon Wolfsteiner

On Minimizing Regular Expressions Without Kleene Star

Finite languages lie at the heart of literally every regular expression. Therefore, we investigate the approximation complexity of minimizing regular expressions without Kleene star, or, equivalently, regular expressions describing finite languages. On the side of approximation hardness, given such an expression of size~$s$, we prove that it is impossible to ... more >>>

TR15-011 | 22nd January 2015
Subhash Khot, Dor Minzer, Muli Safra

On Monotonicity Testing and Boolean Isoperimetric type Theorems

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we
give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function
$f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from
being monotone ... more >>>

TR01-049 | 11th July 2001
Stasys Jukna, Georg Schnitger

On Multi-Partition Communication Complexity of Triangle-Freeness

We show that recognizing the $K_3$-freeness and $K_4$-freeness of
graphs is hard, respectively, for two-player nondeterministic
communication protocols with exponentially many partitions and for
nondeterministic (syntactic) read-$s$ times branching programs.

The key ingradient is a generalization of a coloring lemma, due to
Papadimitriou and Sipser, which says that for every ... more >>>

TR16-051 | 7th April 2016
Ronald Cramer, Chaoping Xing, chen yuan

On Multi-Point Local Decoding of Reed-Muller Codes

Revisions: 4

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a ... 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 >>>

TR01-066 | 28th September 2001
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

On Multipartition Communication Complexity

We study k-partition communication protocols, an extension
of the standard two-party best-partition model to k input partitions.
The main results are as follows.

1. A strong explicit hierarchy on the degree of
non-obliviousness is established by proving that,
using k+1 partitions instead of k may decrease
the communication complexity from ... more >>>

TR16-138 | 3rd September 2016
Alexander A. Sherstov

On multiparty communication with large versus unbounded error

The communication complexity of $F$ with unbounded error is the limit of the $\epsilon$-error randomized complexity of $F$ as $\epsilon\to1/2.$ Communication complexity with weakly bounded error is defined similarly but with an additive penalty term that depends on $1/2-\epsilon$. Explicit functions are known whose two-party communication complexity with unbounded error ... more >>>

TR13-067 | 2nd May 2013
Oded Goldreich

On Multiple Input Problems in Property Testing

Revisions: 1

We consider three types of multiple input problems in the context of property testing.
Specifically, for a property $\Pi\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\begin{enumerate}
\item Direct $m$-Sum Problem for $\Pi$ and $\epsilon$:
Given a sequence of $m$ inputs, output a sequence ... more >>>

TR96-034 | 28th March 1996

On Neural Networks with Minimal Weights

Linear threshold elements are the basic building blocks of artificial neural
networks. A linear threshold element computes a function that is a sign of a
weighted sum of the input variables. The weights are arbitrary integers;
actually, they can be very big integers---exponential in the number of the
input variables. ... more >>>

TR05-058 | 24th May 2005
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

This paper studies the computational complexity of the following type of
quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find $x \in \{-1,+1\}^n$ that maximizes $x^TA x$. This problem recently attracted attention due to its application in various clustering settings (Charikar and Wirth, 2004) as well as ... more >>>

TR13-094 | 13th June 2013
Brendan Juba

On Non-automatizability in PAC-Semantics

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

TR17-094 | 25th May 2017
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

On Non-Optimally Expanding Sets in Grassmann Graphs

The paper investigates expansion properties of the Grassmann graph,
motivated by recent results of [KMS, DKKMS] concerning hardness
of the Vertex-Cover and of the $2$-to-$1$ Games problems. Proving the
hypotheses put forward by these papers seems to first require a better
understanding of these expansion properties.

We consider the edge ... more >>>

TR19-025 | 28th February 2019
Shuichi Hirahara, Osamu Watanabe

On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets

Revisions: 1

We investigate the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators as well as the set of Kolmogorov-random strings. This work contributes to (at least) two lines of research. One line of research is the study of the limits of black-box reductions to some distributional ... more >>>

TR97-030 | 25th August 1997
Martin Sauerhoff

On Nondeterminism versus Randomness for Read-Once Branching Programs

Randomized branching programs are a probabilistic model of computation
defined in analogy to the well-known probabilistic Turing machines.
In this paper, we present complexity theoretic results for randomized
Our main result shows that nondeterminism can be more powerful than
randomness for read-once branching programs. We present a ... more >>>

TR19-001 | 5th January 2019
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

On OBDD-based algorithms and proof systems that dynamically change order of variables

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>

TR06-128 | 5th October 2006
Shankar Kalyanaraman, Chris Umans

On obtaining pseudorandomness from error-correcting codes.

A number of recent results have constructed randomness extractors
and pseudorandom generators (PRGs) directly from certain
error-correcting codes. The underlying construction in these
results amounts to picking a random index into the codeword and
outputting $m$ consecutive symbols (the codeword is obtained from
the weak random source in the case ... more >>>

TR02-020 | 13th March 2002
Elizaveta Okol'nishnikova

On one lower bound for branching programs

The method of obtaining lower bounds on the complexity
of Boolean functions for nondeterministic branching programs
is proposed.
A nonlinear lower bound on the complexity of characteristic
functions of Reed--Muller codes for nondeterministic
branching programs is obtained.

more >>>

TR22-104 | 18th July 2022

On One-Sided Testing Affine Subspaces

Revisions: 1

We study the query complexity of one-sided $\epsilon$-testing the class of Boolean functions $f:F^n\to \{0,1\}$ that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where $F$ is any finite field. We give a polynomial-time $\epsilon$-testers that ask $\tilde O(1/\epsilon)$ queries. This improves the query complexity $\tilde O(|F|/\epsilon)$ ... more >>>

TR20-052 | 14th April 2020
Yanyi Liu, Rafael Pass

On One-way Functions and Kolmogorov Complexity

Revisions: 2

We prove the equivalence of two fundamental problems in the theory of computation:

- Existence of one-way functions: the existence of one-way functions (which in turn are equivalent to pseudorandom generators, pseudorandom functions, private-key encryption schemes, digital signatures, commitment schemes, and more).

- Mild average-case hardness of $K^{poly}$-complexity: ... more >>>

TR21-059 | 20th April 2021
Yanyi Liu, Rafael Pass

On One-way Functions from NP-Complete Problems

Revisions: 2

We present the first natural $\NP$-complete problem whose average-case hardness w.r.t. the uniform distribution over instances implies the existence of one-way functions (OWF). In fact, we prove that the existence of OWFs is \emph{equivalent} to mild average-case hardness of this $\NP$-complete problem. The problem, which originated in the 1960s, is ... more >>>

TR00-006 | 26th January 2000
E.A. Okol'nishnikiva

On operations of geometrical projection and monotone extension

Some operations over Boolean functions are considered. It is shown that
the operation of the geometrical projection and the operation of the
monotone extension can increase the complexity of Boolean functions for
formulas in each finite basis, for switching networks, for branching
programs, and read-$k$-times ... more >>>

TR10-193 | 5th December 2010
Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography

The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krajicek and Pudlak (1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (2009) ... more >>>

TR11-170 | 16th December 2011

On Optimal Multi-Dimensional Mechanism Design

We efficiently solve the optimal multi-dimensional mechanism design problem for independent bidders with arbitrary demand constraints when either the number of bidders is a constant or the number of items is a constant. In the first setting, we need that each bidder's values for the items are sampled from a ... more >>>

TR10-008 | 13th January 2010
Yijia Chen, Joerg Flum

On optimal proof systems and logics for PTIME

Revisions: 1

We prove that TAUT has a $p$-optimal proof system if and only if $L_\le$, a logic introduced in [Gurevich, 88], is a P-bounded logic for P. Furthermore, using the method developed in [Chen and Flum, 10], we show that TAUT has no \emph{effective} $p$-optimal proof system under some reasonable complexity-theoretic ... more >>>

TR97-023 | 3rd June 1997
S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener

On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs

It is known that if a Boolean function f in n variables
has a DNF and a CNF of size at most N then f also has a
(deterministic) decision tree of size $\exp(O(\log n\log^2 N)$.
We show that this simulation {\em cannot} be ... more >>>

TR04-074 | 26th August 2004
Emanuele Viola

On Parallel Pseudorandom Generators

Revisions: 1

We study pseudorandom generator (PRG) constructions $G^f : {0,1}^l \to {0,1}^{l+s}$ from one-way functions $f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form $G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$
where $C$ is a polynomial-size constant depth circuit
and $C$ and the $q$'s are generated from $x$ arbitrarily.
more >>>

TR15-039 | 16th March 2015
Anup Rao, Makrand Sinha

On Parallelizing Streaming Algorithms

We study the complexity of parallelizing streaming algorithms (or equivalently, branching programs). If $M(f)$ denotes the minimum average memory required to compute a function $f(x_1,x_2, \dots, x_n)$ how much memory is required to compute $f$ on $k$ independent streams that arrive in parallel? We show that when the inputs (updates) ... more >>>

TR07-106 | 10th September 2007
Yijia Chen, Martin Grohe, Magdalena Grüber

On Parameterized Approximability

Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability.
The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems.

more >>>

TR09-067 | 18th August 2009

On Parity Check $(0,1)$-Matrix over $Z_p$

Revisions: 1

We prove that for every prime $p$ there exists a $(0,1)$-matrix
$M$ of size $t_p(n,m)\times n$ where
$$t_p(n,m)=O\left(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})}\right)$$ such that every
$m$ columns of $M$ are linearly independent over $\Z_p$, the field
of integers modulo $p$ (and therefore over any field of
characteristic $p$ and over the real ... more >>>

TR20-119 | 1st August 2020
Nikhil Mande, Swagato Sanyal

On parity decision trees for Fourier-sparse Boolean functions

We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows. Let $f : \mathbb{F}_2^n \to \{-1, 1\}$ be a Boolean function with Fourier support ... more >>>

TR15-132 | 13th August 2015
Daniel Reichman, Igor Shinkar

On Percolation and NP-Hardness

Revisions: 2

We consider the robustness of computational hardness of problems
whose input is obtained by applying independent random deletions to worst-case instances.
For some classical NP-hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary
graph are ... more >>>

TR08-067 | 4th June 2008
Scott Aaronson

On Perfect Completeness for QMA

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA and QMA1 ... 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 >>>

TR16-068 | 28th April 2016

On Polynomial Approximations to $\mathrm{AC}^0$

Revisions: 1

We make progress on some questions related to polynomial approximations of $\mathrm{AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC 1991), that any $\mathrm{AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabilistic polynomial over the reals ... more >>>

TR98-054 | 26th August 1998
Igor E. Shparlinski

On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems

Lower bounds are obtained on the degree and the number of monomials of
Boolean functions, considered as a polynomial over $GF(2)$,
which decide if a given $r$-bit integer is square-free.
Similar lower bounds are also obtained for polynomials
over the reals which provide a threshold representation
more >>>

TR96-043 | 16th August 1996
Edmund Ihler

On polynomial time approximation schemes and approximation preserving reductions

We show that a fully polynomial time approximation scheme given
for an optimization problem can always be simply modified to a
polynomial time algorithm solving the problem optimally if the
computation model is the deterministic Turing Machine or the
logarithmic cost RAM and ... more >>>

TR21-149 | 5th November 2021
Sevag Gharibian, Dorian Rudolph

On polynomially many queries to NP or QMA oracles

We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$ and $P^{QMA}$, respectively.
The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate ... more >>>

TR04-031 | 22nd March 2004
Troy Lee, Andrei Romashchenko

On Polynomially Time Bounded Symmetry of Information

The information contained in a string $x$ about a string $y$
is defined as the difference between the Kolmogorov complexity
of $y$ and the conditional Kolmogorov complexity of $y$ given $x$,
i.e., $I(x:y)=\C(y)-\C(y|x)$. From the well-known Kolmogorov--Levin Theorem it follows that $I(x:y)$ is symmetric up to a small ... more >>>

TR16-156 | 12th October 2016
Eli Ben-Sasson, Alessandro Chiesa, Michael Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

On Probabilistic Checking in Perfect Zero Knowledge

Revisions: 1

We present the first constructions of *single*-prover proof systems that achieve *perfect* zero knowledge (PZK) for languages beyond NP, under no intractability assumptions:

1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and ... more >>>

TR05-137 | 21st November 2005
Emanuele Viola

On Probabilistic Time versus Alternating Time

We prove several new results regarding the relationship between probabilistic time, BPTime(t), and alternating time, \Sigma_{O(1)} Time(t). Our main results are the following:

1) We prove that BPTime(t) \subseteq \Sigma_3 Time(t polylog(t)). Previous results show that BPTime(t) \subseteq \Sigma_2 Time(t^2 log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83) ... more >>>

TR06-136 | 22nd October 2006
Mihir Bellare, Oded Goldreich

On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge

This note points out a gap between two natural formulations of
the concept of a proof of knowledge, and shows that in all
natural cases (e.g., NP-statements) this gap can be closed.
The aforementioned formulations differ by whether they refer to
(all possible) probabilistic or deterministic prover strategies.
Unlike ... more >>>

TR05-018 | 6th February 2005
Oded Goldreich

On Promise Problems (a survey in memory of Shimon Even [1935-2004])

The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
notion has found in the twenty years that elapsed.
These include the notion ... more >>>

TR20-034 | 12th March 2020
Erfan Khaniki

On Proof complexity of Resolution over Polynomial Calculus

Revisions: 3

The refutation system ${Res}_R({PC}_d)$ is a natural extension of resolution refutation system such that it operates with disjunctions of degree $d$ polynomials over ring $R$ with boolean variables. For $d=1$, this system is called ${Res}_R({lin})$. Based on properties of $R$, ${Res}_R({lin})$ systems can be too strong to prove lower ... more >>>

TR22-013 | 5th February 2022

On properties that are non-trivial to test

In this note we show that all sets that are neither finite nor too dense are non-trivial to test in the sense that, for every $\epsilon>0$, distinguishing between strings in the set and strings that are $\epsilon$-far from the set requires $\Omega(1/\epsilon)$ queries.
Specifically, we show that if, for ... more >>>

TR13-097 | 25th June 2013
Mikolas Janota, Joao Marques-Silva

On Propositional QBF Expansions and Q-Resolution

Over the years, proof systems for propositional satisfiability (SAT)
have been extensively studied. Recently, proof systems for
quantified Boolean formulas (QBFs) have also been gaining attention.
Q-resolution is a calculus enabling producing proofs from
DPLL-based QBF solvers. While DPLL has become a dominating technique
for SAT, QBF has been tackled ... more >>>

TR94-006 | 12th December 1994
Alexander Razborov

On provably disjoint NP-pairs

In this paper we study the pairs $(U,V)$ of disjoint ${\bf NP}$-sets
representable in a theory $T$ of Bounded Arithmetic in the sense that
$T$ proves $U\cap V=\emptyset$. For a large variety of theories $T$
we exhibit a natural disjoint ${\bf NP}$-pair which is complete for the
class of disjoint ... more >>>

TR19-176 | 4th December 2019
Gal Arnon, Guy Rothblum

On Prover-Efficient Public-Coin Emulation of Interactive Proofs

Revisions: 4

A central question in the study of interactive proofs is the relationship between private-coin proofs, where the verifier is allowed to hide its randomness from the prover, and public-coin proofs, where the verifier's random coins are sent to the prover.

In this work, we study transformations ... more >>>

TR08-041 | 10th April 2008
Oded Goldreich, Dana Ron

On Proximity Oblivious Testing

We initiate a systematic study of a special type of property testers.
These testers consist of repeating a basic test
for a number of times that depends on the proximity parameters,
whereas the basic test is oblivious of the proximity parameter.
We refer to such basic ... more >>>

TR00-056 | 20th July 2000
Oded Goldreich, Avi Wigderson

On Pseudorandomness with respect to Deterministic Observers.

In the theory of pseudorandomness, potential (uniform) observers
are modeled as probabilistic polynomial-time machines.
In fact many of the central results in
that theory are proven via probabilistic polynomial-time reductions.
In this paper we show that analogous deterministic reductions
are unlikely to hold. We conclude that randomness ... more >>>

TR15-094 | 10th June 2015
Eli Ben-Sasson, iddo Ben-Tov, Ivan Bjerre Damgard, Yuval Ishai, Noga Ron-Zewi

On Public Key Encryption from Noisy Codewords

Several well-known public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of inverting noisy linear encodings. These schemes are limited in that they either require the underlying field to grow with the security parameter, ... more >>>

TR21-123 | 25th August 2021
Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani

On public-coin zero-error randomized communication complexity

Revisions: 2

We prove that for every Boolean function, the public-coin zero-error randomized communication complexity and the deterministic communication complexity are polynomially equivalent.

more >>>

TR16-043 | 23rd February 2016
Mikolas Janota

On Q-Resolution and CDCL QBF Solving

Q-resolution and its variations provide the underlying proof
systems for the DPLL-based QBF solvers. While (long-distance) Q-resolution
models a conflict driven clause learning (CDCL) QBF solver, it is not
known whether the inverse is also true. This paper provides a negative
answer to this question. This contrasts with SAT solving, ... more >>>

TR21-115 | 6th August 2021
Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming

On quantum versus classical query complexity

Revisions: 2

Aaronson and Ambainis (STOC 2015, SICOMP 2018) claimed that the acceptance probability of every quantum algorithm that makes $q$ queries to an $N$-bit string can be estimated to within $\epsilon$ by a randomized classical algorithm of query complexity $O_q((N/\epsilon^2)^{1-1/2q})$. We describe a flaw in their argument but prove that the ... more >>>

TR05-007 | 15th December 2004

On Random High Density Subset Sums

In the Subset Sum problem, we are given n integers a_1,...,a_n
and a target number t, and are asked to find the subset of the
a_i's such that the sum is t. A version of the subset sum
problem is the Random Modular Subset Sum problem. In this version,
the ... more >>>

TR98-068 | 12th November 1998
Petr Savicky

On Random Orderings of Variables for Parity OBDDs

There are Boolean functions such that almost all orderings of
its variables yield an OBDD of polynomial size, but there are
also some exceptional orderings, for which the size is exponential.
We prove that for parity OBDDs the size for a random ordering
... more >>>

TR22-074 | 20th May 2022
Michael Saks, Rahul Santhanam

On Randomized Reductions to the Random Strings

We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants.

As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language $L$ that has a randomized ... more >>>

TR95-021 | 20th April 1995
Marek Karpinski, Rutger Verbeek

On Randomized Versus Deterministic Computation

In contrast to deterministic or nondeterministic computation, it is
a fundamental open problem in randomized computation how to separate
different randomized time classes (at this point we do not even know
how to separate linear randomized time from ${\mathcal O}(n^{\log n})$
randomized time) or how to ... more >>>

TR15-003 | 3rd January 2015
Oded Goldreich, Emanuele Viola, Avi Wigderson

On Randomness Extraction in AC0

We consider randomness extraction by AC0 circuits. The main parameter, $n$, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound $k=k(n)$, the seed length $r=r(n)$, the output length $m=m(n)$, and the (output) deviation bound $\epsilon=\epsilon(n)$.

For $k ... more >>> TR94-001 | 12th December 1994 Noam Nisan, Avi Wigderson On Rank vs. Communication Complexity This paper concerns the open problem of Lovasz and Saks regarding the relationship between the communication complexity of a boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems. more >>> TR01-044 | 14th June 2001 Pavel Pudlak On reducibility and symmetry of disjoint NP-pairs We consider some problems about pairs of disjoint$NP$sets. The theory of these sets with a natural concept of reducibility is, on the one hand, closely related to the theory of proof systems for propositional calculus, and, on the other, it resembles the theory of NP completeness. Furthermore, such more >>> TR19-141 | 22nd October 2019 Mark Braverman, Subhash Khot, Dor Minzer On Rich$2$-to-$1$Games We propose a variant of the$2$-to-$1$Games Conjecture that we call the Rich$2$-to-$1$Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the$2$-to-$1$Games Conjecture, we hope to understand ... more >>> TR12-133 | 21st October 2012 Noga Alon, Gil Cohen On Rigid Matrices and Subspace Polynomials Revisions: 1 We introduce a class of polynomials, which we call \emph{subspace polynomials} and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of ... more >>> TR13-109 | 11th August 2013 Oded Goldreich, Dana Ron On Sample-Based Testers Revisions: 1 The standard definition of property testing endows the tester with the ability to make arbitrary queries to elements'' of the tested object. In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object. While sample-based testers were defined by Goldreich, Goldwasser, and Ron ({\em JACM}\/ ... more >>> TR98-028 | 28th May 1998 Paul Beame, Faith Fich On Searching Sorted Lists: A Near-Optimal Lower Bound We obtain improved lower bounds for a class of static and dynamic data structure problems that includes several problems of searching sorted lists as special cases. These lower bounds nearly match the upper bounds given by recent striking improvements in searching algorithms given by Fredman and Willard's ... more >>> TR21-090 | 14th June 2021 Divesh Aggarwal, Eldon Chung, Maciej Obremski, Joao Ribeiro On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing Secret-sharing is one of the most basic and oldest primitives in cryptography, introduced by Shamir and Blakely in the 70s. It allows to strike a meaningful balance between availability and confidentiality of secret information. It has a host of applications most notably in threshold cryptography and multi-party computation. All known ... more >>> TR01-022 | 15th February 2001 Rahul Santhanam On segregators, separators and time versus space We give the first extension of the result due to Paul, Pippenger, Szemeredi and Trotter that deterministic linear time is distinct from nondeterministic linear time. We show that DTIME(n \sqrt(log^{*}(n))) \neq NTIME(n \sqrt(log^{*}(n))). We show that atleast one of the following statements holds: (1) P \neq L ... more >>> TR22-003 | 4th January 2022 Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere On Semi-Algebraic Proofs and Algorithms Revisions: 1 We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-$d$Sherali-Adams refutation of an unsatisfiable CNF formula$C$if and only if there is an$\varepsilon > 0$and a degree-$d$conical junta$J$such that$viol_C(x) - \varepsilon = J$, where$viol_C(x)$counts ... more >>> TR98-002 | 8th January 1998 Jayram S. Thathachar On Separating the Read-k-Times Branching Program Hierarchy We obtain an exponential separation between consecutive levels in the hierarchy of classes of functions computable by polynomial-size syntactic read-$k$-times branching programs, for {\em all\/}$k>0$, as conjectured by various authors~\cite{weg87,ss93,pon95b}. For every$k$, we exhibit two explicit functions that can be computed by linear-sized read-$(\kpluso)$-times branching programs but ... more >>> TR22-066 | 4th May 2022 Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy On sketching approximations for symmetric Boolean CSPs A Boolean maximum constraint satisfaction problem, Max-CSP$$(f)$$, is specified by a predicate $$f:\{-1,1\}^k\to\{0,1\}$$. An $$n$$-variable instance of Max-CSP$$(f)$$ consists of a list of constraints, each of which applies $$f$$ to $$k$$ distinct literals drawn from the $$n$$ variables. For $$k=2$$, Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios ... more >>> TR15-090 | 1st June 2015 Alexander Kozachinsky On Slepian--Wolf Theorem with Interaction Revisions: 1 In this paper we study interactive one-shot'' analogues of the classical Slepian-Wolf theorem. Alice receives a value of a random variable$X$, Bob receives a value of another random variable$Y$that is jointly distributed with$X$. Alice's goal is to transmit$X$to Bob (with some error probability$\varepsilon$). ... more >>> TR17-142 | 21st September 2017 Johan Håstad On small-depth Frege proofs for Tseitin for grids Revisions: 1 We prove that a small-depth Frege refutation of the Tseitin contradiction on the grid requires subexponential size. We conclude that polynomial size Frege refutations of the Tseitin contradiction must use formulas of almost logarithmic depth. more >>> TR22-070 | 8th May 2022 Pranav Bisht, Ilya Volkovich On Solving Sparse Polynomial Factorization Related Problems Revisions: 6 In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most$s$terms and individual degree bounded by$d$can itself have at most$s^{O(d^2\log ... more >>>

TR98-029 | 27th May 1998
Piotr Berman, Marek Karpinski

On Some Tighter Inapproximability Results

We prove a number of improved inaproximability results,
including the best up to date explicit approximation
thresholds for MIS problem of bounded degree, bounded
occurrences MAX-2SAT, and bounded degree Node Cover. We
prove also for the first time inapproximability of the
problem of Sorting by ... more >>>

TR98-065 | 6th November 1998
Piotr Berman, Marek Karpinski

On Some Tighter Inapproximability Results, Further Improvements

Improved inaproximability results are given, including the
best up to date explicit approximation thresholds for bounded
occurence satisfiability problems, like MAX-2SAT and E2-LIN-2,
and problems in bounded degree graphs, like MIS, Node Cover
and MAX CUT. We prove also for the first time inapproximability
more >>>

TR16-184 | 16th November 2016
Alexander Razborov

On Space and Depth in Resolution

We show that the total space in resolution, as well as in any other reasonable
proof system, is equal (up to a polynomial and $(\log n)^{O(1)}$ factors) to
the minimum refutation depth. In particular, all these variants of total space
are equivalent in this sense. The same conclusion holds for ... more >>>

TR03-023 | 12th February 2003
Anna Palbom

On Spanning Cacti and Asymmetric TSP

In an attempt to generalize Christofides algorithm for metric TSP to the asymmetric TSP with triangle inequality we have studied various properties of directed spanning cacti. In this paper we first observe that finding the TSP in a directed, weighted complete graph with triangle inequality is polynomial time equivalent to ... more >>>

TR13-070 | 4th May 2013
Iddo Tzameret

On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation

Revisions: 1

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

TR03-014 | 28th February 2003
Avrim Blum, Ke Yang

On Statistical Query Sampling and NMR Quantum Computing

We introduce a Statistical Query Sampling'' model, in which
the goal of an algorithm is to produce an element in a hidden set
$S\subseteq\bit^n$ with reasonable probability. The algorithm
gains information about $S$ through oracle calls (statistical
queries), where the algorithm submits a query function $g(\cdot)$

TR11-079 | 9th May 2011
Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

On Sums of Locally Testable Affine Invariant Properties

Affine-invariant properties are an abstract class of properties that generalize some
central algebraic ones, such as linearity and low-degree-ness, that have been
studied extensively in the context of property testing. Affine invariant properties
consider functions mapping a big field $\mathbb{F}_{q^n}$ to the subfield $\mathbb{F}_q$ and include all
properties that form ... more >>>

TR11-067 | 25th April 2011
Noga Alon, Amir Shpilka, Chris Umans

On Sunflowers and Matrix Multiplication

We present several variants of the sunflower conjecture of Erd\H{o}s and Rado and discuss the relations among them.

We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and Cohn et al. regarding possible approaches for obtaining fast matrix multiplication algorithms. ... more >>>

TR18-034 | 15th February 2018
Young Kun Ko

On Symmetric Parallel Repetition : Towards Equivalence of MAX-CUT and UG

Unique Games Conjecture (UGC), proposed by [Khot02], lies in the center of many inapproximability results. At the heart of UGC lies approximability of MAX-CUT, which is a special instance of Unique Game.[KhotKMO04, MosselOO05] showed that assuming Unique Games Conjecture, it is NP-hard to distinguish between MAX-CUT instance that has a ... more >>>

TR06-135 | 22nd October 2006
Jin-Yi Cai, Pinyan Lu

On Symmetric Signatures in Holographic Algorithms

The most intriguing aspect of the new theory of matchgate computations and holographic algorithms by Valiant~\cite{Valiant:Quantum} \cite{Valiant:Holographic} is that its reach and ultimate capability are wide open. The methodology produces unexpected polynomial time algorithms solving problems which seem to require exponential time. To sustain our belief in P $\not =$ ... more >>>

TR95-023 | 16th May 1995
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

On Syntactic versus Computational views of Approximability

We attempt to reconcile the two distinct views of approximation
classes: syntactic and computational.
Syntactic classes such as MAX SNP allow for clean complexity-theoretic
results and natural complete problems, while computational classes such
as APX allow us to work with problems whose approximability is
well-understood. Our results give a computational ... more >>>

TR16-140 | 9th September 2016
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

On SZK and PP

Revisions: 3

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>

TR97-016 | 29th April 1997
Manindra Agrawal, Eric Allender, Samir Datta

On TC^0, AC^0, and Arithmetic Circuits

Continuing a line of investigation that has studied the
function classes #P, #SAC^1, #L, and #NC^1, we study the
class of functions #AC^0. One way to define #AC^0 is as the
class of functions computed by constant-depth polynomial-size
arithmetic circuits of unbounded fan-in addition ... more >>>

TR13-166 | 28th November 2013
Arnab Bhattacharyya

On testing affine-invariant properties

An affine-invariant property over a finite field is a property of functions over F_p^n that is closed under all affine transformations of the domain. This class of properties includes such well-known beasts as low-degree polynomials, polynomials that nontrivially factor, and functions of low spectral norm. The last few years has ... more >>>

TR20-118 | 5th August 2020
Oded Goldreich

On Testing Asymmetry in the Bounded Degree Graph Model

Revisions: 4

We consider the problem of testing asymmetry in the bounded-degree graph model, where a graph is called asymmetric if the identity permutation is its only automorphism. Seeking to determine the query complexity of this testing problem, we provide partial results. Considering the special case of $n$-vertex graphs with connected components ... more >>>

TR13-089 | 17th June 2013
Abhishek Bhrushundi

On testing bent functions

Revisions: 1

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

TR10-061 | 10th April 2010
Oded Goldreich

On Testing Computability by Small Width OBDDs

Revisions: 2

We take another step in the study of the testability
of small-width OBDDs, initiated by Ron and Tsur (Random'09).
That is, we consider algorithms that,
given oracle access to a function $f:\{0,1\}^n\to\{0,1\}$,
need to determine whether $f$ can be implemented
by some restricted class of OBDDs or is far from
more >>>

TR00-020 | 27th March 2000
Oded Goldreich, Dana Ron

On Testing Expansion in Bounded-Degree Graphs

We consider testing graph expansion in the bounded-degree graph model.
Specifically, we refer to algorithms for testing whether the graph
has a second eigenvalue bounded above by a given threshold
or is far from any graph with such (or related) property.

We present a natural algorithm aimed ... more >>>

TR20-109 | 19th July 2020
Oded Goldreich

On Testing Hamiltonicity in the Bounded Degree Graph Model

Revisions: 2

We show that testing Hamiltonicity in the bounded-degree graph model requires a linear number of queries. This refers to both the path and the cycle versions of the problem, and similar results hold also for the directed analogues.
In addition, we present an alternative proof for the known fact that ... more >>>

TR14-145 | 4th November 2014
Yuan Li, Alexander Razborov, Benjamin Rossman

On the $AC^0$ Complexity of Subgraph Isomorphism

Let $P$ be a fixed graph (hereafter called a pattern''), and let
$Subgraph(P)$ denote the problem of deciding whether a given graph $G$
contains a subgraph isomorphic to $P$. We are interested in
$AC^0$-complexity of this problem, determined by the smallest possible exponent
$C(P)$ for which $Subgraph(P)$ possesses bounded-depth circuits ... more >>>

TR19-096 | 23rd July 2019

On the $\text{AC}^0[\oplus]$ complexity of Andreev's Problem

Andreev's Problem asks the following: Given an integer $d$ and a subset of $S \subseteq \mathbb{F}_q \times \mathbb{F}_q$, is there a polynomial $y = p(x)$ of degree at most $d$ such that for every $a \in \mathbb{F}_q$, $(a,p(a)) \in S$? We show an $\text{AC}^0[\oplus]$ lower bound for this problem.

... more >>>

TR22-030 | 18th February 2022
Aniruddha Biswas, Palash Sarkar

On The ''Majority is Least Stable'' Conjecture.

Revisions: 1

We show that the ''majority is least stable'' conjecture is true for $n=1$ and $3$ and false for all odd $n\geq 5$.

more >>>

TR21-141 | 28th September 2021
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization

Revisions: 1

We study a natural and quite general model of branch-and-bound algorithms. In this model, an algorithm attempts to minimize (or maximize) a function $f : D \to \mathbb{R}_{\geq 0}$ by making oracle queries to a heuristic $h_f$ satisfying
\[
\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot ... more >>>

TR03-085 | 28th November 2003
Ke Yang

On the (Im)possibility of Non-interactive Correlation Distillation

We study the problem of non-interactive correlation distillation
(NICD). Suppose Alice and Bob each has a string, denoted by
$A=a_0a_1\cdots a_{n-1}$ and $B=b_0b_1\cdots b_{n-1}$,
respectively. Furthermore, for every $k=0,1,...,n-1$, $(a_k,b_k)$ is
independently drawn from a distribution $\noise$, known as the noise
mode''. Alice and Bob wish to distill'' the correlation
more >>>

TR01-057 | 15th August 2001
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

On the (Im)possibility of Obfuscating Programs

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)
"compiler" that takes as input a program (or circuit) <b>P</b> and
produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>
yet is "unintelligible" in some sense. Obfuscators, if they exist,
would have a wide variety of cryptographic ... more >>>

TR03-015 | 20th March 2003
Yael Tauman Kalai

On the (In)security of the Fiat-Shamir Paradigm

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security ... more >>>

TR14-164 | 30th November 2014
Cody Murray, Ryan Williams

On the (Non) NP-Hardness of Computing Circuit Complexity

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function $f$ and a size parameter $k$, is the circuit complexity of $f$ at most $k$? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of ... more >>>

TR07-104 | 15th September 2007
Moses Charikar, Konstantin Makarychev, Yury Makarychev

On the Advantage over Random for Maximum Acyclic Subgraph

In this paper we present a new approximation algorithm for the MAX ACYCLIC SUBGRAPH problem. Given an instance where the maximum acyclic subgraph contains (1/2 + delta) fraction of all edges, our algorithm finds an acyclic subgraph with (1/2 + Omega(delta/ log n)) fraction of all edges.

more >>>

TR00-017 | 3rd March 2000
Valentin E. Brimkov, Stefan S. Dantchev

On the Algebraic Complexity of Integer Programming

In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem
(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors
\mathbb{N}$, when represented as polynomials over the real numbers. We show that as long as$c < n$it holds that deg$(f)=\Omega(n)$. As we can have deg$(f)=1$when$c=n$, our result shows a surprising ... more >>> TR11-002 | 9th January 2011 Gil Cohen, Amir Shpilka, Avishay Tal On the Degree of Univariate Polynomials Over the Integers We study the following problem raised by von zur Gathen and Roche: What is the minimal degree of a nonconstant polynomial$f:\{0,\ldots,n\}\to\{0,\ldots,m\}$? Clearly, when$m=n$the function$f(x)=x$has degree$1$. We prove that when$m=n-1$(i.e. the point$\{n\}$is not in the range), it must be the case ... more >>> TR12-157 | 12th November 2012 Andrej Bogdanov, Chin Ho Lee On the depth complexity of homomorphic encryption schemes Revisions: 2 We show that secure homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure encryption scheme cannot be implemented by constant depth, polynomial size circuits, i.e. in the class AC0. In contrast, we observe that certain previously studied encryption schemes (with quasipolynomial security) can ... more >>> TR00-081 | 5th September 2000 Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P neq NP. As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT using a version of the standard distribution ... more >>> TR00-044 | 26th June 2000 Tzvika Hartman, Ran Raz On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors Weak designs were defined by Raz, Reingold and Vadhan (1999) and are used in constructions of extractors. Roughly speaking, a weak design is a collection of subsets satisfying some near-disjointness properties. Constructions of weak designs with certain parameters are given in [RRV99]. These constructions are explicit in the sense that more >>> TR17-101 | 8th June 2017 Oded Goldreich On the doubly-efficient interactive proof systems of GKR Revisions: 1 We present a somewhat simpler variant of the doubly-efficient interactive proof systems of Goldwasser, Kalai, and Rothblum (JACM, 2015). Recall that these proof systems apply to log-space uniform sets in NC (or, more generally, to inputs that are acceptable by log-space uniform bounded-depth circuits, where the number of rounds in ... more >>> TR97-051 | 11th November 1997 Pekka Orponen On the Effect of Analog Noise in Discrete-Time Analog Computations We introduce a model for analog computation with discrete time in the presence of analog noise that is flexible enough to cover the most important concrete cases, such as noisy analog neural nets and networks of spiking neurons. This model subsumes the classical ... more >>> TR12-012 | 9th February 2012 Oded Goldreich On the Effect of the Proximity Parameter on Property Testers This note refers to the effect of the proximity parameter on the operation of (standard) property testers. Its bottom-line is that, except in pathological cases, the effect of the proximity parameter is restricted to determining the query complexity of the tester. The point is that, in non-pathological cases, the mapping ... more >>> TR08-064 | 11th July 2008 Or Meir On the Efficiency of Non-Uniform PCPP Verifiers We define a non-uniform model of PCPs of Proximity, and observe that in this model the non-uniform verifiers can always be made very efficient. Specifically, we show that any non-uniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity. more >>> TR97-001 | 8th January 1997 Marco Cesati, Luca Trevisan On the Efficiency of Polynomial Time Approximation Schemes A polynomial time approximation scheme (PTAS) for an optimization problem$A$is an algorithm that on input an instance of$A$and$\epsilon > 0$finds a$(1+\epsilon)$-approximate solution in time that is polynomial for each fixed$\epsilon$. Typical running times are$n^{O(1/\epsilon)}$or$2^{1/\epsilon^{O(1)}} ... more >>>

TR15-129 | 7th August 2015
Alex Samorodnitsky

On the entropy of a noisy function

Revisions: 1

Let $f$ be a nonnegative function on $\{0,1\}^n$. We upper bound the entropy of the image of $f$ under the noise operator with noise parameter $\epsilon$ by the average entropy of conditional expectations of $f$, given sets of roughly $(1-2\epsilon)^2 \cdot n$ variables.

As an application, we show that for ... more >>>

TR02-016 | 30th January 2002
Alina Beygelzimer, Mitsunori Ogihara

On the Enumerability of the Determinant and the Rank

We investigate the complexity of enumerative approximation of
two elementary problems in linear algebra, computing the rank
and the determinant of a matrix. In particular, we show that
if there exists an enumerator that, given a matrix, outputs a
list of constantly many numbers, one of which is guaranteed to
more >>>

TR05-061 | 15th June 2005
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

On the Error Parameter of Dispersers

Optimal dispersers have better dependence on the error than
optimal extractors. In this paper we give explicit disperser
constructions that beat the best possible extractors in some
parameters. Our constructions are not strong, but we show that
having such explicit strong constructions implies a solution
to the Ramsey graph construction ... more >>>

TR20-063 | 29th April 2020
Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

On the Existence of Algebraically Natural Proofs

Revisions: 1

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, and that satisfies the following properties:
* For every family {f_n} of polynomials in VP, where f_n is an n ... more >>>

TR98-001 | 17th December 1997
Detlef Sieling

On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization

Revisions: 1

The size of Ordered Binary Decision Diagrams (OBDDs) is
determined by the chosen variable ordering. A poor choice may cause an
OBDD to be too large to fit into the available memory. The decision
variant of the variable ordering problem is known to be
NP-complete. We strengthen this result by ... more >>>

TR98-021 | 7th April 1998
Shai Ben-David, Anna Gringauze.

On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic.

Revisions: 1

We investigate sufficient conditions for the existence of
optimal propositional proof systems (PPS).
We concentrate on conditions of the form CoNF = NF.
We introduce a purely combinatorial property of complexity classes
- the notions of {\em slim} vs. {\em fat} classes.
These notions partition the ... more >>>

TR22-120 | 24th August 2022
Jan Krajicek

On the existence of strong proof complexity generators

The working conjecture from K'04 that there is a proof complexity generator hard for all
proof systems can be equivalently formulated (for p-time generators) without a reference to proof complexity notions
as follows:
\begin{itemize}
\item There exist a p-time function $g$ extending each input by one bit such that its ... more >>>

TR05-112 | 12th September 2005
Eran Ofek

On the expansion of the giant component in percolated $(n,d,\lambda)$ graphs

Revisions: 1

Let $d \geq d_0$ be a sufficiently large constant. A $(n,d,c \sqrt{d})$ graph $G$ is a $d$ regular graph over $n$ vertices whose
second largest eigenvalue (in absolute value) is at most $c \sqrt{d}$. For any $0 < p < 1, ~G_p$ is the graph induced by
retaining each edge ... more >>>

TR15-141 | 26th August 2015
Pushkar Joglekar, Aravind N.R.

On the expressive power of read-once determinants

We introduce and study the notion of read-$k$ projections of the determinant: a polynomial $f \in \mathbb{F}[x_1, \ldots, x_n]$ is called a {\it read-$k$ projection of determinant} if $f=det(M)$, where entries of matrix $M$ are either field elements or variables such that each variable appears at most $k$ times in ... more >>>

TR16-056 | 8th April 2016
Shafi Goldwasser, Dhiraj Holden

On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances

We set out to study the impact of having access to correlated instances on the fine grained complexity of polynomial time problems, which have notoriously resisted improvement.
In particular, we show how to use a logarithmic number of auxiliary correlated instances to obtain $o(n^2)$ time algorithms for the longest common ... more >>>

TR19-045 | 19th February 2019
Jiawei Gao

On the Fine-grained Complexity of Least Weight Subsequence in Graphs

Revisions: 1

Least Weight Subsequence (LWS) is a type of highly sequential optimization problems with form $F(j) = \min_{i < j} [F(i) + c_{i,j}]$. They can be solved in quadratic time using dynamic programming, but it is not known whether these problems can be solved faster than $n^{2-o(1)}$ time. Surprisingly, each such ... more >>>

TR95-032 | 6th April 1995

On the Fourier spectrum of monotone functions

TR21-178 | 3rd December 2021
Srinivasan Arunachalam, Oded Regev, Penghui Yao

On the Gaussian surface area of spectrahedra

We show that for sufficiently large $n\geq 1$ and $d=C n^{3/4}$ for some universal constant $C>0$, a random spectrahedron with matrices drawn from Gaussian orthogonal ensemble has Gaussian surface area $\Theta(n^{1/8})$ with high probability.

more >>>

TR00-073 | 28th August 2000
Venkatesan Guruswami, Sanjeev Khanna

On the Hardness of 4-coloring a 3-colorable Graph

We give a new proof showing that it is NP-hard to color a 3-colorable
graph using just four colors. This result is already known (Khanna,
Linial, Safra 1992), but our proof is novel as it does not rely on
the PCP theorem, while the earlier one does. This ... more >>>

TR18-026 | 7th February 2018
Lijie Chen

On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product

Revisions: 1

In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets $A$ and $B$ of vectors, and the goal is to find $a \in A$ and $b \in B$ maximizing inner product $a \cdot b$. Max-IP is very basic and serves ... more >>>

TR03-020 | 27th March 2003
Elad Hazan, Shmuel Safra, Oded Schwartz

On the Hardness of Approximating k-Dimensional Matching

We study bounded degree graph problems, mainly the problem of
k-Dimensional Matching \emph{(k-DM)}, namely, the problem of
finding a maximal matching in a k-partite k-uniform balanced
hyper-graph. We prove that k-DM cannot be efficiently approximated
to within a factor of $O(\frac{k}{ \ln k})$ unless $P = NP$.
This ... more >>>

TR99-015 | 25th April 1999
Irit Dinur, S. Safra

On the hardness of approximating label cover

The label-cover problem was introduced in \cite{ABSS} and shown
there to be quasi-NP-hard to approximate to within a factor of
$2^{\log^{1-\delta}n}$ for any {\em constant} $\delta>0$. This
combinatorial graph problem has been utilized \cite{ABSS,GM,ABMP}
for showing hardness-of-approximation of numerous problems. We
present a direct combinatorial reduction from low
error-probability PCP ... more >>>

TR04-119 | 8th December 2004
Uriel Feige, Daniel Reichman

On The Hardness of Approximating Max-Satisfy

Max-Satisfy is the problem of finding an assignment that satisfies
the maximum number of equations in a system of linear equations
over $\mathbb{Q}$. We prove that unless NP$\subseteq$BPP there is no
polynomial time algorithm for the problem achieving an
approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number
of ... more >>>

TR20-146 | 24th September 2020
Scott Aaronson, Yosi Atia, Leonard Susskind

On the Hardness of Detecting Macroscopic Superpositions

When is decoherence "effectively irreversible"? Here we examine this central question of quantum foundations using the tools of quantum computational complexity. We prove that, if one had a quantum circuit to determine if a system was in an equal superposition of two orthogonal states (for example, the $|$Alive$\rangle$ and $|$Dead$\rangle$ ... more >>>

TR15-193 | 26th November 2015
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket

On the hardness of learning sparse parities

This work investigates the hardness of computing sparse solutions to systems of linear equations over $\mathbb{F}_2$. Consider the $k$-EvenSet problem: given a homogeneous system of linear equations over $\mathbb{F}_2$ on $n$ variables, decide if there exists a nonzero solution of Hamming weight at most $k$ (i.e. a $k$-sparse solution). While ... more >>>

TR05-113 | 12th September 2005
Bernhard Fuchs

On the Hardness of Range Assignment Problems

We investigate the computational hardness of the {\sc Connectivity},
the {\sc Strong Connectivity} and the {\sc Broadcast} type of Range
Assignment Problems in $\R^2$ and $\R^3$.
We present new reductions for the {\sc Connectivity} problem, which
are easily adapted to suit the other two problems. All reductions
are considerably simpler ... more >>>

TR19-123 | 12th September 2019
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell

On the Hardness of Robust Classification

It is becoming increasingly important to understand the vulnerability of machine learning models to adversarial attacks. In this paper we study the feasibility of robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of robust learnability requires polynomial sample complexity. ... more >>>

TR09-103 | 26th October 2009
Vikraman Arvind, Srikanth Srinivasan

On the Hardness of the Noncommutative Determinant

In this paper we study the computational complexity of computing the noncommutative determinant. We first consider the arithmetic circuit complexity of computing the noncommutative determinant polynomial. Then, more generally, we also examine the complexity of computing the determinant (as a function) over noncommutative domains. Our hardness results are summarized below:

... more >>>

TR06-067 | 12th April 2006
Heiner Ackermann, Heiko Röglin, Berthold Vöcking

On the Impact of Combinatorial Structure on Congestion Games

We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we investigate which properties of the strategy spaces of individual players ensure a polynomial convergence time. We show, if the strategy space ... more >>>

TR03-045 | 8th June 2003
Oded Goldreich, Asaf Nussboim

On the Implementation of Huge Random Objects

Revisions: 1

We initiate a general study of pseudo-random implementations
of huge random objects, and apply it to a few areas
in which random objects occur naturally.
For example, a random object being considered may be
a random connected graph, a random bounded-degree graph,
or a random error-correcting code with good ... more >>>

TR16-118 | 31st July 2016
Shachar Lovett, Jiapeng Zhang

On the impossibility of entropy reversal, and its application to zero-knowledge proofs

Zero knowledge proof systems have been widely studied in cryptography. In the statistical setting, two classes of proof systems studied are Statistical Zero Knowledge (SZK) and Non-Interactive Statistical Zero Knowledge (NISZK), where the difference is that in NISZK only very limited communication is allowed between the verifier and the prover. ... more >>>

TR15-209 | 29th December 2015
Eli Ben-Sasson, Gal Maor

On the information leakage of public-output protocols

In this paper three complexity measures are studied: (i) internal information, (ii) external information, and (iii) a measure called here "output information". Internal information (i) measures the counter-party privacy-loss inherent in a communication protocol. Similarly, the output information (iii) measures the reduction in input-privacy that is inherent when the output ... more >>>

TR01-040 | 16th May 2001

On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents")

We study a model of computation where executing a program on an input corresponds to calculating a product in a finite monoid. We show that in this model, the subsets of {0,1}^n that can be recognized by nilpotent groups have exponential cardinality.

Translator's note: This is a translation of the ... more >>>

TR05-028 | 12th February 2005
Elmar Böhler

On the Lattice of Clones Below the Polynomial Time Functions

A clone is a set of functions that is closed under generalized substitution.
The set FP of functions being computable deterministically in polynomial
time is such a clone. It is well-known that the set of subclones of every
clone forms a lattice. We study the lattice below FP, which ... more >>>

TR16-119 | 1st August 2016
Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov

On the Limits of Gate Elimination

Revisions: 1

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There has been a (very slow) progress in proving linear lower bounds with the latest record of ... more >>>

TR97-031 | 9th September 1997
Oded Goldreich

On the Limits of Non-Approximability of Lattice Problems

Revisions: 2

We show simple constant-round interactive proof systems for
problems capturing the approximability, to within a factor of $\sqrt{n}$,
of optimization problems in integer lattices; specifically,
the closest vector problem (CVP), and the shortest vector problem (SVP).
These interactive proofs are for the coNP direction'';
that is, ... more >>>

TR11-131 | 29th September 2011
Rahul Santhanam, Srikanth Srinivasan

On the Limits of Sparsification

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:
every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear
number of clauses. This lemma has subsequently played a key role in the study
of the exact complexity of the satisfiability problem. A natural question is
more >>>

TR20-070 | 4th May 2020

On the list recoverability of randomly punctured codes

Revisions: 1

We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound.
In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound.
It was previously known that there are Reed-Solomon codes that do not have this ... more >>>

TR10-003 | 6th January 2010
Venkatesan Guruswami, Johan Håstad, Swastik Kopparty

On the List-Decodability of Random Linear Codes

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon > 0$, we prove that with high probability a random subspace $C$ of
$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the
property that every Hamming ball of radius $pn$ has at most
$O(1/\varepsilon)$ codewords.

This ... more >>>

TR11-100 | 20th July 2011
Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin

On the Locality of Codeword Symbols

Consider a linear $[n,k,d]_q$ code $\mc{C}.$ We say that that $i$-th coordinate of $\mc{C}$ has locality $r,$ if the value at this coordinate can be recovered from accessing some other $r$ coordinates of $\mc{C}.$ Data storage applications require codes with small
redundancy, low locality for information coordinates, large distance, and ... more >>>

TR21-175 | 6th December 2021
Oded Goldreich

On the Locally Testable Code of Dinur et al. (2021)

Revisions: 1

This text provides a high-level description of the locally testable code constructed by Dinur, Evra, Livne, Lubotzky, and Mozes (ECCC, TR21-151).
In particular, the group theoretic aspects are abstracted as much as possible.

more >>>

TR16-003 | 2nd December 2015
Boris Brimkov, Illya Hicks

On the logspace shortest path problem

In this paper, we reduce the logspace shortest path problem to biconnected graphs; in particular, we present a logspace shortest path algorithm for general graphs which uses a logspace shortest path oracle for biconnected graphs. We also present a linear time logspace shortest path algorithm for graphs with bounded vertex ... more >>>

TR09-091 | 23rd September 2009
Thanh Minh Hoang

On the Matching Problem for Special Graph Classes

Revisions: 1

In the present paper we show some new complexity bounds for
the matching problem for special graph classes.
We show that for graphs with a polynomially bounded number
of nice cycles, the decision perfect matching problem is in
$SPL$, it is hard for $FewL$, and the construction ... more >>>

TR96-018 | 23rd February 1996

On the Message Complexity of Interactive Proof Systems

Revisions: 2

We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized a probabilitic machine
in time ... more >>>

TR10-178 | 17th November 2010
Amir Shpilka, Avishay Tal

On the Minimal Fourier Degree of Symmetric Boolean Functions

In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function.
Specifically, we prove that for every non-linear and symmetric $f:\{0,1\}^{k} \to \{0,1\}$ there exists a set $\emptyset\neq S\subset[k]$ such that $|S|=O(\Gamma(k)+\sqrt{k})$, and $\hat{f}(S) \neq 0$, where ... more >>>

TR14-167 | 11th November 2014
Beate Bollig

On the Minimization of (Complete) Ordered Binary Decision Diagrams

Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions.
Some applications work with a restricted variant called complete OBDDs
which is strongly related to nonuniform deterministic finite automata.
One of its complexity measures is the width which has been investigated
in several areas in computer science ... 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 >>>

TR08-056 | 22nd April 2008
Beate Bollig

On the OBDD complexity of the most significant bit of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been
in the focus of several complexity theoretical investigations.
Ordered binary decision diagrams (OBDDs) are one of the most common
dynamic data structures for boolean functions.
Among the many areas of application are verification, model checking,
computer-aided design, relational algebra, ... more >>>

TR12-175 | 13th December 2012
James Cook, Omid Etesami, Rachel Miller, Luca Trevisan

On the One-Way Function Candidate Proposed by Goldreich

Revisions: 1

A function $f$ mapping $n$-bit strings to $m$-bit strings can be constructed from a bipartite graph with $n$ vertices on the left and $m$ vertices on the right having right-degree $d$ together with a predicate $P:\{0,1\}^d\rightarrow\{0,1\}$. The vertices on the left correspond to the bits of the input to the ... more >>>

TR11-069 | 18th April 2011
Marius Zimand

On the optimal compression of sets in PSPACE

We show that if DTIME[2^{O(n)}] is not included in DSPACE}[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish ... more >>>

TR09-124 | 24th November 2009
Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi

On the Optimality of a Class of LP-based Algorithms

Revisions: 1

In this paper we will be concerned with a large class of packing
and covering problems which includes Vertex Cover and Independent Set.
Typically, for NP-hard problems among them, one can write an LP relaxation and
then round the solution. For instance, for Vertex Cover, one can obtain a
more >>>

TR15-127 | 7th August 2015
Stasys Jukna, Georg Schnitger

On the Optimality of Bellman--Ford--Moore Shortest Path Algorithm

Revisions: 1

We prove a general lower bound on the size of branching programs over any semiring of zero characteristic, including the (min,+) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum ... more >>>

TR17-186 | 29th November 2017
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi

On the Parameterized Complexity of Approximating Dominating Set

Revisions: 1

We study the parameterized complexity of approximating the $k$-Dominating Set (domset) problem where an integer $k$ and a graph $G$ on $n$ vertices are given as input, and the goal is to find a dominating set of size at most $F(k) \cdot k$ whenever the graph $G$ has a dominating ... more >>>

TR22-090 | 24th June 2022
Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.

More specifically, our previous work applied the well-known partial derivative method in a new setting, that of 'lopsided' set-multilinear polynomials. A ... more >>>

TR99-028 | 30th August 1999
Stefan Edelkamp, Ingo Wegener

On the performance of WEAK-HEAPSORT

Dutton presents a further HEAPSORT variant called
WEAK-HEAPSORT which also contains a new data structure for
priority queues. The sorting algorithm and the underlying
data structure ara analyzed showing that WEAK-HEAPSORT is
the best HEAPSORT variant and that it has a lot of nice
more >>>

TR12-101 | 10th August 2012
Oded Goldreich, Shafi Goldwasser, Dana Ron

On the possibilities and limitations of pseudodeterministic algorithms

We study the possibilities and limitations
of pseudodeterministic algorithms,
a notion put forward by Gat and Goldwasser (2011).
These are probabilistic algorithms that solve search problems
such that on each input, with high probability, they output
the same solution, which may be thought of as a canonical solution.
We consider ... more >>>

TR21-056 | 22nd April 2021
Yanyi Liu, Rafael Pass

On the Possibility of Basing Cryptography on $\EXP \neq \BPP$

Liu and Pass (FOCS'20) recently demonstrated an equivalence between the existence of one-way functions (OWFs) and mild average-case hardness of the time-bounded Kolmogorov complexity problem. In this work, we establish a similar equivalence but to a different form of time-bounded Kolmogorov Complexity---namely, Levin's notion of Kolmogorov Complexity---whose hardness is closely ... more >>>

TR21-012 | 9th February 2021
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

On the Power and Limitations of Branch and Cut

Revisions: 1

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical ... more >>>

TR00-054 | 5th May 2000
Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri

On the power assignment problem in radio networks

Given a finite set $S$ of points (i.e. the stations of a radio
network) on a $d$-dimensional Euclidean space and a positive integer
$1\le h \le |S|-1$, the \minrangeh{d} problem
consists of assigning transmission ranges to the stations so as
to minimize the total power consumption, provided ... more >>>

TR11-083 | 22nd May 2011
Eric Allender, Fengming Wang

On the power of algebraic branching programs of width two

We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several
settings.

more >>>

TR95-046 | 4th August 1995
Vince Grolmusz

On the Power of Circuits with Gates of Low L_1 Norms

We examine the power of Boolean functions with low L_1 norms in several
settings. In large part of the recent literature, the degree of a polynomial
which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function.
However, some functions ... more >>>

TR12-154 | 31st October 2012
Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah

On the Power of Conditional Samples in Distribution Testing

Revisions: 1

In this paper we define and examine the power of the conditional-sampling oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, ... more >>>

TR94-026 | 12th December 1994
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

On the Power of Different Types of Restricted Branching Programs

Almost the same types of restricted branching programs (or
binary decision diagrams BDDs) are considered in complexity
theory and in applications like hardware verification. These
models are read-once branching programs (free BDDs) and certain
types of oblivious branching programs (ordered and indexed BDDs
with k layers). The complexity of ... more >>>

TR00-077 | 24th August 2000
Till Tantau

On the Power of Extra Queries to Selective Languages

Revisions: 1

A language is \emph{selective} if there exists a
selection algorithm for it. Such an algorithm selects
from any two words one, which is an element of the
language whenever at least one of them is.
Restricting the complexity of selection algorithms
yields different \emph{selectivity classes} ... more >>>

TR14-045 | 7th April 2014
Mrinal Kumar, Shubhangi Saraf

On the power of homogeneous depth 4 arithmetic circuits

Revisions: 2

We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in $VP$. Our results hold for the {\it Iterated Matrix Multiplication} polynomial - in particular we show that any homogeneous depth 4 circuit computing the $(1,1)$ entry in the product of $n$ ... more >>>

TR09-024 | 26th February 2009
Raghav Kulkarni

On the Power of Isolation in Planar Structures

The purpose of this paper is to study the deterministic
{\em isolation} for certain structures in directed and undirected
planar graphs.
The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and
\cite{dkr08} isolate a perfect matching in ... more >>>

TR97-029 | 20th August 1997
Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

The study of the computational power of randomized
computations is one of the central tasks of complexity theory. The
main goal of this paper is the comparison of the power of Las Vegas
computation and deterministic respectively nondeterministic
computation. We investigate the power of Las Vegas computation for ... more >>>

TR99-007 | 10th March 1999
Juraj Hromkovic, Georg Schnitger

On the Power of Las Vegas II: Two-Way Finite Automata

The investigation of the computational power of randomized
computations is one of the central tasks of current complexity and
algorithm theory. This paper continues in the comparison of the computational
power of LasVegas computations with the computational power of deterministic
and nondeterministic ones. While for one-way ... more >>>

TR08-091 | 10th September 2008
Vitaly Feldman

On The Power of Membership Queries in Agnostic Learning

Revisions: 1

We study the properties of the agnostic learning framework of Haussler (1992)and Kearns, Schapire and Sellie (1992). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning?

Our results show that the answer is negative for distribution-independent agnostic learning and positive ... more >>>

TR13-137 | 29th September 2013
Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran

On the Power of Public-key Encryption in Secure Computation

We qualitatively separate semi-honest secure computation of non-trivial secure-function evaluation (SFE) functionalities from existence of key-agreement protocols.
Technically, we show the existence of an oracle (namely, PKE-oracle) relative to which key-agreement protocols exist; but it is useless for semi-honest secure realization of symmetric 2-party (deterministic finite) SFE functionalities, i.e. any ... more >>>

TR02-074 | 26th December 2002
Andrew Chi-Chih Yao

On the Power of Quantum Fingerprinting

In the simultaneous message model, two parties holding $n$-bit integers
$x,y$ send messages to a third party, the {\it referee}, enabling
him to compute a boolean function $f(x,y)$. Buhrman et al
[BCWW01] proved the remarkable result that, when $f$ is the
equality function, the referee can solve this problem by ... more >>>

TR12-129 | 9th October 2012
Iftach Haitner, Eran Omri, Hila Zarosim

On the Power of Random Oracles

Revisions: 3

In the random oracle model, the parties are given oracle access to a random member of
a (typically huge) function family, and are assumed to have unbounded computational power
(though they can only make a bounded number of oracle queries). This model provides powerful
properties that allow proving the security ... more >>>

TR95-054 | 24th November 1995
Farid Ablayev, Marek Karpinski

On the Power of Randomized Branching Programs

We define the notion of a randomized branching program in
the natural way similar to the definition of a randomized
circuit. We exhibit an explicit function $f_{n}$ for which
we prove that:
1) $f_{n}$ can be computed by polynomial size randomized
... more >>>

TR98-004 | 13th January 1998
Farid Ablayev, Marek Karpinski

On the Power of Randomized Ordered Branching Programs

We introduce a model of a {\em randomized branching program}
in a natural way similar to the definition of a randomized circuit.
We exhibit an explicit boolean function
$f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that:

1) $f_{n}$ can be computed by a polynomial size randomized
... more >>>

TR05-135 | 19th November 2005
Iftach Haitner, Danny Harnik, Omer Reingold

On the Power of the Randomized Iterate

We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm ... more >>>

TR10-009 | 13th January 2010
A. Pavan, Raghunath Tewari, N. V. Vinodchandran

On the Power of Unambiguity in Logspace

We report progress on the \NL\ vs \UL\ problem.
\begin{itemize}
\item[-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$.
\item[-] We investigate the complexity of min-uniqueness - a central
notion in studying the \NL\ vs \UL\ problem.
more >>>

TR14-050 | 21st March 2014
Edward Hirsch, Dmitry Sokolov

On the probabilistic closure of the loose unambiguous hierarchy

Revisions: 1

Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy $prUH_\bullet$ with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that ... more >>>

TR21-098 | 7th July 2021
Srikanth Srinivasan, S Venkitesh

On the Probabilistic Degree of an $n$-variate Boolean Function

Nisan and Szegedy (CC 1994) showed that any Boolean function $f:\{0,1\}^n\to\{0,1\}$ that depends on all its input variables, when represented as a real-valued multivariate polynomial $P(x_1,\ldots,x_n)$, has degree at least $\log n - O(\log \log n)$. This was improved to a tight $(\log n - O(1))$ bound by Chiarelli, Hatami ... 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 >>>

TR19-138 | 6th October 2019
Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

On the Probabilistic Degrees of Symmetric Boolean functions

The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$ such that there is a random polynomial $\mathbf{P}$ of degree at most $d$ that agrees with $f$ at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees ... more >>>

TR10-054 | 30th March 2010
Jan Krajicek

On the proof complexity of the Nisan-Wigderson generator based on a hard $NP \cap coNP$ function

Let $g$ be a map defined as the Nisan-Wigderson generator
but based on an $NP \cap coNP$-function $f$. Any string $b$ outside the range of
$g$ determines a propositional tautology $\tau(g)_b$ expressing this
fact. Razborov \cite{Raz03} has conjectured that if $f$ is hard on average for
P/poly then these ... more >>>

TR02-019 | 20th March 2002

On the proper learning of axis parallel concepts

We study the proper learnability of axis parallel concept classes
in the PAC learning model and in the exact learning model with
membership and equivalence queries. These classes include union of boxes,
DNF, decision trees and multivariate polynomials.

For the {\it constant} dimensional axis parallel concepts $C$
we ... more >>>

TR11-038 | 10th March 2011
Jiapeng Zhang

On the query complexity for Showing Dense Model

A theorem of Green, Tao, and Ziegler can be stated as follows: if $R$ is a pseudorandom distribution, and $D$ is a dense distribution of $R,$ then $D$ can be modeled as a distribution $M$ which is dense in uniform distribution such that $D$ and $M$ are indistinguishable. The reduction ... more >>>

TR05-082 | 3rd June 2005
Jorge Castro

On the Query Complexity of Quantum Learners

This paper introduces a framework for quantum exact learning via queries, the so-called quantum protocol. It is shown that usual protocols in the classical learning setting have quantum counterparts. A combinatorial notion, the general halving dimension, is also introduced. Given a quantum protocol and a target concept class, the general ... more >>>

TR14-031 | 16th February 2014
Joao Marques-Silva, Mikolas Janota

On the Query Complexity of Selecting Few Minimal Sets

Propositional Satisfiability (SAT) solvers are routinely used for
solving many function problems.

A natural question that has seldom been addressed is: what is the
best worst-case number of calls to a SAT solver for solving some
target function problem?

This paper develops tighter upper bounds on the query complexity of
more >>>

TR07-015 | 1st March 2007
Oded Goldreich, Or Sheffet

On the randomness complexity of property testing

We initiate a general study of the randomness complexity of
property testing, aimed at reducing the randomness complexity of
testers without (significantly) increasing their query complexity.
One concrete motovation for this study is provided by the
observation that the product of the randomness and query complexity
of a tester determine ... more >>>

TR22-048 | 4th April 2022
Hanlin Ren, Rahul Santhanam, Zhikun Wang

On the Range Avoidance Problem for Circuits

We consider the range avoidance problem (called Avoid): given the description of a circuit $C:\{0, 1\}^n \to \{0, 1\}^\ell$ (where $\ell > n$), find a string $y\in\{0, 1\}^\ell$ that is not in the range of $C$. This problem is complete for the class APEPP that corresponds to explicit constructions of ... more >>>

TR07-061 | 12th July 2007
Or Meir

On the Rectangle Method in proofs of Robustness of Tensor Products

Revisions: 4

Given linear two codes R,C, their tensor product $R \otimes C$
consists of all matrices whose rows are codewords of R and whose
columns are codewords of C. The product $R \otimes C$ is said to
be robust if for every matrix M that is far from $R \otimes C$
more >>>

TR10-036 | 8th March 2010
Amir Shpilka, Ilya Volkovich

On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors

We say that a polynomial $f(x_1,\ldots,x_n)$ is {\em indecomposable} if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The {\em polynomial decomposition} problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that ... more >>>

TR15-186 | 24th November 2015
Benny Applebaum, Pavel Raykov

On the Relationship between Statistical Zero-Knowledge and Statistical Randomized Encodings

\emph{Statistical Zero-knowledge proofs} (Goldwasser, Micali and Rackoff, SICOMP 1989) allow a computationally-unbounded server to convince a computationally-limited client that an input $x$ is in a language $\Pi$ without revealing any additional information about $x$ that the client cannot compute by herself. \emph{Randomized encoding} (RE) of functions (Ishai and Kushilevitz, FOCS ... more >>>

TR07-126 | 5th November 2007
Nathan Segerlind

On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs

We show that tree-like OBDD proofs of unsatisfiability require an exponential increase ($s \mapsto 2^{s^{\Omega(1)}}$) in proof size to simulate unrestricted resolution, and that unrestricted OBDD proofs of unsatisfiability require an almost-exponential increase ($s \mapsto 2^{ 2^{\left( \log s \right)^{\Omega(1)}}}$) in proof size to simulate $\Res{O(\log n)}$. The OBDD proof ... more >>>

TR10-045 | 15th March 2010
Jakob Nordström

On the Relative Strength of Pebbling and Resolution

Revisions: 1

The last decade has seen a revival of interest in pebble games in the
context of proof complexity. Pebbling has proven to be a useful tool
for studying resolution-based proof systems when comparing the
strength of different subsystems, showing bounds on proof space, and
establishing size-space trade-offs. The typical approach ... more >>>

TR04-109 | 15th November 2004
Neeraj Kayal, Nitin Saxena

On the Ring Isomorphism & Automorphism Problems

We study the complexity of the isomorphism and automorphism problems for finite rings with unity.

We show that both integer factorization and graph isomorphism reduce to the problem of counting
automorphisms of rings. The problem is shown to be in the complexity class $\AM \cap co\AM$
and hence ... more >>>

TR05-104 | 16th September 2005
Don Coppersmith, Atri Rudra

On the Robust Testability of Product of Codes

Ben-Sasson and Sudan in~\cite{BS04} asked if the following test
is robust for the tensor product of a code with another code--
pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that ... more >>>

TR14-062 | 22nd March 2014
Alexander Kozachinsky

On the role of private coins in unbounded-round Information Complexity

We prove a version of "Reversed Newman Theorem" in context of information complexity: every private-coin communication protocol with information complexity $I$ and communication complexity $C$ can be replaced by public-coin protocol with the same behavior so that it's information complexity does not exceed $O\left(\sqrt{IC}\right)$. This result holds for unbounded-round communication ... more >>>

TR15-137 | 22nd August 2015
Mohammad Bavarian, Dmytro Gavinsky, Tsuyoshi Ito

On the Role of Shared Randomness in Simultaneous Communication

Two parties wish to carry out certain distributed computational tasks, and they are given access to a source of correlated random bits.
It allows the parties to act in a correlated manner, which can be quite useful.
But what happens if the shared randomness is not perfect?

In this work, ... more >>>

TR99-005 | 21st December 1998
Michael Schmitt

On the Sample Complexity for Nonoverlapping Neural Networks

A neural network is said to be nonoverlapping if there is at most one
edge outgoing from each node. We investigate the number of examples
that a learning algorithm needs when using nonoverlapping neural
networks as hypotheses. We derive bounds for this sample complexity
in terms of the Vapnik-Chervonenkis dimension. ... more >>>

TR04-033 | 23rd January 2004
Michael Schmitt

On the sample complexity of learning for networks of spiking neurons with nonlinear synaptic interactions

We study networks of spiking neurons that use the timing of pulses
to encode information. Nonlinear interactions model the spatial
groupings of synapses on the dendrites and describe the computations
performed at local branches. We analyze the question of how many
examples these networks must ... more >>>

TR06-104 | 25th August 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

On the Sample Complexity of MAX-CUT

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest.

more >>>

TR00-045 | 23rd June 2000
Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

On the Security of Diffie--Hellman Bits

Boneh and Venkatesan have recently proposed a polynomial time
algorithm for recovering a hidden'' element $\alpha$ of a
finite field $\F_p$ of $p$ elements from rather short
strings of the most significant bits of the remainder
mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected
uniformly at ... more >>>

TR01-007 | 7th December 2000
Vered Rosen

On the Security of Modular Exponentiation

Assuming the inractability of factoring, we show that the
output of the exponentiation modulo a composite function
$f_{N,g}(x)=g^x\bmod N$ (where $N=P\cdot Q$) is pseudorandom,
even when its input is restricted to be half the size.
This result is equivalent to the simultaneous hardness of
the ... more >>>

TR02-049 | 4th August 2002
Oded Goldreich, Vered Rosen

On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators

Assuming the inractability of factoring, we show that
the output of the exponentiation modulo a composite function
$f_{N,g}(x)=g^x\bmod N$ (where $N=P\cdot Q$) is pseudorandom,
even when its input is restricted to be half the size.
This result is equivalent to the simultaneous hardness of the upper
half of the bits ... more >>>

TR97-027 | 29th April 1997
Johannes Merkle, Ralph Werchner

On the Security of Server aided RSA protocols

Revisions: 1

In this paper we investigate the security of the server aided
RSA protocols RSA-S1 and RSA-S1M proposed by Matsumoto, Kato and Imai
resp. Matsumoto, Imai, Laih and Yen. We prove lower bounds for the
complexity of attacks on these protocols and show that the bounds are
sharp by describing attacks ... more >>>

TR16-062 | 18th April 2016
Avishay Tal

On The Sensitivity Conjecture

The sensitivity of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ is the maximal number of neighbors a point in the Boolean hypercube has with different $f$-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the ... more >>>

TR16-132 | 23rd August 2016
Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker

On the Sensitivity Conjecture for Read-k Formulas

Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision ... more >>>

TR05-020 | 22nd November 2004
Sourav Chakraborty

On the Sensitivity of Cyclically-Invariant Boolean Functions

In this paper we construct a cyclically invariant Boolean function
whose sensitivity is $\Theta(n^{1/3})$. This result answers two
previously published questions. Tur\'an (1984) asked if any
Boolean function, invariant under some transitive group of
permutations, has sensitivity $\Omega(\sqrt{n})$. Kenyon and Kutin
(2004) asked whether for a nice'' function the product ... more >>>

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

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

Revisions: 1

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

TR15-181 | 13th November 2015
Neeraj Kayal, Chandan Saha, Sébastien Tavenas

On the size of homogeneous and of depth four formulas with low individual degree

Let $r \geq 1$ be an integer. Let us call a polynomial $f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}]$ as a multi-$r$-ic polynomial if the degree of $f$ with respect to any variable is at most $r$ (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output ... more >>>

TR14-170 | 10th December 2014
Yael Tauman Kalai, Ran Raz

On the Space Complexity of Linear Programming with Preprocessing

Revisions: 1

Linear Programs are abundant in practice, and tremendous effort has been put into designing efficient algorithms for such problems, resulting with very efficient (polynomial time) algorithms. A fundamental question is: what is the space complexity of Linear Programming?

It is widely believed that (even approximating) Linear Programming requires a large ... more >>>

TR12-150 | 1st November 2012
Michael Elberfeld, Christoph Stockhusen, Till Tantau

On the Space Complexity of Parameterized Problems

Revisions: 1

Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. ... more >>>

TR01-008 | 6th November 2000
Eldar Fischer

On the strength of comparisons in property testing

An $\epsilon$-test for a property $P$ of functions from
${\cal D}=\{1,\ldots,d\}$ to the positive integers is a randomized
algorithm, which makes queries on the value of an input function at
specified locations, and distinguishes with high probability between the
case of the function satisfying $P$, and the case that it ... more >>>

TR21-182 | 30th December 2021
Ilario Bonacina, Maria Luisa Bonet

On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems

The propositional proof system Sherali-Adams (SA) has polynomial-size proofs of the pigeonhole principle (PHP). Similarly, the Nullstellensatz (NS) proof system has polynomial size proofs of the bijective (i.e. both functional and onto) pigeonhole principle (ofPHP). We characterize the strength of these algebraic proof systems in terms of Boolean proof systems ... more >>>

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

On the Structure of Boolean Functions with Small Spectral Norm

Revisions: 1

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

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

2. ... more >>>

TR09-080 | 19th September 2009

On the Structure of Cubic and Quartic Polynomials

Revisions: 1

In this paper we study the structure of polynomials of degree three and four that have high bias or high Gowers norm, over arbitrary prime fields. In particular we obtain the following results. 1. We give a canonical representation for degree three or four polynomials that have a significant bias ... more >>>

TR21-173 | 5th December 2021

On the Structure of Learnability beyond P/poly

Motivated by the goal of showing stronger structural results about the complexity of learning, we study the learnability of strong concept classes beyond P/poly, such as PSPACE/poly and EXP/poly. We show the following:

1. (Unconditional Lower Bounds for Learning) Building on [KKO13], we prove unconditionally that BPE/poly cannot be weakly ... more >>>

TR15-101 | 15th June 2015
Patrick Scharpfenecker

On the structure of Solution-Graphs for Boolean Formulas

Revisions: 2

In this work we extend the study of solution graphs and prove that for boolean formulas in a class called CPSS, all connected components are partial cubes of small dimension, a statement which was proved only for some cases in [Schwerdtfeger 2013]. In contrast, we show that general Schaefer formulas ... more >>>

TR06-146 | 30th September 2006
Christoph Buchheim, Peter J Cameron, Taoyang Wu

On the Subgroup Distance Problem

We investigate the computational complexity of finding an element of
a permutation group~$H\subseteq S_n$ with a minimal distance to a
given~$\pi\in S_n$, for different metrics on~$S_n$. We assume
that~$H$ is given by a set of generators, such that the problem
cannot be solved in polynomial time ... more >>>

TR13-039 | 18th March 2013

On the sum of $L1$ influences

Revisions: 2

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

TR10-189 | 8th December 2010
Neeraj Kayal, Chandan Saha

On the Sum of Square Roots of Polynomials and related problems

The sum of square roots problem over integers is the task of deciding the sign of a nonzero sum, $S = \Sigma_{i=1}^{n}{\delta_i}$ . \sqrt{$a_i$}, where $\delta_i \in$ { +1, -1} and $a_i$'s are positive integers that are upper bounded by $N$ (say). A fundamental open question in numerical analysis and ... 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-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 >>>

TR06-018 | 8th February 2006
Jin-Yi Cai, Vinay Choudhary

On the Theory of Matchgate Computations

Valiant has proposed a new theory of algorithmic
computation based on perfect matchings and the Pfaffian.
We study the properties of {\it matchgates}---the basic
building blocks in this new theory. We give a set of
algebraic identities
which completely characterize these objects in terms of
the ... more >>>

TR99-021 | 8th April 1999
Igor E. Shparlinski

ON THE UNIFORMITY OF DISTRIBUTION OF A CERTAIN PSEUDO-RANDOM FUNCTION

We show that a pseudo-random number generator,
introduced recently by M. Naor and O. Reingold,
possess one more attractive and useful property.
Namely, it is proved that for almost all values of parameters it
produces a uniformly distributed sequence.
The proof is based on some recent bounds of exponential
more >>>

TR08-024 | 26th February 2008
Paul Beame, Trinh Huynh

On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

Revisions: 2

Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by ... more >>>

TR22-139 | 15th October 2022
Radu Curticapean, Nutan Limaye, Srikanth Srinivasan

On the VNP-hardness of Some Monomial Symmetric Polynomials

A polynomial $P\in F[x_1,\ldots,x_n]$ is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, ... more >>>

TR16-010 | 28th January 2016
Alexander Razborov

On the Width of Semi-Algebraic Proofs and Algorithms

In this paper we initiate the study of width in semi-algebraic proof systems
and various cut-based procedures in integer programming. We focus on two
important systems: Gomory-Chv\'atal cutting planes and
Lov\'asz-Schrijver lift-and-project procedures. We develop general methods for
proving width lower bounds and apply them to random $k$-CNFs and several ... 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 >>>

TR19-020 | 4th February 2019
Ludmila Glinskih, Dmitry Itsykson

On Tseitin formulas, read-once branching programs and treewidth

Revisions: 1

We show that any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on an $n\times n$ grid graph has size at least $2^{\Omega(n)}$. Then using the Excluded Grid Theorem by Robertson and Seymour we show that for arbitrary graph $G(V,E)$ any nondeterministic read-once branching program that computes ... more >>>

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

On Two-Level Poset Games

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

TR01-039 | 18th May 2001
Stasys Jukna, Stanislav Zak

On Uncertainty versus Size in Branching Programs

Revisions: 1

We propose an information-theoretic approach to proving lower
bounds on the size of branching programs. The argument is based on
Kraft-McMillan type inequalities for the average amount of
uncertainty about (or entropy of) a given input during the various
stages of computation. The uncertainty is measured by the average
more >>>

TR14-036 | 8th March 2014
Mikolas Janota, Leroy Chew, Olaf Beyersdorff

On Unification of QBF Resolution-Based Calculi

Revisions: 1

Several calculi for quantified Boolean formulas (QBFs) exist, but
relations between them are not yet fully understood.
This paper defines a novel calculus, which is resolution-based and
enables unification of the principal existing resolution-based QBF
calculi, namely Q-resolution, long-distance Q-resolution and the expansion-based
calculus ... more >>>

TR22-105 | 18th July 2022
Ilario Bonacina, Nicola Galesi, Massimo Lauria

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size.

more >>>

TR17-087 | 9th May 2017
Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar

On Weak-Space Complexity over Complex Numbers

Defining a feasible notion of space over the Blum-Shub-Smale (BSS) model of algebraic computation is a long standing open problem. In an attempt to define a right notion of space complexity for the BSS model, Naurois [CiE, 2007] introduced the notion of weak-space. We investigate the weak-space bounded computations and ... more >>>

TR21-161 | 16th November 2021
Shuichi Hirahara, Mikito Nanashima

On Worst-Case Learning in Relativized Heuristica

A PAC learning model involves two worst-case requirements: a learner must learn all functions in a class on all example distributions. However, basing the hardness of learning on NP-hardness has remained a key challenge for decades. In fact, recent progress in computational complexity suggests the possibility that a weaker assumption ... more >>>

TR05-015 | 27th January 2005
Andrej Bogdanov, Luca Trevisan

On Worst-Case to Average-Case Reductions for NP Problems

We show that if an NP-complete problem has a non-adaptive
self-corrector with respect to a samplable distribution then
coNP is contained in NP/poly and the polynomial
hierarchy collapses to the third level. Feigenbaum and
Fortnow (SICOMP 22:994-1005, 1993) show the same conclusion
under the stronger assumption that an
more >>>

TR95-050 | 15th October 1995
Oded Goldreich, Noam Nisan, Avi Wigderson

On Yao's XOR-Lemma

TR03-052 | 13th May 2003
Stanislav Busygin, Dmitrii V. Pasechnik

On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds

We show that for a graph G it is NP-hard to decide whether its independence number alpha(G) equals its clique partition number ~chi(G) even when some minimum clique partition of G is given. This implies that any alpha(G)-upper bound provably better than ~chi(G) is NP-hard to compute.

To establish this ... more >>>

TR00-063 | 13th July 2000
Peter Auer

On-line Learning of Rectangles in Noisy Environments

We investigate the implications of noise in the equivalence query
model. Besides some results for general target and hypotheses
classes, we prove bounds on the learning complexity of d-dimensional
discretized rectangles in the case where only rectangles are allowed
as hypotheses.
Our noise model assumes ... more >>>

TR00-071 | 14th July 2000
Peter Auer, Nicolo Cesa-Bianchi

On-line Learning with Malicious Noise and the Closure Algorithm

We investigate a variant of the on-line learning model for classes
of {0,1}-valued functions (concepts) in which the labels of a certain
amount of the input instances are corrupted by adversarial noise.
We propose an extension of a general learning strategy, known as
"Closure Algorithm", to this noise ... more >>>

TR00-001 | 14th January 2000
Piotr Berman, Moses Charikar, Marek Karpinski

On-Line Load Balancing for Related Machines

We consider the problem of scheduling permanent jobs on related machines
in an on-line fashion. We design a new algorithm that achieves the
competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic
version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant,
improving the previous competitive ratios ... more >>>

TR99-014 | 30th May 1999
Alexander Razborov, Nikolay Vereshchagin

One Property of Cross-Intersecting Families

Assume that A, B are finite families of n-element sets.
We prove that there is an element that simultaneously
belongs to at least |A|/2n sets
in A and to at least |B|/2n sets in B. We use this result to prove
that for any inconsistent DNF's F,G with OR ... more >>>

TR14-091 | 22nd July 2014
Ryan O'Donnell, A. C. Cem Say

One time-travelling bit is as good as logarithmically many

Revisions: 1

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On ... more >>>

TR12-091 | 16th July 2012
Abuzer Yakaryilmaz

One-counter verifiers for decidable languages

Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working ... more >>>

TR06-130 | 27th September 2006
Tanmoy Chakraborty, Samir Datta

One-input-face MPCVP is Hard for L, but in LogDCFL

A monotone planar circuit (MPC) is a Boolean circuit that can be
embedded in a plane, and that has only AND and OR
gates. Yang showed that the one-input-face
monotone planar circuit value problem (MPCVP) is in NC^2, and
Limaye et. al. improved the bound to ... more >>>

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

One-Round Multi-Party Communication Complexity of Distinguishing Sums

Revisions: 1

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

TR16-173 | 5th November 2016
Egor Klenin, Alexander Kozachinsky

One-sided error communication complexity of Gap Hamming Distance

Revisions: 2

Assume that Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$. Their goal is to output 0, if $x$ and $y$ are at least $L$-close in Hamming distance, and output 1, if $x$ and $y$ are at least $U$-far in Hamming distance, where ... more >>>

TR20-068 | 3rd May 2020
Oded Goldreich, Dana Ron

One-Sided Error Testing of Monomials and Affine Subspaces

Revisions: 2

We consider the query complexity of three versions of the problem of testing monomials and affine (and linear) subspaces with one-sided error, and obtain the following results:
\begin{itemize}
\item The general problem, in which the arity of the monomial (resp., co-dimension of the subspace) is not specified, has ... more >>>

TR20-103 | 9th July 2020
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

Revisions: 1

For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A ... more >>>

TR17-152 | 9th October 2017
Swagato Sanyal

One-way Communication and Non-adaptive Decision Tree

Let $f$ be a Boolean function on $n$-bits, and $\mathsf{IP}$ the inner-product function on $2b$ bits. Let $f^{\mathsf{IP}}:=f \circ \mathsf{IP}^n$ be the two party function obtained by composing $f$ with $\mathsf{IP}$. In this work we bound the one-way communication complexity of $f^{\IP}$ in terms of the non-adaptive query complexity of ... more >>>

TR21-065 | 5th May 2021
Nikhil Mande, Swagato Sanyal

One-way communication complexity and non-adaptive decision trees

Revisions: 1

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on ... more >>>

TR03-083 | 21st November 2003
Jan Arpe, Andreas Jakoby, Maciej Liskiewicz

One-Way Communication Complexity of Symmetric Boolean Functions

We study deterministic one-way communication complexity
of functions with Hankel communication matrices.
Some structural properties of such matrices are established
and applied to the one-way two-party communication complexity
of symmetric Boolean functions.
It is shown that the number of required communication bits
does not depend on ... more >>>

TR21-009 | 1st February 2021
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

One-way Functions and Partial MCSP

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>>

TR09-019 | 10th March 2009
Agrawal Manindra, Osamu Watanabe

One-Way Functions and the Isomorphism Conjecture

We study the Isomorphism Conjecture proposed by Berman and Hartmanis.
It states that all sets complete for NP under polynomial-time many-one
reductions are P-isomorphic to each other. From previous research
it has been widely believed that all NP-complete sets are reducible
each other by one-to-one and length-increasing polynomial-time
reductions, but ... more >>>

TR07-079 | 11th August 2007
Emanuele Viola, Avi Wigderson

One-way multi-party communication lower bound for pointer jumping with applications

In this paper we study the one-way multi-party communication model,
in which every party speaks exactly once in its turn. For every
fixed $k$, we prove a tight lower bound of
$\Omega{n^{1/(k-1)}}$ on the probabilistic communication
complexity of pointer jumping in a $k$-layered tree, where the
pointers of the $i$-th ... more >>>

TR09-097 | 2nd September 2009
Rakesh Mohanty, N. S. Narayanaswamy

Online Algorithms for Self-Organizing Sequential Search - A Survey

The main objective of this survey is to present the important theoretical and experimental results contributed till date in the area of online algorithms for the self organizing sequential search problem, also popularly known as the List Update Problem(LUP) in a chronological way. The survey includes competitiveness results of deterministic ... more >>>

TR10-016 | 22nd December 2009
Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking

Online Capacity Maximization in Wireless Networks

In this paper we study a dynamic version of capacity maximization in the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension $d$ arrive iteratively over time. When a new request arrives, an online algorithm needs to decide ... more >>>

TR05-161 | 13th December 2005
John Hitchcock

Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets

We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu (1995) and Lutz and Zhao (2000), and solves one ... more >>>

TR21-088 | 23rd June 2021
Oded Goldreich

Open Problems in Property Testing of Graphs

Revisions: 1

We briefly discuss a few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks. In the dense graph model, we discuss several open problems, including:

* Determining the complexity of testing triangle-freeness.
* Characterizing the class of properties ... more >>>

TR96-061 | 27th November 1996
Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener

Optimal attribute-efficient learning of disjunction, parity, and threshold functions

Decision trees are a very general computation model.
Here the problem is to identify a Boolean function $f$ out of a given
set of Boolean functions $F$ by asking for the value of $f$ at adaptively
chosen inputs.
For classes $F$ consisting of functions which may be obtained from one
more >>>

TR12-030 | 4th April 2012

Optimal bounds for monotonicity and Lipschitz testing over the hypercube

Revisions: 2

The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved
question in property testing. We are given query access to $f:\{0,1\}^n \mapsto R$
(for some ordered range $R$). The boolean hypercube ${\cal B}^n$ has a natural partial order, denoted by $\prec$ (defined by the product ... more >>>

TR10-025 | 24th February 2010
Alexander A. Sherstov

Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

The threshold degree of a function
$f\colon\{0,1\}^n\to\{-1,+1\}$ is the least degree of a
real polynomial $p$ with $f(x)\equiv\mathrm{sgn}\; p(x).$ We
prove that the intersection of two halfspaces on
$\{0,1\}^n$ has threshold degree $\Omega(n),$ which
matches the trivial upper bound and completely answers
a question due to Klivans (2002). The best ... more >>>

TR95-041 | 28th June 1995
Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim

Optimal Bounds for the Approximation of Boolean Functions and Some Applications

We prove an optimal bound on the Shannon function
$L(n,m,\epsilon)$ which describes the trade-off between the
circuit-size complexity and the degree of approximation; that is
$$L(n,m,\epsilon)\ =\ \Theta\left(\frac{m\epsilon^2}{\log(2 + m\epsilon^2)}\right)+O(n).$$
Our bound applies to any partial boolean function
and any ... more >>>

TR12-104 | 8th August 2012
Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman

Optimal Coding for Streaming Authentication and Interactive Communication

Revisions: 1

Error correction and message authentication are well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for error-correcting ... more >>>

TR22-056 | 18th April 2022
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $\delta$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/\delta) + O(1)$. In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that ... more >>>

TR10-106 | 17th June 2010
Yuichi Yoshida

Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP

Revisions: 1

Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it.
In this paper, we show that a ... more >>>

TR12-176 | 14th December 2012
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu

Optimal Cuts and Partitions in Tree Metrics in Polynomial Time

We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one dimensional geometric metric settings. Our method of solution could be also of independent interest ... more >>>

TR20-069 | 4th May 2020

Optimal Error Pseudodistributions for Read-Once Branching Programs

Revisions: 1

In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$ and width $w$ read-once branching programs with seed length $O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$ and error $\varepsilon$. It remains a central question to reduce the seed length to $O(\log (nw/\varepsilon))$, which would prove that $\mathbf{BPL}=\mathbf{L}$. However, there has ... more >>>

TR21-060 | 8th April 2021
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Optimal Error Resilience of Adaptive Message Exchange

We study the error resilience of the message exchange task: Two parties, each holding a private input, want to exchange their inputs. However, the channel connecting them is governed by an adversary that may corrupt a constant fraction of the transmissions. What is the maximum fraction of corruptions that still ... more >>>

TR06-032 | 25th February 2006
Vitaly Feldman

Optimal Hardness Results for Maximizing Agreements with Monomials

We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was ... more >>>

TR11-091 | 20th May 2011
Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal

Optimal heuristic algorithms for the image of an injective function

The existence of optimal algorithms is not known for any decision problem in NP$\setminus$P. We consider the problem of testing the membership in the image of an injective function. We construct optimal heuristic algorithms for this problem in both randomized and deterministic settings (a heuristic algorithm can err on a ... more >>>

TR12-158 | 14th November 2012

Optimal Hitting Sets for Combinatorial Shapes

We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2011). These generalize many well-studied classes of tests, including symmetric functions and combinatorial rectangles. Generalizing results of Linial, Luby, Saks, and Zuckerman (Combinatorica 1997) ... more >>>

TR20-130 | 30th August 2020
Amey Bhangale, Subhash Khot

Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

A seminal result of H\r{a}stad [J. ACM, 48(4):798–859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant ... more >>>

TR05-101 | 20th September 2005
Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of $\GW + \eps$, for all $\eps > 0$; here $\GW \approx .878567$ denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>>

TR19-151 | 5th November 2019
Per Austrin, Jonah Brown-Cohen, Johan Håstad

Optimal Inapproximability with Universal Factor Graphs

The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many ... more >>>

TR17-079 | 1st May 2017
Alexander A. Sherstov, Pei Wu

Optimal Interactive Coding for Insertions, Deletions, and Substitutions

Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... 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 >>>

TR09-130 | 1st December 2009
Ryan O'Donnell, YI WU, Yuan Zhou

Optimal lower bounds for locality sensitive hashing (except when $q$ is tiny)

We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in $\{0,1\}^d$ under the Hamming distance. Recall that $\mathcal{H}$ is said to be an $(r, cr, p, q)$-sensitive hash family if all pairs $x,y \in \{0,1\}^d$ with dist$(x,y) \leq r$ have probability at least $p$ ... more >>>

TR96-022 | 15th March 1996
Martin Sauerhoff, Ingo Wegener, Ralph Werchner

Optimal Ordered Binary Decision Diagrams for Tree-like Circuits

Many Boolean functions have short representations by OBDDs (ordered
binary decision diagrams) if appropriate variable orderings are used.
For tree-like circuits, which may contain EXOR-gates, it is proved
that some depth first traversal leads to an optimal variable ordering.
Moreover, an optimal variable ordering and the resulting OBDD
can ... more >>>

TR08-107 | 12th November 2008

Optimal Proof Systems and Complete Languages

We investigate the connection between optimal propositional
proof systems and complete languages for promise classes.
We prove that an optimal propositional proof system exists
if and only if there exists a propositional proof system
in which every promise class with the test set in co-NP
... more >>>

TR97-026 | 18th June 1997
Jochen Me\3ner, Jacobo Toran

Optimal proof systems for Propositional Logic and complete sets

A polynomial time computable function $h:\Sigma^*\to\Sigma^*$ whose range
is the set of tautologies in Propositional Logic (TAUT), is called
a proof system. Cook and Reckhow defined this concept
and in order to compare the relative strenth of different proof systems,
they considered the notion ... more >>>

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

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

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

TR20-172 | 13th November 2020
Venkatesan Guruswami, Chaoping Xing

Optimal rate list decoding over bounded alphabets using algebraic-geometric codes

We construct two classes of algebraic code families which are efficiently list decodable with small output list size from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The alphabet size depends only on $\epsilon$ and is nearly-optimal.

The ... more >>>

TR16-166 | 1st November 2016
Mark Braverman, Ran Gelles, Michael A. Yitayew

Optimal Resilience for Short-Circuit Noise in Formulas

Revisions: 1

We show an efficient method for converting a logic circuit of gates with fan-out 1 into an equivalent circuit that works even if some fraction of its gates are short-circuited, i.e., their output is short-circuited to one of their inputs. Our conversion can be applied to any circuit with fan-in ... more >>>

TR96-044 | 6th August 1996
Yosi Ben-Asher, Ilan Newman

Optimal Search in Trees

Revisions: 1

It is well known that the optimal solution for
searching in
a finite total order set is the binary search.
In the binary search we
divide the set into two halves'', by querying the middle
element, and continue the search on the suitable half.
What is the equivalent of binary ... more >>>

TR09-061 | 2nd July 2009
Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

Optimal Sherali-Adams Gaps from Pairwise Independence

This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by $P$ contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on $n$ variables cannot be approximated ... more >>>

TR20-140 | 14th September 2020
Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price

Optimal Testing of Discrete Distributions with High Probability

We study the problem of testing discrete distributions with a focus on the high probability regime.
Specifically, given samples from one or more discrete distributions, a property $\mathcal{P}$, and
parameters $0< \epsilon, \delta <1$, we want to distinguish {\em with probability at least $1-\delta$}
whether these distributions satisfy $\mathcal{P}$ ... more >>>

TR11-059 | 15th April 2011

Optimal testing of multivariate polynomials over small prime fields

We consider the problem of testing if a given function $f : \F_q^n \rightarrow \F_q$ is close to a $n$-variate degree $d$ polynomial over the finite field $\F_q$ of $q$ elements. The natural, low-query, test for this property would be to pick the smallest dimension $t = t_{q,d}\approx d/q$ such ... more >>>

TR09-086 | 2nd October 2009
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

Optimal testing of Reed-Muller codes

Revisions: 1

We consider the problem of testing if a given function
$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial
in $n$ variables, also known as the Reed-Muller testing problem.
Alon et al.~\cite{AKKLR} proposed and analyzed a natural
$2^{d+1}$-query test for this property and showed that it accepts
more >>>

TR04-049 | 15th June 2004
Piotr Berman, Marek Karpinski, Yakov Nekrich

Optimal Trade-Off for Merkle Tree Traversal

We prove upper and lower bounds for computing Merkle tree
traversals, and display optimal trade-offs between time
and space complexity of that problem.

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

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

TR19-153 | 6th November 2019
Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi

Optimally Resilient Codes for List-Decoding from Insertions and Deletions

Revisions: 1

We give a complete answer to the following basic question: What is the maximal fraction of deletions or insertions tolerable by $q$-ary list-decodable codes with non-vanishing information rate?''

This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results ... more >>>

TR01-069 | 24th October 2001
Robert Albin Legenstein

Optimizing the Layout of a Balanced Tree

Revisions: 1

It is shown that the total wire length of layouts of a
balanced binary tree on a 2-dimensional grid can be reduced by 33%
if one does not choose the obvious symmetric'' layout strategy.
Furthermore it is shown that the more efficient layout strategy that

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

TR95-015 | 6th February 1995
Bshouty, Cleve, Gavalda, Kannan, Tamon.

Oracles and queries that are sufficient for exact learning

We show what happen to learning if the learner can use NP-oracle.
A consequence of our results we show that
If NP\subset P/poly then the polynomial Hierarchy collapses to ZPP^NP

END_OF_DESCRIPTION

more >>>

TR05-040 | 13th April 2005
Scott Aaronson

Oracles Are Subtle But Not Malicious

Theoretical computer scientists have been debating the role of
oracles since the 1970's. This paper illustrates both that oracles
can give us nontrivial insights about the barrier problems in
circuit complexity, and that they need not prevent us from trying to
solve those problems.

First, we ... more >>>

TR98-039 | 14th July 1998
Christoph Meinel, Thorsten Theobald

Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey

Many problems in computer-aided design of highly integrated circuits
(CAD for VLSI) can be transformed to the task of manipulating objects
over finite domains. The efficiency of these operations depends
substantially on the chosen data structures. In the last years,
ordered binary decision diagrams (OBDDs) have ... more >>>

TR09-087 | 1st October 2009
Olga Tveretina, Carsten Sinz, Hans Zantema

Ordered Binary Decision Diagrams, Pigeonhole Formulas and Beyond

Groote and Zantema proved that a particular OBDD computation of the pigeonhole formula has an exponential
size and that limited OBDD derivations cannot simulate resolution polynomially. Here we show that any arbitrary OBDD Apply refutation of the pigeonhole formula has an exponential
size: we prove that the size of one ... more >>>

TR05-131 | 7th November 2005
Don Coppersmith, Lisa Fleischer, Atri Rudra

Ordering by weighted number of wins gives a good ranking for weighted tournaments

We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of $5$ if the weights satisfy \textit{probability constraints}
(for any pair of vertices $u$ and $v$, $w_{uv}+w_{vu}=1$). Special cases ... more >>>

TR16-053 | 6th April 2016
Jiawei Gao, Russell Impagliazzo

Orthogonal Vectors is hard for first-order properties on sparse graphs

Revisions: 3

Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until ... more >>>

TR11-132 | 2nd September 2011
Ludwig Staiger

Oscillation-free Chaitin $h$-random sequences

Revisions: 1

The present paper generalises results by Tadaki [12] and Calude et al. [1] on oscillation-free partially random infinite strings. Moreover, it shows that oscillation-free partial Chaitin randomness can be separated from scillation-free partial strong Martin-L\"of randomness by $\Pi_{1}^{0}$-definable sets of infinite strings.

more >>>

TR20-176 | 26th November 2020
Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona

Outcome Indistinguishability

Prediction algorithms assign numbers to individuals that are popularly understood as individual `probabilities''---what is the probability of 5-year survival after cancer diagnosis?---and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are ... more >>>

TR13-189 | 21st December 2013
Periklis Papakonstantinou, Dominik Scheder, Hao Song

Overlays and Limited Memory Communication Mode(l)s

We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models.

We introduce the notion of rectangle overlay complexity of a function $f: \{0,1\}^n\times \{0,1\}^n\to\{0,1\}$. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in ... more >>>

TR17-102 | 9th June 2017
Oded Goldreich

Overview of the doubly-efficient interactive proof systems of RRR

We provide an overview of the doubly-efficient interactive proof systems of Reingold, Rothblum, and Rothblum (STOC, 2016).
Recall that by their result, any set that is decidable in polynomial-time by an algorithm of space complexity $s(n)\leq n^{0.499}$, has a constant-round interactive proof system
in which the prover runs polynomial time ... more >>>

ISSN 1433-8092 | Imprint