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 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 >>> 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 >>> 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 >>> 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 >>> 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 >>> 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 >>> 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 Comments: 2 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 Vasken Bohossian, Jehoshua Bruck #### 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 #### On Non-Approximability for Quadratic Programs 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 read-once branching programs. 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 >>> 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 Constantinos Daskalakis, S. Matthew Weinberg #### 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 Hanna Mazzawi, Nader Bshouty #### 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 Prahladh Harsha, Srikanth Srinivasan #### 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). In this article we survey some of the applications that this 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 Nader Bshouty, Oded Goldreich #### 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 Vadim Lyubashevsky #### 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

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

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)$and receives ... more >>> 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 Comments: 1 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 Aditya Potukuchi #### 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$b \in {\bf R}^m$,$d \in {\bf R}^n$, decide if there is$x ... more >>>

TR21-071 | 16th May 2021
Samuel Epstein

#### On the Algorithmic Content of Quantum Measurements

We show that given a quantum measurement, for an overwhelming majority of pure states, no meaningful information is produced. This is independent of the number of outcomes of the quantum measurement. Due to conservation inequalities, such random noise cannot be processed into coherent data.

more >>>

TR11-019 | 5th February 2011
Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni

#### On the Approximability of a Geometric Set Cover Problem

Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case ... more >>>

TR96-015 | 12th December 1995
Edoardo Amaldi, Viggo Kann

#### On the approximability of some NP-hard minimization problems for linear systems

We investigate the computational complexity of two classes of
combinatorial optimization problems related to linear systems
and study the relationship between their approximability properties.
In the first class (MIN ULR) one wishes, given a possibly infeasible
system of linear relations, to find ... more >>>

TR96-046 | 27th August 1996
Luca Trevisan

#### On the Approximability of the Multi-dimensional Euclidean TSP

Revisions: 1

We consider the Traveling Salesperson Problem (TSP) restricted
to Euclidean spaces of dimension at most k(n), where n is the number of
cities. We are interested in the relation between the asymptotic growth of
k(n) and the approximability of the problem. We show that the problem is ... more >>>

TR06-031 | 27th February 2006
Li-Sha Huang, Shang-Hua Teng

#### On the Approximation and Smoothed Complexity of Leontief Market Equilibria

We show that the problem of finding an \epsilon-approximate Nash equilibrium af an n*n two-person game can be reduced to the computation of an (\epsilon/n)^2-approximate market equilibrium of a Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange ... more >>>

TR20-096 | 22nd June 2020
Igor Sergeev

#### On the asymptotic complexity of sorting

We investigate the number of pairwise comparisons sufficient to sort $n$ elements chosen from a linearly ordered set. This number is shown to be $\log_2(n!) + o(n)$ thus improving over the previously known upper bounds of the form $\log_2(n!) + \Theta(n)$. The new bound is achieved by the proposed group ... more >>>

TR09-014 | 7th February 2009
Soren Riis

#### On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity

We show that the asymptotic complexity of uniformly generated (expressible in First-Order (FO) logic) propositional tautologies for the Nullstellensatz proof system (NS) as well as for Polynomial Calculus, (PC) has four distinct types of asymptotic behavior over fields of finite characteristic. More precisely, based on some highly non-trivial work by ... more >>>

TR09-035 | 26th March 2009
Nicola Galesi, Massimo Lauria

