Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > S:
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

S
TR07-030 | 29th March 2007
Kai-Min Chung, Omer Reingold, Salil Vadhan

#### S-T Connectivity on Digraphs with a Known Stationary Distribution

We present a deterministic logspace algorithm for solving s-t connectivity on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex $s$ has polynomial mixing time. This result generalizes the recent deterministic logspace ... more >>>

TR15-037 | 20th February 2015
Arnab Bhattacharyya, Palash Dey

#### Sample Complexity for Winner Prediction in Elections

Predicting the winner of an election is a favorite problem both for news media pundits and computational social choice theorists. Since it is often infeasible to elicit the preferences of all the voters in a typical prediction scenario, a common algorithm used for winner prediction is to run the election ... more >>>

TR17-133 | 7th September 2017
Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

#### Sample-Optimal Identity Testing with High Probability

We study the problem of testing identity against a given distribution (a.k.a. goodness-of-fit) with a focus on the high confidence regime. More precisely, given samples from an unknown distribution $p$ over $n$ elements, an explicitly given distribution $q$, and parameters $0< \epsilon, \delta < 1$, we wish to distinguish, {\em ... more >>>

TR19-059 | 18th April 2019
Rohit Agrawal

#### Samplers and extractors for unbounded functions

Revisions: 1

Blasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions $f:\{0,1\}^m \to \mathbb{R}$ such that $f(U_m)$ has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact ... more >>>

TR19-011 | 27th January 2019
Benny Applebaum, Eliran Kachlon

#### Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders

Revisions: 2

We initiate the study of the following hypergraph sampling problem: Sample a $d$-uniform hypergraph over $n$ vertices and $m$ hyperedges from some pseudorandom distribution $\mathcal{G}$ conditioned on not having some small predefined $t$-size hypergraph $H$ as a subgraph. The algorithm should run in $\mathrm{poly}(n)$-time even when the size of the ... more >>>

TR03-037 | 30th April 2003
Ziv Bar-Yossef

#### Sampling Lower Bounds via Information Theory

We present a novel technique, based on the Jensen-Shannon divergence
from information theory, to prove lower bounds on the query complexity
of sampling algorithms that approximate functions over arbitrary
domain and range. Unlike previous methods, our technique does not
use a reduction from a binary decision problem, but rather ... more >>>

TR18-060 | 6th April 2018
Emanuele Viola

#### Sampling lower bounds: boolean average-case and permutations

Revisions: 1

We show that for every small AC$^{0}$ circuit
$C:\{0,1\}^{\ell}\to\{0,1\}^{m}$ there exists a multiset $S$ of
$2^{m-m^{\Omega(1)}}$ restrictions that preserve the output distribution of
$C$ and moreover \emph{polarize min-entropy: }the restriction of $C$ to
any $r\in S$ either is constant or has polynomial min-entropy. This
structural result is then applied to ... more >>>

TR12-135 | 26th October 2012
Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf

#### Sampling-based proofs of almost-periodicity results and algorithmic applications

Revisions: 2

We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [Geom. Funct. Anal. 2010], whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and $L^p$-norm free) point of view, which allows for ... more >>>

TR21-044 | 14th February 2021
Alexander Kulikov, Nikita Slezkin

#### SAT-based Circuit Local Improvement

Finding exact circuit size is a notorious optimization problem in practice. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in blink of an eye, it may take more than a week to search for a circuit of size thirteen. One of the reasons of ... more >>>

TR15-099 | 12th June 2015
Ruiwen Chen

#### Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

We give a \#SAT algorithm for boolean formulas over arbitrary finite bases. Let $B_k$ be the basis composed of all boolean functions on at most $k$ inputs. For $B_k$-formulas on $n$ inputs of size $cn$, our algorithm runs in time $2^{n(1-\delta_{c,k})}$ for $\delta_{c,k} = c^{-O(c^2k2^k)}$. We also show the average-case ... more >>>

TR10-038 | 10th March 2010
Dieter van Melkebeek, Holger Dell

#### Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses

Revisions: 1

Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small ... more >>>

TR18-115 | 11th June 2018
Valentine Kabanets, Zhenjian Lu

#### Satisfiability and Derandomization for Small Polynomial Threshold Circuits

A polynomial threshold function (PTF) is defined as the sign of a polynomial $p\colon\bool^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth.