#### On the Automatizability of Polynomial Calculus

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, unless W[P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov (SIAM J. Computing, 38(4), 2008).

more >>>

TR02-010 | 21st January 2002
Albert Atserias, Maria Luisa Bonet

#### On the Automatizability of Resolution and Related Propositional Proof Systems

Having good algorithms to verify tautologies as efficiently as possible
is of prime interest in different fields of computer science.
In this paper we present an algorithm for finding Resolution refutations
based on finding tree-like Res(k) refutations. The algorithm is based on
the one of Beame and Pitassi \cite{BP96} ... more >>>

TR02-056 | 19th September 2002
Todd Ebert, Wolfgang Merkle, Heribert Vollmer

#### On the Autoreducibility of Random Sequences

A binary sequence A=A(0)A(1).... is called i.o. Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either A(x) or a don't-know symbol on any given input x, and outputs A(x) for infinitely many x. If in addition ... more >>>

TR07-057 | 11th July 2007
Oded Goldreich

#### On the Average-Case Complexity of Property Testing

Revisions: 1

Motivated by a recent study of Zimand (22nd CCC, 2007),
we consider the average-case complexity of property testing
(focusing, for clarity, on testing properties of Boolean strings).
We make two observations:

1) In the context of average-case analysis with respect to
the uniform distribution (on all strings of ... more >>>

TR15-190 | 2nd November 2015
Esther Ezra, Shachar Lovett

#### On the Beck-Fiala Conjecture for Random Set Systems

Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems $(X,\Sigma)$, where each element $x \in X$ lies in $t$ randomly selected sets of $\Sigma$, where $t$ is an integer parameter. We provide new bounds in two regimes of parameters. We ... more >>>

TR12-093 | 1st July 2012
Charanjit Jutla, Vijay Kumar, Atri Rudra

#### On the Circuit Complexity of Composite Galois Field Transformations

We study the circuit complexity of linear transformations between Galois fields GF(2^{mn}) and their isomorphic composite fields GF((2^{m})^n). For such a transformation, we show a lower bound of \Omega(mn) on the number of gates required in any circuit consisting of constant-fan-in XOR gates, except for a class of transformations between ... more >>>

TR96-041 | 24th July 1996
Oded Goldreich, Avi Wigderson

#### On the Circuit Complexity of Perfect Hashing

We consider the size of circuits which perfectly hash
an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$
into $\bitset^m$.
We observe that, in general, the size of such circuits is
exponential in $2k-m$,
and provide a matching upper bound.

more >>>

TR13-073 | 14th May 2013
Oded Goldreich

#### On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing

Revisions: 2

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity
of property testing via communication complexity. They provided a restricted formulation of their methodology
(via simple combining operators'')
and also hinted towards a more general formulation, which we spell ... more >>>

TR16-055 | 11th April 2016
Tim Roughgarden, Omri Weinstein

#### On the Communication Complexity of Approximate Fixed Points

We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition
of two Lipschitz functions $g\circ f : [0,1]^n \to [0,1]^n$, where Alice holds $f$ and Bob holds $g$. We prove an
exponential (in $n$) lower bound on the deterministic ... more >>>

TR18-031 | 15th February 2018
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

#### On the Communication Complexity of Key-Agreement Protocols

Revisions: 2

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of ... more >>>

TR06-037 | 10th February 2006
Xi Chen, Xiaotie Deng

#### On the Complexity of 2D Discrete Fixed Point Problem

While the 3-dimensional analogue of the Sperner problem in the plane was known to be PPAD-complete, the complexity of the 2D-SPERNER itself is not known to be PPAD-complete or not. In this paper, we settle this open problem proposed by Papadimitriou~\cite{PAP90} fifteen years ago. This also allows us to derive ... more >>>

TR22-053 | 24th April 2022
Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

#### On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs

We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform TC^0 circuits
for division, matrix powering, and related problems, where the improvement is in terms of ... more >>>

TR09-048 | 29th May 2009
Parikshit Gopalan, Shachar Lovett, Amir Shpilka

#### On the Complexity of Boolean Functions in Different Characteristics

Every Boolean function on $n$ variables can be expressed as a unique multivariate polynomial modulo $p$ for every prime $p$. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree ... more >>>

TR11-004 | 10th January 2011

#### On the complexity of computational problems regarding distributions (a survey)

We consider two basic computational problems
regarding discrete probability distributions:
(1) approximating the statistical difference (aka variation distance)
between two given distributions,
and (2) approximating the entropy of a given distribution.
Both problems are considered in two different settings.
In the first setting the approximation algorithm
more >>>

TR19-036 | 5th March 2019
Pavel Hrubes

#### On the complexity of computing a random Boolean function over the reals

Revisions: 1

We say that a first-order formula $A(x_1,\dots,x_n)$ over $\mathbb{R}$ defines a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, if for every $x_1,\dots,x_n\in\{0,1\}$, $A(x_1,\dots,x_n)$ is true iff $f(x_1,\dots,x_n)=1$. We show that:

(i) every $f$ can be defined by a formula of size $O(n)$,
(ii) if $A$ is required to have at most $k\geq 1$ ... more >>>

TR00-086 | 26th September 2000
Michael Schmitt

#### On the Complexity of Computing and Learning with Multiplicative Neural Networks

In a great variety of neuron models neural inputs are
combined using the summing operation. We introduce the concept of
multiplicative neural networks which contain units that multiply
their inputs instead of summing them and, thus, allow inputs to
interact nonlinearly. The class of multiplicative networks
comprises such widely known ... more >>>

TR21-128 | 4th September 2021
Xiaotie Deng, Yuhao Li, David Mguni, Jun Wang, Yaodong Yang

#### On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games

Similar to the role of Markov decision processes in reinforcement learning, Markov Games (also called Stochastic Games)lay down the foundation for the study of multi-agent reinforcement learning (MARL) and sequential agent interactions. In this paper, we introduce the solution concept, approximate Markov Perfect Equilibrium (MPE), to finite-state Stochastic Games repeated ... more >>>

TR12-069 | 23rd March 2012
Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry

#### On the complexity of computing minimal unsatisfiable LTL formulas

We show that (1) the Minimal False QCNF search problem (MF-search) and
the Minimal Unsatisfiable LTL formula search problem (MU-search) are FPSPACE complete because of the very expressive power of QBF/LTL, (2) we extend the PSPACE-hardness of the MF decision problem to the MU decision problem. As a consequence, we ... more >>>

TR12-019 | 2nd March 2012
Eric Miles, Emanuele Viola

#### On the complexity of constructing pseudorandom functions (especially when they don't exist)

We study the complexity of black-box constructions of
pseudorandom functions (PRF) from one-way functions (OWF)
that are secure against non-uniform adversaries. We show
that if OWF do not exist, then given as an oracle any
(inefficient) hard-to-invert function, one can compute a
PRF in polynomial time with only $k(n)$ oracle ... more >>>

TR08-084 | 16th June 2008
Sanjeeb Dash

#### On the complexity of cutting plane proofs using split cuts

We prove a monotone interpolation property for split cuts which, together with results from Pudlak (1997), implies that cutting-plane proofs which use split cuts have exponential length in the worst case.
As split cuts are equivalent to mixed-integer rounding cuts and Gomory mixed-integer cuts, cutting-plane proofs using the above cuts ... more >>>

TR19-088 | 16th June 2019
Oded Goldreich

#### On the Complexity of Estimating the Effective Support Size

Revisions: 1

Loosely speaking, the effective support size of a distribution is the size of the support of a distribution that is close to it (in totally variation distance).
We study the complexity of estimating the effective support size of an unknown distribution when given samples of the distributions as well ... more >>>

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

#### On the Complexity of Fair Coin Flipping

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

TR99-038 | 27th August 1999
Peter Jonsson, Paolo Liberatore

#### On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

We study the computational complexity of an optimization
version of the constraint satisfaction problem: given a set $F$ of
constraint functions, an instance consists of a set of variables $V$
related by constraints chosen from $F$ and a natural number $k$. The
problem is to decide whether there exists a ... more >>>

TR00-050 | 13th July 2000
Peter Auer, Philip M. Long, Gerhard J. Woeginger

#### On the Complexity of Function Learning

The majority of results in computational learning theory
are concerned with concept learning, i.e. with the special
case of function learning for classes of functions
with range {0,1}. Much less is known about the theory of
learning functions with a larger range such
as N or R. In ... more >>>

TR11-052 | 4th April 2011
Fabian Wagner

#### On the Complexity of Group Isomorphism

The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one ... more >>>

TR01-076 | 24th October 2001
Robert Albin Legenstein

#### On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets

In this article we consider a basic problem in the layout of
VLSI-circuits, the channel-routing problem in the knock-knee mode.
We show that knock-knee channel routing with 3-terminal nets is
NP-complete and thereby settling a problem that was open for more
than a decade. In 1987, Sarrafzadeh showed that knock-knee ... more >>>

TR97-049 | 22nd October 1997
Michael Schmitt

#### On the Complexity of Learning for Spiking Neurons with Temporal Coding

Spiking neurons are models for the computational units in
biological neural systems where information is considered to be encoded
mainly in the temporal pattern of their activity. In a network of
spiking neurons a new set of parameters becomes relevant which has no
counterpart in traditional ... more >>>

TR02-012 | 3rd February 2002
Ran Raz

#### On the Complexity of Matrix Product

We prove a lower bound of $\Omega(m^2 \log m)$ for the size of
any arithmetic circuit for the product of two matrices,
over the real or complex numbers, as long as the circuit doesn't
use products with field elements of absolute value larger than 1
(where $m \times m$ is ... more >>>

TR15-004 | 4th January 2015
Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan

#### On the Complexity of Noncommutative Polynomial Factorization

In this paper we study the complexity of factorization of polynomials in the free noncommutative ring $\mathbb{F}\langle x_1,x_2,\ldots,x_n\rangle$ of polynomials over the field $\mathbb{F}$ and noncommuting variables $x_1,x_2,\ldots,x_n$. Our main results are the following.

Although $\mathbb{F}\langle x_1,\dots,x_n \rangle$ is not a unique factorization ring, we note that variable-disjoint factorization in ... more >>>

TR05-037 | 8th April 2005
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

#### On the Complexity of Numerical Analysis

We study two quite different approaches to understanding the complexity
of fundamental problems in numerical analysis. We show that both hinge
on the question of understanding the complexity of the following problem,
which we call PosSLP:
Given a division-free straight-line program
producing an integer N, decide whether N>0.
more >>>

TR13-041 | 14th March 2013
Igor Sergeev

#### On the complexity of parallel prefix circuits

It is shown that complexity of implementation of prefix sums of $m$ variables (i.e. functions $x_1 \cdot \ldots\cdot x_i$, $1\le i \le m$) by circuits of depth $\lceil \log_2 m \rceil$ in the case $m=2^n$ is exactly $$3.5\cdot2^n - (8.5+3.5(n \bmod 2))2^{\lfloor n/2\rfloor} + n + 5.$$ As a consequence, ... more >>>

TR01-054 | 12th April 2001
Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir

#### On the Complexity of Positional Sequencing by Hybridization

In sequencing by hybridization (SBH),
one has to reconstruct a sequence
from its $l$-long substrings.
SBH was proposed as
an alternative to
gel-based
DNA sequencing approaches, but in its original form the method
is
not competitive.
Positional SBH (PSBH) is a recently proposed
enhancement ... more >>>

TR14-148 | 8th November 2014
Vitaly Feldman, Will Perkins, Santosh Vempala

#### On the Complexity of Random Satisfiability Problems with Planted Solutions

Revisions: 1

We consider the problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment. This problem exhibits a large algorithmic gap: while the planted solution can always be identified given a formula with $O(n\log n)$ clauses, there are distributions over clauses for which the best known ... more >>>

TR06-100 | 17th July 2006
Meena Mahajan, Jayalal Sarma

#### On the Complexity of Rank and Rigidity

Given a matrix $M$ over a ring \Ringk, a target rank $r$ and a bound
$k$, we want to decide whether the rank of $M$ can be brought down to
below $r$ by changing at most $k$ entries of $M$. This is a decision
version of the well-studied notion of ... more >>>

TR04-001 | 11th December 2003
Lance Fortnow, Russell Impagliazzo, Chris Umans

#### On the complexity of succinct zero-sum games

We study the complexity of solving succinct zero-sum games,
i.e., the
games whose payoff matrix $M$ is given implicitly by a Boolean circuit
$C$ such that $M(i,j)=C(i,j)$. We complement the known $\EXP$-hardness
of computing the \emph{exact} value of a succinct zero-sum game by
several results on \emph{approximating} the value. (1) ... more >>>

TR12-067 | 6th May 2012
Xiaohui Bei, Ning Chen, Shengyu Zhang

#### On the Complexity of Trial and Error

Revisions: 1

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems with unknown inputs. Given a search problem with a hidden input, we are asked ... more >>>

TR14-034 | 3rd March 2014
Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram

#### On the complexity of trial and error for constraint satisfaction problems

In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if ... more >>>

TR21-124 | 17th August 2021

#### On the Complexity of Two-Party Differential Privacy

Revisions: 1

In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, ... more >>>

TR06-022 | 17th February 2006
Danny Harnik, Moni Naor

#### On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

We initiate the study of the compressibility of NP problems. We
consider NP problems that have long instances but relatively
short witnesses. The question is, can one efficiently compress an
instance and store a shorter representation that maintains the
information of whether the original input is in the language or
more >>>

TR08-059 | 20th May 2008
Farid Ablayev, Alexander Vasiliev

#### On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting

Revisions: 1

We develop quantum fingerprinting technique for constructing quantum
branching programs (QBPs), which are considered as circuits with an
ability to use classical bits as control variables.

We demonstrate our approach constructing optimal quantum ordered
binary decision diagram (QOBDD) for $MOD_m$ and $DMULT_n$ Boolean
functions. The construction of our technique also ... more >>>

TR16-034 | 7th March 2016
Mohamed El Halaby

#### On the Computational Complexity of MaxSAT

Revisions: 1

Given a Boolean formula in Conjunctive Normal Form (CNF) $\phi=S \cup H$, the MaxSAT (Maximum Satisfiability) problem asks for an assignment that satisfies the maximum number of clauses in $\phi$. Due to the good performance of current MaxSAT solvers, many real-life optimization problems such as scheduling can be solved efficiently ... more >>>

TR96-033 | 6th March 1996
Bernd Borchert, Desh Ranjan, Frank Stephan

#### On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

The paper analyzes in terms of polynomial time many-one reductions
the computational complexity of several natural equivalence
relations on Boolean functions which derive from replacing
variables by expressions. Most of these computational problems
turn out to be between co-NP and Sigma^p_2.

more >>>

TR04-116 | 18th November 2004
PERRET ludovic

#### On the computational complexity of some equivalence problems of polynomial systems of equations over finite fields

We study in this paper the computational complexity of some
equivalence relations on polynomial systems of equations over finite
fields. These problems are analyzed with respect to polynomial-time
many-one reductions (resp. Turing reductions, Levin reductions). In
particular, we show that some of these problems are between ... more >>>

TR99-027 | 17th July 1999
Marek Karpinski, Igor E. Shparlinski

#### On the computational hardness of testing square-freeness of sparse polynomials

We show that deciding square-freeness of a sparse univariate
polynomial over the integer and over the algebraic closure of a
finite field is NP-hard. We also discuss some related open

more >>>

TR94-023 | 12th December 1994
Matthias Krause, Pavel Pudlak

#### On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates

We investigate the computational power of depth two circuits
consisting of $MOD^r$--gates at the bottom and a threshold gate at
the top (for short, threshold--$MOD^r$ circuits) and circuits with
two levels of $MOD$ gates ($MOD^{p}$-$MOD^q$ circuits.) In particular, we
will show the following results

(i) For all prime numbers ... more >>>

TR98-038 | 9th July 1998
Marek Karpinski

#### On the Computational Power of Randomized Branching Programs

We survey some upper and lower bounds established recently on
the sizes of randomized branching programs computing explicit
boolean functions. In particular, we display boolean
functions on which randomized read-once ordered branching
programs are exponentially more powerful than deterministic
or nondeterministic read-$k$-times branching programs for ... more >>>

TR02-022 | 12th April 2002
Henry Markram

#### On the Computational Power of Recurrent Circuits of Spiking Neurons

Understanding the structure of real-time neural computation in
highly recurrent neural microcircuits that consist of complex
heterogeneous components has remained a serious challenge for
computational modeling. We propose here a new conceptual framework
that strongly differs from all previous approaches based on
computational models inspired ... more >>>

TR00-032 | 31st May 2000

#### On the Computational Power of Winner-Take-All

In this paper the computational power of a new type of gate is studied:
winner-take-all gates. This work is motivated by the fact that the cost
of implementing a winner-take-all gate in analog VLSI is about the same
as that of implementing a threshold gate.

We show that ... more >>>

TR12-045 | 22nd April 2012
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

#### On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

Revisions: 3

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables succinct verification of long proofs/computations in many cryptographic constructions, such as succinct arguments and proof-carrying data.

Despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these cryptographic constructions from being used in practice. This reflects ... more >>>

TR13-148 | 26th October 2013
Irit Dinur, Igor Shinkar

#### On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors

For $3 \leq q < Q$ we consider the $\text{ApproxColoring}(q,Q)$ problem of deciding for a given graph $G$ whether $\chi(G) \leq q$ or $\chi(G) \geq Q$. It was show in [DMR06] that the problem $\text{ApproxColoring}(q,Q)$ is NP-hard for $q=3,4$ and arbitrary large constant $Q$ under variants of the Unique Games ... more >>>

TR95-052 | 4th October 1995
Douglas R. Stinson

#### On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes

In this primarily expository
paper, we discuss the connections between two popular and useful
tools in theoretical computer science, namely,
universal hashing and pairwise
independent random variables; and classical combinatorial stuctures
such as error-correcting codes, balanced incomplete block designs,
difference matrices
... more >>>

TR09-143 | 22nd December 2009
Noam Livne

#### On the Construction of One-Way Functions from Average Case Hardness

In this paper we study the possibility of proving the existence of
one-way functions based on average case hardness. It is well-known
that if there exists a polynomial-time sampler that outputs
instance-solution pairs such that the distribution on the instances
is hard on average, then one-way functions exist. We study ... more >>>

TR97-005 | 17th February 1997
Moni Naor, Omer Reingold

#### On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

Luby and Rackoff showed a method for constructing a pseudo-random
permutation from a pseudo-random function. The method is based on
composing four (or three for weakened security) so called Feistel
permutations each of which requires the evaluation of a pseudo-random
function. We reduce somewhat the complexity ... more >>>

TR12-137 | 1st November 2012

#### On the correlation of parity and small-depth circuits

Revisions: 1

We prove that the correlation of a depth-$d$
unbounded fanin circuit of size $S$ with parity
of $n$ variables is at most $2^{-\Omega(n/(\log S)^{d-1})}$.

more >>>

TR15-001 | 2nd January 2015
Nir Bitansky, Omer Paneth, Alon Rosen

#### On the Cryptographic Hardness of Finding a Nash Equilibrium

Revisions: 1

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which ... more >>>

TR98-052 | 5th August 1998
Boris Hemkemeier, Frank Vallentin

#### On the decomposition of lattices

Revisions: 1

A lattice in euclidean space which is an orthogonal sum of
nontrivial sublattices is called decomposable. We present an algorithm
to construct a lattice's decomposition into indecomposable sublattices.
Similar methods are used to prove a covering theorem for generating
systems of lattices and to speed up variations of the LLL ... more >>>

TR06-142 | 26th October 2006
Olaf Beyersdorff

#### On the Deduction Theorem and Complete Disjoint NP-Pairs

In this paper we ask the question whether the extended Frege proof
system EF satisfies a weak version of the deduction theorem. We
prove that if this is the case, then complete disjoint NP-pairs
exist. On the other hand, if EF is an optimal proof system, ... more >>>

TR10-039 | 10th March 2010
Gil Cohen, Amir Shpilka

#### On the degree of symmetric functions on the Boolean cube

In this paper we study the degree of non-constant symmetric functions $f:\{0,1\}^n \to \{0,1,\ldots,c\}$, where $c\in \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 >>> 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
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 Oded Goldreich, Johan Håstad #### 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 Nader Bshouty, Lynn Burroughs #### 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 Comments: 1 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 Elad Haramaty, Amir Shpilka #### 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 Ninad Rajgopal, Rahul Santhanam #### 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 Arturs Backurs, Mohammad Bavarian #### 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 >>> 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 >>> 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 Revisions: 2 , Comments: 1 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 Comments: 1 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 Revisions: 3 , Comments: 1 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 C. Seshadhri, Deeparnab Chakrabarty #### 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 Eshan Chattopadhyay, Jyun-Jie Liao #### 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 Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan #### 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 Zenon Sadowski #### 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 Elad Haramaty, Amir Shpilka, Madhu Sudan #### 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 is presented in this article ... more >>> TR18-107 | 31st May 2018 Ran Raz, Avishay Tal #### Oracle Separation of BQP and PH We present a distribution$D$over inputs in$\{-1,1\}^{2N}$, such that: (1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time$O(\log N)$, that distinguishes between$D$and the uniform distribution with advantage$\Omega(1/\log N)$. (2) No Boolean circuit of$\mathrm{quasipoly}(N)$... more >>> 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 Contact: bshouty@cpsc.ucalgary.ca (Nader Bshouty) 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