Satisfiability (#SAT). We give the first zero-error randomized algorithm ... more >>>

TR15-192 | 26th November 2015
Ruiwen Chen, Rahul Santhanam

#### Satisfiability on Mixed Instances

The study of the worst-case complexity of the Boolean Satisfiability (SAT) problem has seen considerable progress in recent years, for various types of instances including CNFs \cite{PPZ99, PPSZ05, Sch99, Sch05}, Boolean formulas \cite{San10} and constant-depth circuits \cite{IMP12}. We systematically investigate the complexity of solving {\it mixed} instances, where different parts ... more >>>

TR04-029 | 7th April 2004
John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo

#### Scaled dimension and the Kolmogorov complexity of Turing hard sets

Scaled dimension has been introduced by Hitchcock et al (2003) in order to quantitatively distinguish among classes such as SIZE(2^{a n}) and SIZE(2^{n^{a}}) that have trivial dimension and measure in ESPACE.

more >>>

TR06-047 | 11th February 2006
Maria Lopez-Valdes

#### Scaled Dimension of Individual Strings

We define a new discrete version of scaled dimension and we find
connections between the scaled dimension of a string and its Kolmogorov
complexity and predictability. We give a new characterization
of constructive scaled dimension by Kolmogorov complexity, and prove
a new result about scaled dimension and prediction.

more >>>

TR08-043 | 12th April 2008
Gábor Ivanyos, Marek Karpinski, Nitin Saxena

#### Schemes for Deterministic Polynomial Factoring

In this work we relate the deterministic
complexity of factoring polynomials (over
finite
fields) to certain combinatorial objects we
call
m-schemes. We extend the known conditional
deterministic subexponential time polynomial
factoring algorithm for finite fields to get an
underlying m-scheme. We demonstrate ... more >>>

TR19-172 | 28th November 2019
Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan

#### Schur Polynomials do not have small formulas if the Determinant doesn't!

Schur Polynomials are families of symmetric polynomials that have been
classically studied in Combinatorics and Algebra alike. They play a central
role in the study of Symmetric functions, in Representation theory [Sta99], in
Schubert calculus [LM10] as well as in Enumerative combinatorics [Gas96, Sta84,
Sta99]. In recent years, they have ... more >>>

TR15-203 | 13th December 2015
Scott Aaronson, Shalev Ben-David

#### Sculpting Quantum Speedups

Given a problem which is intractable for both quantum and classical algorithms, can we find a sub-problem for which quantum algorithms provide an exponential advantage? We refer to this problem as the "sculpting problem." In this work, we give a full characterization of sculptable functions in the query complexity setting. ... more >>>

TR19-140 | 7th October 2019
Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson

#### Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings.

Revisions: 1

We consider the problem of outputting succinct encodings of lists of generators for invariant rings. Mulmuley conjectured that there are always polynomial sized such encodings for all invariant rings. We provide simple examples that disprove this conjecture (under standard complexity assumptions).

more >>>

TR97-044 | 26th September 1997
David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum

#### Searching constant width mazes captures the AC^0 hierarchy

We show that searching a width k maze is complete for \Pi_k, i.e., for
the k'th level of the AC^0 hierarchy. Equivalently, st-connectivity
for width k grid graphs is complete for \Pi_k. As an application,
we show that there is a data structure solving dynamic st-connectivity
for constant ... more >>>

TR04-076 | 17th September 2004
Oliver Giel, Ingo Wegener

#### Searching Randomly for Maximum Matchings

Many real-world optimization problems in, e.g., engineering
or biology have the property that not much is known about
the function to be optimized. This excludes the application
of problem-specific algorithms. Simple randomized search
heuristics are then used with surprisingly good results. In
order to understand the working principles behind such
more >>>

TR11-082 | 20th May 2011
Miklos Ajtai

#### Secure Computation with Information Leaking to an Adversary

Assume that Alice is running a program $P$ on a RAM, and an adversary
Bob would like to get some information about the input or output of the
program. At each time, during the execution of $P$, Bob is able to see
the addresses of the memory cells involved in ... more >>>

TR15-010 | 19th January 2015
Maciej Li\'skiewicz, Rüdiger Reischuk, Ulrich Wölfel

#### Security Levels in Steganography -- Insecurity does not Imply Detectability

This paper takes a fresh look at security notions for steganography --
the art of encoding secret messages into unsuspicious covertexts
such that an adversary cannot distinguish the resulting stegotexts from original covertexts.
Stegosystems that fulfill the security notion used so far, however, are quite inefficient.
This ... more >>>

TR98-033 | 12th June 1998
C.P. Schnorr

#### Security of Allmost ALL Discrete Log Bits

Let G be a finite cyclic group with generator \alpha and with
an encoding so that multiplication is computable in polynomial time. We
study the security of bits of the discrete log x when given \exp_{\alpha}(x),
assuming that the exponentiation function \exp_{\alpha}(x) = \alpha^x is one-way.
... more >>>

TR00-041 | 19th May 2000
Igor E. Shparlinski

#### Security of Polynomial Transformations of the Diffie--Hellman Key

D. Boneh and R. Venkatesan have recently proposed an approach to proving
that a reasonably small portions of most significant bits of the
Diffie--Hellman key modulo a prime are as secure the the whole key. Some
further improvements and generalizations have been obtained by
I. M. Gonzales Vasco ... more >>>

TR00-040 | 19th May 2000
Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

#### Security of the Most Significant Bits of the Shamir Message Passing Scheme

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 random ... more >>>

TR20-161 | 5th November 2020
Gil Cohen, Dean Doron, Shahar Samocha

\to \{0,1\}$such that the xor of two independent copies ($D+D$) does not fool$f$, for any of the following choices: 1.$\epsilon = 2^{-\Omega(n)}$and$f$is in P/poly; 2.$\epsilon = 2^{-\Omega(n/\log n)}$and$f$is ... more >>> TR15-176 | 6th November 2015 Vikraman Arvind, Raja S #### Some Lower Bound Results for Set-Multilinear Arithmetic Computations Revisions: 1 In this paper, we study the structure of set-multilinear arithmetic circuits and set-multilinear branching programs with the aim of showing lower bound results. We define some natural restrictions of these models for which we are able to show lower bound results. Some of our results extend existing lower bounds, while ... more >>> TR17-002 | 6th January 2017 Frantisek Duris #### Some notes on two lower bound methods for communication complexity We compare two methods for proving lower bounds on standard two-party model of communication complexity, the Rank method and Fooling set method. We present bounds on the number of functions$f(x,y)$,$x,y\in\{0,1\}^n$, with rank of size$k$and fooling set of size at least k,$k\in [1,2^n]$. Using these bounds ... more >>> TR13-082 | 6th June 2013 Eldar Fischer, Yonatan Goldhirsh, Oded Lachish #### Some properties are not even partially testable For a property$P$and a sub-property$P'$, we say that$P$is$P'$-partially testable with$q$queries if there exists an algorithm that distinguishes, with high probability, inputs in$P'$from inputs$\epsilon$-far from$P$by using$q$queries. There are natural properties that require many queries to test, ... more >>> TR99-006 | 10th March 1999 Jin-Yi Cai #### Some Recent Progress on the Complexity of Lattice Problems We survey some recent developments in the study of the complexity of lattice problems. After a discussion of some problems on lattices which can be algorithmically solved efficiently, our main focus is the recent progress on complexity results of intractability. We will discuss Ajtai's worst-case/ average-case connections, NP-hardness and non-NP-hardness, more >>> TR06-048 | 9th April 2006 Jin-Yi Cai, Vinay Choudhary #### Some Results on Matchgates and Holographic Algorithms We establish a 1-1 correspondence between Valiant's character theory of matchgate/matchcircuit and his signature theory of planar-matchgate/matchgrid, thus unifying the two theories in expressibility. Previously we had established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Pl{\"u}cker identities. With this correspondence, we give a corresponding ... more >>> TR97-043 | 25th September 1997 Bruno Codenotti, Pavel Pudlak, Giovanni Resta #### Some structural properties of low rank matrices related to computational complexity Revisions: 1 , Comments: 1 We consider the conjecture stating that a matrix with rank$o(n)$and ones on the main diagonal must contain nonzero entries on a$2\times 2$submatrix with one entry on the main diagonal. We show that a slightly stronger conjecture implies that ... more >>> TR08-055 | 19th May 2008 Ryan O'Donnell #### Some Topics in Analysis of Boolean Functions This article accompanies a tutorial talk given at the 40th ACM STOC conference. In it, we give a brief introduction to Fourier analysis of boolean functions and then discuss some applications: Arrow?s Theorem and other ideas from the theory of Social Choice; the Bonami-Beckner Inequality as an extension of Chernoff/Hoeffding ... more >>> TR19-158 | 11th November 2019 Stasys Jukna, Hannes Seiwert #### Sorting Can Exponentially Speed Up Pure Dynamic Programming Many discrete minimization problems, including various versions of the shortest path problem, can be efficiently solved by dynamic programming (DP) algorithms that are pure'' in that they only perform basic operations, as$\min$,$\max$,$+$, but no conditional branchings via if-then-else in their recursion equations. It is known that any ... more >>> TR16-141 | 11th September 2016 Ryan O'Donnell #### SOS is not obviously automatizable, even approximately Revisions: 1 Suppose we want to minimize a polynomial$p(x) = p(x_1, \dots, x_n)$, subject to some polynomial constraints$q_1(x), \dots, q_m(x) \geq 0$, using the Sum-of-Squares (SOS) SDP hierarachy. Assume we are in the "explicitly bounded" ("Archimedean") case where the constraints include$x_i^2 \leq 1$for all$1 \leq i \leq ... more >>>

TR21-070 | 13th May 2021
Shuo Pang

#### SOS lower bound for exact planted clique

We prove a SOS degree lower bound for the planted clique problem on Erd{\"o}s-R\'enyi random graphs $G(n,1/2)$. The bound we get is degree $d=\Omega(\epsilon^2\log n/\log\log n)$ for clique size $\omega=n^{1/2-\epsilon}$, which is almost tight. This improves the result of \cite{barak2019nearly} on the soft'' version of the problem, where the family ... more >>>

TR07-127 | 22nd November 2007
Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

#### Sound 3-query PCPPs are Long

We initiate the study of the tradeoff between the {\em length} of a
probabilistically checkable proof of proximity (PCPP) and the
maximal {\em soundness} that can be guaranteed by a $3$-query
verifier with oracle access to the proof. Our main observation is
that a verifier limited to querying a short ... more >>>

TR12-132 | 21st October 2012
Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen

#### Space Complexity in Polynomial Calculus

During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving, and so research has mostly focused on weak systems ... more >>>

TR99-040 | 20th October 1999
Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

#### Space Complexity in Propositional Calculus

We study space complexity in the framework of
propositional proofs. We consider a natural model analogous to
Turing machines with a read-only input tape, and such
popular propositional proof systems as Resolution, Polynomial
Calculus and Frege systems. We propose two different space measures,
corresponding to the maximal number of bits, ... more >>>

TR10-079 | 28th April 2010
Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran

#### Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

We investigate the space complexity of certain perfect matching
problems over bipartite graphs embedded on surfaces of constant genus
(orientable or non-orientable). We show that the problems of deciding
whether such graphs have (1) a perfect matching or not and (2) a
unique perfect matching or not, are in the ... more >>>

TR01-031 | 5th April 2001
Eli Ben-Sasson, Nicola Galesi

#### Space Complexity of Random Formulae in Resolution

We study the space complexity of refuting unsatisfiable random $k$-CNFs in
the Resolution proof system. We prove that for any large enough $\Delta$,
with high probability a random $k$-CNF over $n$ variables and $\Delta n$
clauses requires resolution clause space of
$\Omega(n \cdot \Delta^{-\frac{1+\epsilon}{k-2-\epsilon}})$,
for any $0<\epsilon<1/2$. For constant $\Delta$, ... more >>>

TR14-008 | 20th January 2014
N. V. Vinodchandran

The graph reachability problem, the computational task of deciding whether there is a path between two given nodes in a graph is the canonical problem for studying space bounded computations. Three central open questions regarding the space complexity of the reachability problem over directed graphs are: (1) improving Savitch's $O(\log^2 ... more >>> TR06-103 | 5th July 2006 Oded Lachish, Ilan Newman, Asaf Shapira #### Space Complexity vs. Query Complexity Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input$x$, one wants to decide whether$x$satisfies the property or is far'' from satisfying it. The main focus of property testing is in identifying large families of properties that can be ... more >>> TR02-021 | 11th April 2002 Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk #### Space Efficient Algorithms for Directed Series-Parallel Graphs The subclass of directed series-parallel graphs plays an important role in computer science. Whether a given graph is series-parallel is a well studied problem in algorithmic graph theory, for which fast sequential and parallel algorithms have been developed in a sequence of papers. Also methods are known to solve ... more >>> TR07-134 | 14th December 2007 Jeff Kinne, Dieter van Melkebeek #### Space Hierarchy Results for Randomized and Other Semantic Models Revisions: 1 We prove space hierarchy and separation results for randomized and other semantic models of computation with advice. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems are the following. Let <i>s</i>(<i>n</i>) ... more >>> TR14-146 | 6th November 2014 Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan #### Space proof complexity for random$3$-CNFs via a$(2-\epsilon)$-Hall's Theorem We investigate the space complexity of refuting$3$-CNFs in Resolution and algebraic systems. No lower bound for refuting any family of$3$-CNFs was previously known for the total space in resolution or for the monomial space in algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a ... more >>> TR13-064 | 22nd April 2013 Anat Ganor, Ran Raz #### Space Pseudorandom Generators by Communication Complexity Lower Bounds Revisions: 1 In 1989, Babai, Nisan and Szegedy [BNS92] gave a construction of a pseudorandom generator for logspace, based on lower bounds for multiparty communication complexity. The seed length of their pseudorandom generator was$2^{\Theta(\sqrt n)}\,\,\,$, because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for ... more >>> TR10-154 | 8th October 2010 Derrick Stolee, N. V. Vinodchandran #### Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs We consider the reachability problem for a certain class of directed acyclic graphs embedded on surfaces. Let${\cal G}(m,g)$be the class of directed acyclic graphs with$m = m(n)$source vertices embedded on a surface (orientable or non-orientable) of genus$g = g(n)$. We give a log-space reduction that ... more >>> TR14-180 | 22nd December 2014 Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah #### Space-Efficient Approximations for Subset Sum SUBSET SUM is a well known NP-complete problem: given$t \in Z^{+}$and a set$S$of$m$positive integers, output YES if and only if there is a subset$S^\prime \subseteq S$such that the sum of all numbers in$S^\prime$equals$t$. The problem and its search ... more >>> TR10-110 | 14th July 2010 Ben Reichardt #### Span programs and quantum query algorithms Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semi-definite program that lower-bounds quantum query complexity. By giving a matching algorithm, we show that the general adversary lower ... more >>> TR12-049 | 27th April 2012 Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan #### Sparse affine-invariant linear codes are locally testable We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field${\mathbb{F}}_q$and an extension field${\mathbb{F}}_{q^n}$, a property is a set of functions mapping${\mathbb{F}}_{q^n}$to${\mathbb{F}}_q$. The property is said to be affine-invariant if it ... more >>> TR12-097 | 26th July 2012 Andrej Bogdanov, Siyao Guo #### Sparse extractor families for all the entropy We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, we seek extractors for essentially all the entropy without any assumption on the underlying distribution beyond a min-entropy requirement. We give two simple constructions of ... more >>> TR96-014 | 14th February 1996 Mitsunori Ogihara #### Sparse Hard Sets for P Yields Space-Efficient Algorithms In 1978, Hartmanis conjectured that there exist no sparse complete sets for P under logspace many-one reductions. In this paper, in support of the conjecture, it is shown that if P has sparse hard sets under logspace many-one reductions, then P is included in DPSPACE[log^2 n]. more >>> TR07-060 | 11th July 2007 Tali Kaufman, Madhu Sudan #### Sparse Random Linear Codes are Locally Decodable and Testable We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and ... more >>> TR10-163 | 3rd November 2010 Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin #### Sparse Selfreducible Sets and Nonuniform Lower Bounds It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in$EXP^{NP}$, or even ... more >>> TR98-027 | 15th April 1998 Vikraman Arvind, Jacobo Toran #### Sparse sets, approximable sets, and parallel queries to NP We relate the existence of disjunctive hard sets for NP to other well studied hypotheses in complexity theory showing that if an NP-complete set or a coNP-complete set is polynomial-time disjunctively reducible to a sparse set then FP$^{\rm NP}_{||}$= FP$^{\rm NP[log]}$. Using a similar argument we obtain also that ... more >>> TR18-044 | 5th March 2018 Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner #### Spatial Isolation Implies Zero Knowledge Even in a Quantum World Revisions: 1 Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, ... more >>> TR10-029 | 3rd March 2010 Alexandra Kolla #### Spectral Algorithms for Unique Games We present a new algorithm for Unique Games which is based on purely {\em spectral} techniques, in contrast to previous work in the area, which relies heavily on semidefinite programming (SDP). Given a highly satisfiable instance of Unique Games, our algorithm is able to recover a good assignment. The approximation ... more >>> TR20-026 | 25th February 2020 Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman #### Spectral Sparsification via Bounded-Independence Sampling Revisions: 1 We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph$G$on$n$vertices described by a binary string of length$N$, an integer$k\leq \log n$and an error parameter$\varepsilon > 0$, our algorithm runs in space$\tilde{O}(k\log (N\cdot ... more >>>

TR05-029 | 2nd March 2005
Frank Neumann, Marco Laumanns

#### Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization

Revisions: 1

We give faster approximation algorithms for the
generalization of two NP-hard spanning tree problems. First,
we investigate the problem of minimizing the degree of
minimum spanning forests. The task is to compute for each
number of connected components a minimum spanning forest
whose degree is as small as possible. Fischer
more >>>

TR06-083 | 16th May 2006
Nils Hebbinghaus, Benjamin Doerr, Frank Neumann

#### Speeding up Evolutionary Algorithms by Restricted Mutation Operators

We investigate the effect of restricting the mutation operator in
evolutionary algorithms with respect to the runtime behavior.
Considering the Eulerian cycle problem we present runtime bounds on
evolutionary algorithms with a restricted operator that are much
smaller than the best upper bounds for the ... more >>>

TR09-056 | 20th June 2009
Hunter Monroe

#### Speedup for Natural Problems and coNP?=NP

Revisions: 2

Informally, a language L has speedup if, for any Turing machine for L, there exists one that is better. Blum showed that there are computable languages that have almost-everywhere speedup. These languages were unnatural in that they were constructed for the sole purpose of having such speedup. We identify a ... more >>>

TR16-049 | 28th March 2016
Cynthia Dwork, Moni Naor, Guy Rothblum

#### Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems

We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).

In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of ... more >>>

TR17-151 | 8th October 2017
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

#### Stabbing Planes

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by
branching on an inequality and its "integer negation.'' That is, we can (nondeterministically ... more >>>

TR96-049 | 9th September 1996
Per Enflo, Meera Sitharam

#### Stable basis families and complexity lower bounds

--
Scalar product estimates have so far been used in
proving several unweighted threshold lower bounds.
We show that if a basis set of Boolean functions satisfies
certain weak stability conditions, then
scalar product estimates
yield lower bounds for the size of weighted thresholds
of these basis functions.
Stable ... more >>>

TR07-101 | 10th September 2007
Patrick Briest, Martin Hoefer, Piotr Krysta

#### Stackelberg Network Pricing Games

Revisions: 1

We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of m pricable edges in a graph. The other edges have a fixed cost. Based on the leader's decision one or more followers optimize a polynomial-time solvable combinatorial minimization ... more >>>

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

#### Static Data Structure Lower Bounds Imply Rigidity

Revisions: 2

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

TR12-064 | 10th May 2012
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao

#### Statistical Algorithms and a Lower Bound for Planted Clique

Revisions: 2

We develop a framework for proving lower bounds on computational problems over distributions, including optimization and unsupervised learning. Our framework is based on defining a restricted class of algorithms, called statistical algorithms, that instead of accessing samples from the input distribution can only obtain an estimate of the expectation ... more >>>

TR19-038 | 7th March 2019
Itay Berman, Akshay Degwekar, Ron D. Rothblum, Prashant Vasudevan

Revisions: 1

The polarization lemma for statistical distance ($\mathrm{SD}$), due to Sahai and Vadhan (JACM, 2003), is an efficient transformation taking as input a pair of circuits $(C_0,C_1)$ and an integer $k$ and outputting a new pair of circuits $(D_0,D_1)$ such that if $\mathrm{SD}(C_0,C_1)\geq\alpha$ then $\mathrm{SD}(D_0,D_1) \geq 1-2^{-k}$ and if $\mathrm{SD}(C_0,C_1) \leq ... more >>> TR16-177 | 11th November 2016 Ilias Diakonikolas, Daniel Kane, Alistair Stewart #### Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures Revisions: 1 We prove the first {\em Statistical Query lower bounds} for two fundamental high-dimensional learning problems involving Gaussian distributions: (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown mean Gaussian. In particular, we show a {\em super-polynomial gap} between the (information-theoretic) sample complexity and the ... more >>> TR06-075 | 19th June 2006 Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan #### Statistical Zero-Knowledge Arguments for NP from Any One-Way Function We show that every language in NP has a *statistical* zero-knowledge argument system under the (minimal) complexity assumption that one-way functions exist. In such protocols, even a computationally unbounded verifier cannot learn anything other than the fact that the assertion being proven is true, whereas a polynomial-time prover cannot convince ... more >>> TR04-115 | 1st December 2004 Iftach Haitner, Ronen Shaltiel #### Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions A statistical zero knowledge argument for NP is a cryptographic primitive that allows a polynomial-time prover to convince another polynomial-time verifier of the validity of an NP statement. It is guaranteed that even an infinitely powerful verifier does not learn any additional information but the validity of the claim. Naor ... more >>> TR17-043 | 3rd March 2017 Alexey Milovanov, Nikolay Vereshchagin #### Stochasticity in Algorithmic Statistics for Polynomial Time A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for$x$if it looks likely that$x$was drawn at random with respect to that distribution. In this paper, we ... more >>> TR11-080 | 11th May 2011 mohammad iftekhar husain, steve ko, Atri Rudra, steve uurtamo #### Storage Enforcement with Kolmogorov Complexity and List Decoding We consider the following problem that arises in outsourced storage: a user stores her data$x$on a remote server but wants to audit the server at some later point to make sure it actually did store$x$. The goal is to design a (randomized) verification protocol that has the ... more >>> TR19-185 | 6th December 2019 Greg Bodwin, Ofer Grossman #### Strategy-Stealing is Non-Constructive In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing. This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing ... more >>> TR10-094 | 17th May 2010 Ajesh Babu, Nutan Limaye, Girish Varma #### Streaming algorithms for some problems in log-space. In this paper, we give streaming algorithms for some problems which are known to be in deterministic log-space, when the number of passes made on the input is unbounded. If the input data is massive, the conventional deterministic log-space algorithms may not run efficiently. We study the complexity of the ... more >>> TR21-064 | 5th May 2021 Noah Singer, Madhu Sudan, Santhoshini Velusamy #### Streaming approximation resistance of every ordering CSP An ordering constraint satisfaction problem (OCSP) is given by a positive integer$k$and a constraint predicate$\Pi$mapping permutations on$\{1,\ldots,k\}$to$\{0,1\}$. Given an instance of OCSP$(\Pi)$on$n$variables and$m$constraints, the goal is to find an ordering of the$n$variables that maximizes the number ... more >>> TR12-183 | 25th December 2012 András Salamon #### Streaming bounds from difference ramification Revisions: 1 , Comments: 1 In graph streaming a graph with$n$vertices and$m$edges is presented as a read-once stream of edges. We obtain an$\Omega(n \log n)$lower bound on the space required to decide graph connectivity. This improves the known bounds of$\Omega(n)$for undirected and$\Omega(m)$for sparse directed graphs. ... more >>> TR16-150 | 23rd September 2016 Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez #### Streaming Communication Protocols We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that depends on inputs that are distributed to each agent. The inputs arrive as data streams and each agent has a bounded memory. Agents ... more >>> TR12-128 | 21st September 2012 Nathanaël François, Frederic Magniez #### Streaming Complexity of Checking Priority Queues Revisions: 1 This work is in the line of designing efficient checkers for testing the reliability of some massive data structures. Given a sequential access to the insert/extract operations on such a structure, one would like to decide, a posteriori only, if it corresponds to the evolution of a reliable structure. In ... more >>> TR11-105 | 22nd July 2011 Graham Cormode, Michael Mitzenmacher, Justin Thaler #### Streaming Graph Computations with a Helpful Advisor Revisions: 1 Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a ... more >>> TR15-104 | 13th May 2015 Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont #### Streaming Property Testing of Visibly Pushdown Languages Revisions: 2 In the context of language recognition, we demonstrate the superiority of streaming property testers against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum et al, a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs ... more >>> TR20-100 | 6th July 2020 Amit Chakrabarti, Prantar Ghosh, Justin Thaler #### Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that ... more >>> TR19-101 | 24th July 2019 Amit Chakrabarti, Prantar Ghosh #### Streaming Verification of Graph Computations via Graph Structure We give new algorithms in the annotated data streaming setting---also known as verifiable data stream computation---for certain graph problems. This setting is meant to model outsourced computation, where a space-bounded verifier limited to sequential data access seeks to overcome its computational limitations by engaging a powerful prover, without needing to ... more >>> TR15-058 | 1st April 2015 Peng Cui #### Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion In this paper, the author puts forward a variation of Feige's Hypothesis, which claims that it is hard on average refuting Unbalanced Max 3-XOR under biased assignments on a natural distribution. Under this hypothesis, the author strengthens the previous known hardness for approximating Minimum Unique Game,$5/4-\epsilon$, by proving that ... more >>> TR02-026 | 7th April 2002 Boaz Barak, Yehuda Lindell #### Strict Polynomial-time in Simulation and Extraction Revisions: 2 The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time which is only polynomial {\em on the average} (i.e., ... more >>> TR08-035 | 18th February 2008 James I. Lathrop, Jack H. Lutz, Scott M. Summers #### Strict Self-Assembly of Discrete Sierpinski Triangles Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely ... more >>> TR09-095 | 25th September 2009 Swapnoneel Roy #### STRIP EXCHANGING IS HARD Revisions: 1 The sorting by strip exchanges (aka strip exchanging) problem is motivated by applications in optical character recognition and genome rearrangement analysis. While a couple of approximation algorithms have been designed for the problem, nothing has been known about its computational hardness till date. In this work, we show that the ... more >>> TR06-112 | 22nd August 2006 Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang #### Strip Packing vs. Bin Packing In this paper we establish a general algorithmic framework between bin packing and strip packing, with which we achieve the same asymptotic bounds by applying bin packing algorithms to strip packing. More precisely we obtain the following results: (1) Any offline bin packing algorithm can be applied to strip packing ... more >>> TR20-036 | 9th March 2020 Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl #### Strong (D)QBF Dependency Schemes via Tautology-free Resolution Paths We suggest a general framework to study dependency schemes for dependency quantified Boolean formulas (DQBF). As our main contribution, we exhibit a new tautology-free DQBF dependency scheme that generalises the reflexive resolution path dependency scheme. We establish soundness of the tautology-free scheme, implying that it can be used in any ... more >>> TR20-010 | 12th February 2020 Lijie Chen, Hanlin Ren #### Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization Revisions: 1 We prove that for all constants a, NQP = NTIME[n^{polylog(n)}] cannot be (1/2 + 2^{-log^a n})-approximated by 2^{log^a n}-size ACC^0 of THR circuits (ACC^0 circuits with a bottom layer of THR gates). Previously, it was even open whether E^NP can be (1/2+1/sqrt{n})-approximated by AC^0[2] circuits. As a straightforward application, ... more >>> TR11-040 | 22nd March 2011 Alexander A. Sherstov #### Strong Direct Product Theorems for Quantum Communication and Query Complexity A strong direct product theorem (SDPT) states that solving$n$instances of a problem requires$\Omega(n)$times the resources for a single instance, even to achieve success probability$2^{-\Omega(n)}.$We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by ... more >>> TR16-002 | 18th January 2016 Ryan Williams #### Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit$C(x_1,\ldots,x_n)$of size$s$and degree$d$over a field${\mathbb F}$, and any inputs$a_1,\ldots,a_K \in {\mathbb F}^n$,$\bullet$the Prover sends the Verifier the values$C(a_1), \ldots, C(a_K) \in {\mathbb F}$and ... more >>> TR16-111 | 20th July 2016 Amit Chakrabarti, Sagar Kale #### Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics We develop a paradigm for studying multi-player deterministic communication, based on a novel combinatorial concept that we call a {\em strong fooling set}. Our paradigm leads to optimal lower bounds on the per-player communication required for solving multi-player$\textsc{equality}$problems in a private-message setting. This in turn gives a ... more >>> TR09-023 | 12th March 2009 Akinori Kawachi, Osamu Watanabe #### Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with mild hardness'' under any P-samplable distribution H; ... more >>> TR14-043 | 2nd April 2014 Venkatesan Guruswami, Euiwoong Lee #### Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs Consider a$K$-uniform hypergraph$H = (V,E)$. A coloring$c : V \rightarrow \{1, 2, \dots, k \}$with$k$colors is rainbow if every hyperedge$e$contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A ... more >>> TR14-025 | 25th February 2014 Oded Goldreich, Tom Gur, Ilan Komargodski #### Strong Locally Testable Codes with Relaxed Local Decoders Locally testable codes (LTCs) are error-correcting codes that admit very efficient codeword tests. An LTC is said to be strong if it has a proximity-oblivious tester; that is, a tester that makes only a constant number of queries and reject non-codewords with probability that depends solely on their distance from ... more >>> TR13-022 | 5th February 2013 Michael Viderman #### Strong LTCs with inverse poly-log rate and constant soundness Revisions: 1 An error-correcting code$C \subseteq \F^n$is called$(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most$q$queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords$x\notin C$with probability at least$\epsilon \cdot \delta(x,C)$, where ... more >>> TR12-168 | 26th November 2012 Michael Viderman #### Strong LTCs with inverse polylogarithmic rate and soundness An error-correcting code$C \subseteq \F^n$is called$(q,\epsilon)$-strong locally testable code (LTC) if there exists a randomized algorithm (tester) that makes at most$q$queries to the input word. This algorithm accepts all codewords with probability 1 and rejects all non-codewords$x\notin C$with probability at least$\epsilon \cdot ... more >>>

TR21-042 | 16th March 2021
Dana Moshkovitz

#### Strong Parallel Repetition for Unique Games on Small Set Expanders

We show that NP-hardness of approximating Boolean unique games on small set expanders can be amplified to the full Unique Games Conjecture on small set expanders.
The latter conjecture is known to imply hardness results for problems like Balanced-Separator, Minimum-Linear-Rearrangement and Small-Set-Expansion that are not known under the Unique ... more >>>

TR11-135 | 9th October 2011
Maurice Jansen, Rahul Santhanam

#### Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes

We associate to each Boolean language complexity class $\mathcal{C}$ the algebraic class $a\cdot\mathcal{C}$ consisting of families of polynomials $\{f_n\}$ for which the evaluation problem over the integers is in $\mathcal{C}$. We prove the following lower bound and randomness-to-hardness results:

1. If polynomial identity testing (PIT) is in $NSUBEXP$ then $a\cdot ... more >>> TR10-030 | 18th February 2010 Airat Khasianov #### Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem Revisions: 2 We consider the \emph{Hidden Subgroup} in the context of quantum \emph{Ordered Binary Decision Diagrams}. We show several lower bounds for this function. In this paper we also consider a slightly more general definition of the hidden subgroup problem (in contrast to that in \cite{khashsp1}). It turns out that ... more >>> TR16-188 | 21st November 2016 Toniann Pitassi, Robert Robere #### Strongly Exponential Lower Bounds for Monotone Computation For a universal constant$\alpha > 0$, we prove size lower bounds of$2^{\alpha N}$for computing an explicit monotone function in NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where$N$is the number of variables of the ... more >>> TR19-032 | 4th March 2019 Srikanth Srinivasan #### Strongly Exponential Separation Between Monotone VP and Monotone VNP Revisions: 1 We show that there is a sequence of explicit multilinear polynomials$P_n(x_1,\ldots,x_n)\in \mathbb{R}[x_1,\ldots,x_n]$with non-negative coefficients that lies in monotone VNP such that any monotone algebraic circuit for$P_n$must have size$\exp(\Omega(n)).$This builds on (and strengthens) a result of Yehudayoff (2018) who showed a lower bound of$\exp(\tilde{\Omega}(\sqrt{n})).$more >>> TR04-057 | 16th May 2004 Monica del Pilar Canales Chacon, Michael Johannes Vielhaber #### Structural and Computational Complexity of Isometries and their Shift Commutators {\bf Abstract} Isometries on formal power series over the finite field$\ff_2$or on$2$--adic integers can be computed by invertible transducers on inputs from$\{0,1\}^\infty$. We consider the structural complexity of an isometry$f$, measured as {\it tree complexity}$T(f,h)$,$h$the tree height [H.~Niederreiter, M.~Vielhaber, {\it J.~Cpx.}, ... more >>> TR08-073 | 4th August 2008 Dmitry Itsykson #### Structural complexity of AvgBPP We study class AvgBPP that consists of distributional problems that can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial-time samplable distributions. Since we use deterministic ... more >>> TR96-066 | 21st November 1996 Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan #### Structure in Approximation Classes The study of the approximability properties of NP-hard optimization problems has recently made great advances mainly due to the results obtained in the field of proof checking. In a recent breakthrough the APX-completeness of several important optimization problems is proved, thus reconciling two distinct views of ... more >>> TR16-044 | 21st March 2016 Kaave Hosseini, Shachar Lovett #### Structure of protocols for XOR functions Revisions: 1 Let$f:\{0,1\}^n \to \{0,1\}$be a boolean function. Its associated XOR function is the two-party function$f_\oplus(x,y) = f(x \oplus y)$. We show that, up to polynomial factors, the deterministic communication complexity of$f_{\oplus}$is equal to the parity decision tree complexity of$f$. This relies on a novel technique ... more >>> TR07-008 | 27th November 2006 Philipp Weis, Neil Immerman #### Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words It is well-known that every first-order property on words is expressible using at most three variables. The subclass of properties expressible with only two variables is also quite interesting and well-studied. We prove precise structure theorems that characterize the exact expressive power of first-order logic with two variables on words. ... more >>> TR13-182 | 20th December 2013 Boaz Barak #### Structure vs Combinatorics in Computational Complexity Some computational problems seem to have a certain "structure" that is manifested in non-trivial algorithmic properties, while others are more "unstructured" in the sense that they are either "very easy" or "very hard". I survey some of the known results and open questions about this classification and its connections to ... more >>> TR16-091 | 3rd June 2016 Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan #### Structure vs Hardness through the Obfuscation Lens Revisions: 3 Cryptography relies on the computational hardness of structured problems. While one-way functions, the most basic cryptographic object, do not seem to require much structure, as we advance up the ranks into public-key cryptography and beyond, we seem to require that certain structured problems are hard. For example, factoring, quadratic residuosity, ... more >>> TR96-048 | 12th September 1996 Eric Allender, Klaus-Joern Lange #### StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n) We present a deterministic algorithm running in space O((log^2 n)/loglog n) solving the connectivity problem on strongly unambiguous graphs. In addition, we present an O(log n) time-bounded algorithm for this problem running on a parallel pointer machine. more >>> TR05-086 | 14th August 2005 Dana Moshkovitz, Ran Raz #### Sub-Constant Error Low Degree Test of Almost Linear Size Revisions: 1 Given a function f:F^m \rightarrow F over a finite field F, a low degree tester tests its proximity to an m-variate polynomial of total degree at most d over F. The tester is usually given access to an oracle A providing the supposed restrictions of f to affine subspaces of ... more >>> TR07-026 | 21st November 2006 Dana Moshkovitz, Ran Raz #### Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size We show a construction of a PCP with both sub-constant error and almost-linear size. Specifically, for some constant alpha in (0,1), we construct a PCP verifier for checking satisfiability of Boolean formulas that on input of size n uses log n + O((log n)^{1-alpha}) random bits to query a constant ... more >>> TR14-088 | 13th July 2014 Swagato Sanyal #### Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity Revisions: 1 , Comments: 1 We prove that the Fourier dimension of any Boolean function with Fourier sparsity$s$is at most$O\left(s^{2/3}\right)$. Our proof method yields an improved bound of$\widetilde{O}(\sqrt{s})$assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every Boolean function of sparsity$s$there is an affine subspace of more >>> TR14-157 | 27th November 2014 Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk #### Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models. For depth-3 multilinear formulas, of size$\exp(n^\delta)$, we give a hitting set of size$\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$. ... more >>> TR05-125 | 2nd November 2005 Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith #### Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size We raise the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present algorithms and lower bounds for approximating compressibility with respect to ... more >>> TR11-013 | 3rd February 2011 Ronitt Rubinfeld, Asaf Shapira #### Sublinear Time Algorithms Sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a very small portion of the input. We discuss the types of answers that one can hope to achieve in this setting. more >>> TR11-090 | 2nd June 2011 Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee #### Submodular Functions Are Noise Stable Revisions: 2 We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on$\{-1,1\}^n$(for any constant accuracy parameter$\epsilon$). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular ... more >>> TR09-129 | 30th November 2009 Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer #### Subsampling Semidefinite Programs and Max-Cut on the Sphere Revisions: 1 We study the question of whether the value of mathematical programs such as linear and semidefinite programming hierarchies on a graph$G$, is preserved when taking a small random subgraph$G'$of$G$. We show that the value of the Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of$G'$is more >>> TR17-064 | 20th April 2017 Venkatesan Guruswami, Chaoping Xing, chen yuan #### Subspace Designs based on Algebraic Function Fields Subspace designs are a (large) collection of high-dimensional subspaces$\{H_i\}$of$\F_q^m$such that for any low-dimensional subspace$W$, only a small number of subspaces from the collection have non-trivial intersection with$W$; more precisely, the sum of dimensions of$W \cap H_i$is at most some parameter$L$. The ... more >>> TR11-139 | 26th October 2011 Zeev Dvir, Shachar Lovett #### Subspace Evasive Sets In this work we describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed subspace-evasive sets, started in the work of Pudlak and Rodl (2004) ... more >>> TR14-037 | 21st March 2014 Hamidreza Jahanjou, Eric Miles, Emanuele Viola #### Succinct and explicit circuits for sorting and connectivity We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$circuits ... more >>> TR96-006 | 24th January 1996 Bernd Borchert, Antoni Lozano #### Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept This note connects two topics of Complexity Theory: The topic of succinct circuit representations initiated by Galperin and Wigderson and the topic of leaf languages initiated by Bovet, Crescenzi, and Silvestri. It will be shown for any language that its succinct version is more >>> TR15-100 | 16th June 2015 Bireswar Das, Patrick Scharpfenecker, Jacobo Toran #### Succinct Encodings of Graph Isomorphism It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity. We introduce a new way for encoding graph problems, based on$\textrm{CNF}$or$\textrm{DNF}$formulas. We show that contrary to the other existing succinct models, there are ... more >>> TR17-007 | 19th January 2017 Michael Forbes, Amir Shpilka, Ben Lee Volk #### Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds Revisions: 1 We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been ... more >>> TR12-086 | 4th July 2012 Shlomi Dolev, Nova Fandina, Dan Gutfreund #### Succinct Permanent is NEXP-hard with Many Hard Instances Finding a problem that is both hard to solve and hard to solve on many instances is a long standing issue in theoretical computer science. In this work, we prove that the Succinct Permanent$\bmod \; p$is$NEXP$time hard in the worst case (via randomized polynomial time ... more >>> TR95-048 | 5th October 1995 Helmut Veith #### Succinct Representation and Leaf Languages In this paper, we present stronger results in the theory of succinct problem representation by boolean circuits, and establish a close relationship between succinct problems and leaf languages. As a major tool, we use quantifierfree projection reductions from descriptive complexity theory. In particular, we show that the succinct upgrading ... more >>> TR09-043 | 18th May 2009 Elena Grigorescu, Tali Kaufman, Madhu Sudan #### Succinct Representation of Codes with Applications to Testing Motivated by questions in property testing, we search for linear error-correcting codes that have the single local orbit'' property: i.e., they are specified by a single local constraint and its translations under the symmetry group of the code. We show that the dual of every sparse'' binary code whose coordinates more >>> TR16-079 | 2nd May 2016 Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli #### Sum-of-squares hierarchy lower bounds for symmetric formulations We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of well-behaved'' univariate polynomial inequalities. We illustrate the technique on ... more >>> TR18-126 | 24th June 2018 Pravesh Kothari, Ruta Mehta #### Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium Several works have shown unconditional hardness (via integrality gaps) of computing equilibria using strong hierarchies of convex relaxations. Such results however only apply to the problem of computing equilibria that optimize a certain objective function and not to the (arguably more fundamental) task of finding \emph{any} equilibrium. We present ... more >>> TR14-059 | 21st April 2014 Boaz Barak, David Steurer #### Sum-of-squares proofs and the quest toward optimal algorithms Revisions: 2 In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible ... more >>> TR15-071 | 23rd April 2015 Mrinal Kumar, Shubhangi Saraf #### Sums of products of polynomials in few variables : lower bounds and polynomial identity testing We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T \prod_{j = 1}^d Q_{ij}$$ such that each$Q_{ij}$is an arbitrary polynomial that depends on at most$s$variables. ... more >>> TR15-204 | 14th December 2015 Meena Mahajan, Anuj Tawari #### Sums of read-once formulas: How many summands suffice? Revisions: 2 An arithmetic read-once formula (ROF) is a formula (circuit of fan-out 1) over$+, \times$where each variable labels at most one leaf. Every multilinear polynomial can be expressed as the sum of ROFs. In this work, we prove, for certain multilinear polynomials, a tight lower bound ... more >>> TR18-082 | 21st April 2018 Xin Li, Shachar Lovett, Jiapeng Zhang #### Sunflowers and Quasi-sunflowers from Randomness Extractors The Erdos-Rado sunflower theorem (Journal of Lond. Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding sunflower conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which ... more >>> TR20-011 | 9th February 2020 Dominik Scheder, Navid Talebanfard #### Super Strong ETH is true for strong PPSZ We construct$k$-CNFs with$m$variables on which the strong version of PPSZ$k$-SAT algorithm, which uses bounded width resolution, has success probability at most$2^{-(1 - (1 + \epsilon)2/k)m}$for every$\epsilon > 0$. Previously such a bound was known only for the weak PPSZ algorithm which exhaustively searches ... more >>> TR15-188 | 24th November 2015 Daniel Kane, Ryan Williams #### Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for ... more >>> TR00-025 | 20th May 2000 Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee #### Super-linear time-space tradeoff lower bounds for randomized computation We prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques are an extension of those used by Ajtai in his ... more >>> TR14-097 | 31st July 2014 Oded Goldreich, Liav Teichner #### Super-Perfect Zero-Knowledge Proofs Revisions: 1 We initiate a study of super-perfect zero-knowledge proof systems. Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time. In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated by a strict probabilistic polynomial-time that ... more >>> TR13-167 | 28th November 2013 Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma #### Super-polylogarithmic hypergraph coloring hardness via low-degree long codes We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the “short code” of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results. In particular, we prove quasi-NP-hardness of the following problems on ... more >>> TR16-203 | 21st December 2016 Christoph Berkholz, Jakob Nordström #### Supercritical Space-Width Trade-offs for Resolution We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben-Sasson '09]}, and provides one more ... more >>> TR13-002 | 31st December 2012 Venkatesan Guruswami, Krzysztof Onak #### Superlinear lower bounds for multipass graph processing Revisions: 3 We prove$n^{1+\Omega(1/p)}/p^{O(1)}$lower bounds for the space complexity of$p$-pass streaming algorithms solving the following problems on$n$-vertex graphs: * testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size), * testing if two ... more >>> TR00-010 | 12th January 2000 Amitabha Roy, Christopher Wilson #### Supermodels and Closed Sets A {\em supermodel} is a satisfying assignment of a boolean formula for which any small alteration, such as a single bit flip, can be repaired by another small alteration, yielding a nearby satisfying assignment. We study computational problems associated with super models and some generalizations thereof. For general formulas, ... more >>> TR13-181 | 20th December 2013 Mrinal Kumar, Shubhangi Saraf #### Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits In this paper, we prove superpolynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. We give an explicit polynomial in VNP of degree$n$in$n^2$variables such that any homogeneous depth 4 arithmetic circuit computing it must have size$n^{\Omega(\log \log n)}$. Our results extend ... more >>> TR05-072 | 11th July 2005 Christian Glaßer, Alan L. Selman, Liyu Zhang #### Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems We survey recent results on disjoint NP-pairs. In particular, we survey the relationship of disjoint NP-pairs to the theory of proof systems for propositional calculus. more >>> TR12-139 | 2nd November 2012 Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson #### Sylvester-Gallai type theorems for approximate collinearity We study questions in incidence geometry where the precise position of points is `blurry' (e.g. due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and more generally affine subspaces are replaced by their small neighborhood. We show that the presence of a sufficiently large number of ... more >>> TR07-024 | 5th March 2007 Laszlo Egri, Benoit Larose, Pascal Tesson #### Symmetric Datalog and Constraint Satisfaction Problems in Logspace We introduce symmetric Datalog, a syntactic restriction of linear Datalog and show that its expressive power is exactly that of restricted symmetric monotone Krom SNP. The deep result of Reingold on the complexity of undirected connectivity suffices to show that symmetric Datalog queries can be evaluated in logarithmic space. We ... more >>> TR10-199 | 14th December 2010 Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan #### Symmetric LDPC codes are not necessarily locally testable Locally testable codes, i.e., codes where membership in the code is testable with a constant number of queries, have played a central role in complexity theory. It is well known that a code must be a "low-density parity check" (LDPC) code for it to be locally testable, but few LDPC ... more >>> TR94-003 | 12th December 1994 Noam Nisan, Amnon Ta-Shma #### Symmetric Logspace is Closed Under Complement We present a Logspace, many-one reduction from the undirected st-connectivity problem to its complement. This shows that$SL=co-SL$more >>> TR03-047 | 22nd June 2003 Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton #### Symmetric Polynomials over Z_m and Simultaneous Communication Protocols We study the problem of representing symmetric Boolean functions as symmetric polynomials over Z_m. We show an equivalence between such representations and simultaneous communication protocols. Computing a function with a polynomial of degree d modulo m=pq is equivalent to a two player protocol where one player is given the first ... more >>> TR94-015 | 12th December 1994 Miklos Ajtai #### Symmetric Systems of Linear Equations modulo$p$Suppose that$p$is a prime number$A$is a finite set with$n$elements and for each sequence$a=<a_{1},...,a_{k}>$of length$k$from the elements of$A$,$x_{a}$is a variable. (We may think that$k$and$p$are fixed an$n$is sufficiently large.) We will ... more >>> TR06-091 | 29th May 2006 Felix Brandt, Felix Fischer, Markus Holzer #### Symmetries and the Complexity of Pure Nash Equilibrium Strategic games may exhibit symmetries in a variety of ways. A common aspect of symmetry, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering ... more >>> TR10-070 | 17th April 2010 Eric Allender, Klaus-Joern Lange #### Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC$^1$= LogCFL) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time. more >>> TR10-191 | 9th December 2010 Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland #### Symmetry-assisted adversaries for quantum state generation We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum ... more >>> TR12-122 | 17th September 2012 Giorgio Ausiello, Francesco Cristiano, Luigi Laura #### Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete We investigate the complexity of the syntactic isomorphism problem of CNF Boolean Formulas (CSFI): given two CNF Boolean formulas$\varphi(a_{1},\ldots,a_{n})$and$\varphi(b_{1},\ldots,b_{n})$decide whether there exists a permutation of clauses, a permutation of literals and a bijection between their variables such that$\varphi(a_{1},\ldots,a_{n})$and$\varphi(b_{1},\ldots,b_{n})$become syntactically identical. We first ... more >>> TR95-045 | 4th September 1995 Moni Naor, Omer Reingold #### Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions A pseudo-random function is a fundamental cryptographic primitive that is essential for encryption, identification and authentication. We present a new cryptographic primitive called pseudo-random synthesizer and show how to use it in order to get a parallel construction of a pseudo-random function. We show an$NC^1$implementation of synthesizers ... more >>> TR01-030 | 25th April 2001 Jin-Yi Cai #### S_2^p \subseteq ZPP^{NP} We show that the class${\rm S}_2^p$is a subclass of${{\rm ZPP}^{\rm NP}}$. The proof uses universal hashing, approximate counting and witness sampling. As a consequence, a collapse first noticed by Samik Sengupta that the assumption NP has small circuits collapses PH to${\rm S}_2^p\$
becomes the strongest version ... more >>>

ISSN 1433-8092 | Imprint