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

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.

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

TR07-103 | 28th September 2007
Emanuele Viola

#### Selected Results in Additive Combinatorics: An Exposition

We give a self-contained exposition of selected results in additive
combinatorics over the group {0,1}^n. In particular, we prove the
celebrated theorems known as the Balog-Szemeredi-Gowers theorem ('94 and '98) and
the
Freiman-Ruzsa theorem ('73 and '99), leading to the remarkable result
by Samorodnitsky ('07) that linear transformations are efficiently ... more >>>

TR95-031 | 25th June 1995
Dorit Dor, Uri Zwick

#### Selecting the median

Improving a long standing result of Sch\"{o}nhage, Paterson
and Pippenger we show that the MEDIAN of a set containing n
elements can always be found using at most 2.95n comparisons.

This is the full version of the paper. An extended abstract
version ... more >>>

TR04-085 | 3rd October 2004
Erez Petrank, Guy Rothblum

#### Selection from Structured Data Sets

A large body of work studies the complexity of selecting the
$j$-th largest element in an arbitrary set of $n$ elements (a.k.a.
the select$(j)$ operation). In this work, we study the
complexity of select in data that is partially structured by
an initial preprocessing stage and in a data structure ... more >>>

TR19-142 | 23rd October 2019
Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch, Iddo Tzameret

#### Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?

We introduce the binary value principle' which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, ... more >>>

TR14-090 | 11th July 2014
Justin Thaler

#### Semi-Streaming Algorithms for Annotated Graph Streams

Revisions: 2

Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require $\Omega(n^2)$ space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of ... more >>>

TR19-106 | 12th August 2019
Noah Fleming, Pravesh Kothari, Toniann Pitassi

#### Semialgebraic Proofs and Efficient Algorithm Design

Revisions: 2

Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential ... more >>>

TR95-011 | 15th February 1995
Roman Bacik, Sanjeev Mahajan

#### Semidefinite Programming and its Applications to NP Problems

The graph homomorphism problem is a canonical $NP$-complete problem.
It generalizes various other well-studied problems such as graph
coloring and finding cliques. To get a better insight into a
combinatorial problem, one often studies relaxations of the problem.
We define fractional homomorphisms and pseudo-homomorphisms ... more >>>

TR20-002 | 6th January 2020
Sophie Laplante, Reza Naserasr, Anupa Sunny

#### Sensitivity lower bounds from linear dependencies

Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least the square root of n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we ... more >>>

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

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

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

TR14-126 | 9th October 2014
Debasis Mandal, A. Pavan, Rajeswari Venugopalan

#### Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis

We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a {\em worst-case} hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time $O(2^{2^{n^c}})$ (for some $c > 1$) accepting $\Sigma^*$ whose accepting ... more >>>

TR18-124 | 6th July 2018
Amir Yehudayoff

#### Separating Monotone VP and VNP

This work is about the monotone versions of the algebraic complexity classes VP and VNP. The main result is that monotone VNP is strictly stronger than monotone VP.

more >>>

TR11-134 | 9th October 2011
Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

#### Separating multilinear branching programs and formulas

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of ... more >>>

TR08-014 | 26th February 2008
Matei David

#### Separating NOF communication complexity classes RP and NP

We provide a non-explicit separation of the number-on-forehead communication complexity classes RP and NP when the number of players is up to \delta log(n) for any \delta<1. Recent lower bounds on Set-Disjointness [LS08,CA08] provide an explicit separation between these classes when the number of players is only up to o(loglog(n)).

... more >>>

TR14-110 | 19th August 2014
Uriel Feige, Shlomo Jozeph

#### Separation between Estimation and Approximation

We show (under standard assumptions) that there are NP optimization problems for which estimation is easier than approximation. Namely, one can estimate the value of the optimal solution within a ratio of $\rho$, but it is difficult to find a solution whose value is within $\rho$ of optimal.
As an ... more >>>

TR15-154 | 22nd September 2015
Neeraj Kayal, Vineet Nair, Chandan Saha

#### Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following:

1. There exists an explicit $n$-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) ... more >>>

TR17-022 | 13th February 2017
Benjamin Rossman, Srikanth Srinivasan

#### Separation of AC$^0[\oplus]$ Formulas and Circuits

This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the $\mathrm{AC}^0[\oplus]$ basis (unbounded fan-in AND, OR, NOT and MOD$_2$ gates). We show, for all $d(n) \le O(\frac{\log n}{\log\log n})$, that there exist {\em polynomial-size depth-$d$ circuits} that are not equivalent ... more >>>

TR01-032 | 3rd April 2001
A. Pavan, Alan L. Selman

#### Separation of NP-completeness Notions

We use hypotheses of structural complexity theory to separate various
NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is Turing complete but not truth-table complete. We provide fairly thorough analyses of the hypotheses that we introduce. Unlike previous approaches, we ... more >>>

TR16-072 | 4th May 2016
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

#### Separations in communication complexity using cheat sheets and information complexity

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized
communication complexity for a ... more >>>

TR15-098 | 15th June 2015
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

#### Separations in Query Complexity Based on Pointer Functions

Revisions: 2

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized
query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree
of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. ... more >>>

TR15-175 | 5th November 2015
Scott Aaronson, Shalev Ben-David, Robin Kothari

#### Separations in query complexity using cheat sheets

We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity ... more >>>

TR10-136 | 26th August 2010
Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie

#### Separations of Matroid Freeness Properties

Revisions: 1

Properties of Boolean functions on the hypercube that are invariant
with respect to linear transformations of the domain are among some of
the most well-studied properties in the context of property testing.
In this paper, we study a particular natural class of linear-invariant
properties, called matroid freeness properties. These properties ... more >>>

TR19-159 | 11th November 2019
Noah Stephens-Davidowitz, Vinod Vaikuntanathan

#### SETH-hardness of Coding Problems

We show that assuming the strong exponential-time hypothesis (SETH), there are no non-trivial algorithms for the nearest codeword problem (NCP), the minimum distance problem (MDP), or the nearest codeword problem with preprocessing (NCPP) on linear codes over any finite field. More precisely, we show that there are no NCP, MDP, ... more >>>

TR05-140 | 30th November 2005
Xi Chen, Xiaotie Deng

#### Settling the Complexity of 2-Player Nash-Equilibrium

Revisions: 1

We prove that finding the solution of two player Nash Equilibrium is PPAD-complete.

more >>>

TR17-068 | 20th April 2017
Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie

#### Settling the query complexity of non-adaptive junta testing

We prove that any non-adaptive algorithm that tests whether an unknown
Boolean function $f\colon \{0, 1\}^n\to\{0, 1\}$ is a $k$-junta or $\epsilon$-far from every $k$-junta must make $\widetilde{\Omega}(k^{3/2} / \epsilon)$ many queries for a wide range of parameters $k$ and $\epsilon$. Our result dramatically improves previous lower ... more >>>

TR03-012 | 21st January 2003
Edward Hirsch, Arist Kojevnikov

#### Several notes on the power of Gomory-Chvatal cuts

We prove that the Cutting Plane proof system based on
Gomory-Chvatal cuts polynomially simulates the
lift-and-project system with integer coefficients
written in unary. The restriction on coefficients can be
omitted when using Krajicek's cut-free Gentzen-style extension
of both systems. We also prove that Tseitin tautologies
have short proofs in ... more >>>

TR17-164 | 3rd November 2017
Scott Aaronson

#### Shadow Tomography of Quantum States

We introduce the problem of *shadow tomography*: given an unknown $D$-dimensional quantum mixed state $\rho$, as well as known two-outcome measurements $E_{1},\ldots,E_{M}$, estimate the probability that $E_{i}$ accepts $\rho$, to within additive error $\varepsilon$, for each of the $M$ measurements. How many copies of $\rho$ are needed to achieve this, ... more >>>

TR13-044 | 25th March 2013
Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

#### Shared Randomness and Quantum Communication in the Multi-Party Model

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case.

First, we demonstrate a hierarchy of modes of shared ... more >>>

TR17-132 | 7th September 2017
Ilias Diakonikolas, Daniel Kane, Alistair Stewart

#### Sharp Bounds for Generalized Uniformity Testing

We study the problem of {\em generalized uniformity testing}~\cite{BC17} of a discrete probability distribution: Given samples from a probability distribution $p$ over an {\em unknown} discrete domain $\mathbf{\Omega}$, we want to distinguish, with probability at least $2/3$, between the case that $p$ is uniform on some {\em subset} of $\mathbf{\Omega}$ ... more >>>

TR96-011 | 29th January 1996
Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

#### Sharply Bounded Alternation within P

We define the sharply bounded hierarchy, SBHQL, a hierarchy of
classes within P, using quasilinear-time computation and
quantification over values of length log n. It generalizes the
limited nondeterminism hierarchy introduced by Buss and Goldsmith,
while retaining the invariance properties. The new hierarchy has
several alternative characterizations.

We define ... more >>>

TR15-189 | 25th November 2015
Shay Moran, Cyrus Rashtchian

#### Shattered Sets and the Hilbert Function

Revisions: 1

We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result ... more >>>

TR13-003 | 2nd January 2013
Eric Miles, Emanuele Viola

#### Shielding circuits with groups

Revisions: 2

We show how to efficiently compile any given circuit $C$
into a leakage-resistant circuit $\widehat{C}$ such that any
function on the wires of $\widehat{C}$ that leaks information
during a computation $\widehat{C}(x)$ yields advantage in
computing the product of $|\widehat{C}|^{\Omega(1)}$ elements
of the alternating group $A_u$. In combination with new
compression ... more >>>

TR16-046 | 23rd March 2016
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

#### Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck

Revisions: 2

We study *interactive oracle proofs* (IOPs) (Ben-Sasson, Chiesa, Spooner '16), which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and general techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs ... more >>>

TR13-007 | 8th January 2013
Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand

#### Short lists with short programs in short time

Revisions: 1

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on ... more >>>

TR05-014 | 30th January 2005
Oded Goldreich

#### Short Locally Testable Codes and Proofs (Survey)

We survey known results regarding locally testable codes
and locally testable proofs (known as PCPs),
with emphasis on the length of these constructs.
Locally testability refers to approximately testing
large objects based on a very small number of probes,
each retrieving a single bit in the ... more >>>

TR14-017 | 9th February 2014
Eli Ben-Sasson, Emanuele Viola

#### Short PCPs with projection queries

We construct a PCP for NTIME(2$^n$) with constant
soundness, $2^n \poly(n)$ proof length, and $\poly(n)$
queries where the verifier's computation is simple: the
queries are a projection of the input randomness, and the
computation on the prover's answers is a 3CNF. The
previous upper bound for these two computations was
more >>>

TR99-022 | 14th June 1999
Eli Ben-Sasson, Avi Wigderson

#### Short Proofs are Narrow - Resolution made Simple

The width of a Resolution proof is defined to be the maximal number of
literals in any clause of the proof. In this paper we relate proof width
to proof length (=size), in both general Resolution, and its tree-like
variant. The following consequences of these relations reveal width as ... more >>>

TR11-174 | 30th December 2011
Pavel Hrubes, Iddo Tzameret

#### Short Proofs for the Determinant Identities

Revisions: 1

We study arithmetic proof systems $\mathbb{P}_c(\mathbb{F})$ and $\mathbb{P}_f(\mathbb{F})$ operating with arithmetic circuits and arithmetic formulas, respectively, that prove polynomial identities over a field $\mathbb{F}$. We establish a series of structural theorems about these proof systems, the main one stating that $\mathbb{P}_c(\mathbb{F})$ proofs can be balanced: if a polynomial identity of ... more >>>

TR18-102 | 15th May 2018
Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan

#### Short Proofs in QBF Expansion

For quantified Boolean formulas (QBF) there are two main different approaches to solving: QCDCL and expansion solving. In this paper we compare the underlying proof systems and show that expansion systems admit strictly shorter proofs than CDCL systems for formulas of bounded quantifier complexity, thus pointing towards potential advantages of ... more >>>

TR09-002 | 23rd November 2008
Eli Ben-Sasson, Jakob Nordström

#### Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution

A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space.

In this paper we resolve the question by answering ... more >>>

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

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

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

TR14-048 | 10th April 2014
Avishay Tal

#### Shrinkage of De Morgan Formulae from Quantum Query Complexity

Revisions: 1

We give a new and improved proof that the shrinkage exponent of De Morgan formulae is $2$. Namely, we show that for any Boolean function $f: \{-1,1\}^n \to \{-1,1\}$, setting each variable out of $x_1, \ldots, x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size ... more >>>

TR19-067 | 6th May 2019
Hamed Hatami, Kaave Hosseini, Shachar Lovett

#### Sign rank vs Discrepancy

Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions.
In this article, we establish the strongest possible separation by constructing a Boolean matrix whose sign-rank ... more >>>

TR14-135 | 23rd October 2014
Noga Alon, Shay Moran, Amir Yehudayoff

#### Sign rank, VC dimension and spectral gaps

Revisions: 2

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>

TR19-027 | 1st March 2019
Mark Bun, Nikhil Mande, Justin Thaler

#### Sign-Rank Can Increase Under Intersection

The communication class $UPP^{cc}$ is a communication analog of the Turing Machine complexity class $PP$. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds.

For a communication problem ... more >>>

TR09-063 | 29th July 2009
Matt DeVos, Ariel Gabizon

#### Simple Affine Extractors using Dimension Expansion

Revisions: 2

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$
such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased
bit when $x$ is chosen uniformly from $X$.
Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets ... more >>>

TR18-100 | 18th May 2018
Eshan Chattopadhyay, Anindya De, Rocco Servedio

#### Simple and efficient pseudorandom generators from Gaussian processes

Revisions: 1

We show that a very simple pseudorandom generator fools intersections of $k$ linear threshold functions (LTFs) and arbitrary functions of $k$ LTFs over $n$-dimensional Gaussian space.

The two analyses of our PRG (for intersections versus arbitrary functions of LTFs) are quite different from each other and from previous analyses of ... more >>>

TR17-018 | 6th February 2017
Oded Goldreich, Guy Rothblum

#### Simple doubly-efficient interactive proof systems for locally-characterizable sets

Revisions: 3

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.

We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.
Specifically, such ... more >>>

TR05-071 | 29th June 2005
Marius Zimand

#### Simple extractors via constructions of cryptographic pseudo-random generators

Trevisan has shown that constructions of pseudo-random generators from
hard functions (the Nisan-Wigderson approach) also produce extractors.
We show that constructions of pseudo-random generators from one-way permutations
(the Blum-Micali-Yao approach) can be used for building extractors as well.
Using this new technique we build extractors that ... more >>>

TR18-063 | 5th April 2018
William Hoza, David Zuckerman

#### Simple Optimal Hitting Sets for Small-Success $\mathbf{RL}$

Revisions: 1

We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order. Our generator has seed length $O\left(\frac{\log(wr) \log r}{\max\{1, \log \log w - \log \log r\}} + \log(1/\varepsilon)\right)$. This seed length improves on recent work by Braverman, Cohen, and ... more >>>

TR04-060 | 22nd July 2004

#### Simple PCPs with Poly-log Rate and Query Complexity

We give constructions of PCPs of length n*polylog(n) (with respect
to circuits of size n) that can be verified by making polylog(n)
queries to bits of the proof. These PCPs are not only shorter than
previous ones, but also simpler. Our (only) building blocks are
Reed-Solomon codes and the bivariate ... more >>>

TR04-071 | 11th August 2004
Marcus Schaefer, Stephen A. Fenner

#### Simplicity and Strong Reductions

A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP ... more >>>

TR00-004 | 14th January 2000
Oded Goldreich, Salil Vadhan, Avi Wigderson

#### Simplified derandomization of BPP using a hitting set generator.

A hitting-set generator is a deterministic
algorithm which generates a set of strings that intersects
every dense set recognizable by a small circuit.
A polynomial time hitting-set generator readily implies $RP=P$.
Andreev \etal\/ (ICALP'96, and JACM 1998)
showed that if polynomial-time hitting-set
generator in fact implies ... more >>>

TR19-048 | 2nd April 2019
Per Austrin, Amey Bhangale, Aditya Potukuchi

#### Simplified inpproximability of hypergraph coloring via t-agreeing families

We reprove the results on the hardness of approximating hypergraph coloring using a different technique based on bounds on the size of extremal $t$-agreeing families of $[q]^n$. Specifically, using theorems of Frankl-Tokushige [FT99], Ahlswede-Khachatrian [AK98] and Frankl [F76] on the size of such families, we give simple and unified proofs ... more >>>

TR14-060 | 21st April 2014
Anup Rao, Amir Yehudayoff

#### Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Revisions: 1

We show that the deterministic multiparty communication complexity of set disjointness for $k$ parties on a universe of size $n$ is $\Omega(n/4^k)$. We also simplify Sherstov's proof
showing an $\Omega(\sqrt{n}/(k2^k))$ lower bound for the randomized communication complexity of set disjointness.

more >>>

TR15-057 | 13th April 2015
Anup Rao, Makrand Sinha

#### Simplified Separation of Information and Communication

Revisions: 3

We give an example of a boolean function whose information complexity is exponentially
smaller than its communication complexity. Our result simplifies recent work of Ganor, Kol and
Raz (FOCS'14, STOC'15).

more >>>

TR04-089 | 26th October 2004
Ingo Wegener

#### Simulated Annealing Beats Metropolis in Combinatorial Optimization

The Metropolis algorithm is simulated annealing with a fixed temperature.Surprisingly enough, many problems cannot be solved more efficiently by simulated annealing than by the Metropolis algorithm with the best temperature. The problem of finding a natural example (artificial examples are known) where simulated annealing outperforms the Metropolis algorithm for all ... more >>>

TR00-067 | 13th July 2000
Peter Auer, Philip M. Long

We introduce a new technique which enables a learner without access to
hidden information to learn nearly as well as a learner with access to
hidden information. We apply our technique to solve an open problem
of Maass and Turan, showing that for any concept class F the least ... more >>>

TR05-006 | 28th December 2004
Edward Hirsch, Sergey I. Nikolenko

#### Simulating Cutting Plane proofs with restricted degree of falsity by Resolution

Goerdt (1991) considered a weakened version of the Cutting Plane proof system with a restriction on the degree of falsity of intermediate inequalities. (The degree of falsity of an inequality written in the form $\sum a_ix_i+\sum b_i(1-x_i)\ge c,\ a_i,b_i\ge0$ is its constant term $c$.) He proved a superpolynomial lower bound ... more >>>

TR10-037 | 8th March 2010
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

#### Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a
distribution $X$ on binary strings of length $n$ is a
$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$
to any string of length $n$. For every $\delta>0$ we construct the
following poly($n$)-time ... more >>>

TR14-119 | 15th September 2014
Mark Braverman, Jieming Mao

#### Simulating Noisy Channel Interaction

We show that $T$ rounds of interaction over the binary symmetric channel $BSC_{1/2-\epsilon}$ with feedback can be simulated with $O(\epsilon^2 T)$ rounds of interaction over a noiseless channel. We also introduce a more general "energy cost'' model of interaction over a noisy channel. We show energy cost to be equivalent ... more >>>

TR13-154 | 29th October 2013
Martin Schwarz, Maarten Van den Nest

#### Simulating Quantum Circuits with Sparse Output Distributions

We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained ... more >>>

TR17-170 | 6th November 2017

#### Simulation Beats Richness: New Data-Structure Lower Bounds

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a $p \times n$ ... more >>>

TR14-098 | 30th July 2014
Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

#### Simultaneous Approximation of Constraint Satisfaction Problems

Given $k$ collections of 2SAT clauses on the same set of variables $V$, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.

Our main result is that ... more >>>

TR19-148 | 1st November 2019
Amey Bhangale, Subhash Khot

#### Simultaneous Max-Cut is harder to approximate than Max-Cut

A systematic study of simultaneous optimization of constraint satisfaction problems was initiated in [BKS15]. The simplest such problem is the simultaneous Max-Cut. [BKKST18] gave a $.878$-minimum approximation algorithm for simultaneous Max-Cut which is {\em almost optimal} assuming the Unique Games Conjecture (UGC). For a single instance Max-Cut, [GW95] gave an ... more >>>

TR12-164 | 17th November 2012
Rafail Ostrovsky, Ivan Visconti

#### Simultaneous Resettability from Collision Resistance

In FOCS 2001, Barak, Goldreich, Goldwasser and Lindell conjectured that the existence of ZAPs, introduced by Dwork and Naor in FOCS 2000, could lead to the design of a zero-knowledge proof system that is secure against both resetting provers and resetting verifiers. Their conjecture has been proven true by Deng, ... more >>>

TR19-114 | 2nd September 2019
Visu Makam, Avi Wigderson

#### Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties)

The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: ${\rm SING}_{n,m}$, consisting of all $m$-tuples of $n\times n$ complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in ${\rm SING}_{n,m}$ will imply super-polynomial circuit lower bounds, ... more >>>

TR03-074 | 24th June 2003
Vince Grolmusz

#### Sixtors and Mod 6 Computations

We consider the following phenomenon: with just one multiplication
we can compute (3u+2v)(3x+2y)= 3ux+4vy mod 6, while computing the same polynomial modulo 5 needs 2 multiplications. We generalize this observation and we define some vectors, called sixtors, with remarkable zero-divisor properties. Using sixtors, we also generalize our earlier result ... more >>>

TR14-077 | 2nd June 2014
Andris Ambainis, Jevgenijs Vihrovs

#### Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma

Revisions: 2

We study the structure of sets $S\subseteq\{0, 1\}^n$ with small sensitivity. The well-known Simon's lemma says that any $S\subseteq\{0, 1\}^n$ of sensitivity $s$ must be of size at least $2^{n-s}$. This result has been useful for proving lower bounds on sensitivity of Boolean functions, with applications to the theory of ... more >>>

TR17-137 | 11th September 2017
Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde

#### Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs

As a natural extension of the SAT problem, different proof systems for quantified Boolean formulas (QBF) have been proposed. Many of these extend a propositional system to handle universal quantifiers.

By formalising the construction of the QBF proof system from a propositional proof system, by the addition of the ... more >>>

TR14-183 | 25th December 2014
Nikhil Balaji, Andreas Krebs, Nutan Limaye

#### Skew Circuits of Small Width

A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs -- polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known that width-3 PBPs ... more >>>

TR12-178 | 18th December 2012
Paul Beame, Raphael Clifford, Widad Machmouchi

#### Sliding Windows With Limited Storage

Revisions: 1

We consider time-space tradeoffs for exactly computing frequency
moments and order statistics over sliding windows.
Given an input of length $2n-1$, the task is to output the function of
each window of length $n$, giving $n$ outputs in total.
Computations over sliding windows are related to direct sum problems
except ... more >>>

TR17-091 | 17th May 2017
Andrej Bogdanov

#### Small bias requires large formulas

Revisions: 1

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on the size of (1) general Boolean formulas, (2) Boolean formulas of fan-in two, (3) de Morgan formulas, as well as (4) correlation lower bounds against small de Morgan formulas ... more >>>

TR03-069 | 13th August 2003
Elmar Böhler, Christian Glaßer, Daniel Meister

#### Small Bounded-Error Computations and Completeness

SBP is a probabilistic promise class located
between MA and AM \cap BPPpath. The first
part of the paper studies the question of whether
SBP has many-one complete sets. We relate
this question to the existence of uniform
enumerations. We construct an oracle relative to
which SBP and AM do ... more >>>

TR13-102 | 17th July 2013
Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

#### Small Depth Proof Systems

A proof system for a language $L$ is a function $f$ such that Range$(f)$ is exactly $L$. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by ... more >>>

TR16-095 | 7th June 2016

#### Small Error Versus Unbounded Error Protocols in the NOF Model

We show that a simple function has small unbounded error communication complexity in the $k$-party number-on-forehead (NOF) model but every probabilistic protocol that solves it with sub-exponential advantage over random guessing has cost essentially $\Omega\left(\frac{\sqrt{n}}{4^k}\right)$ bits. Such a separation was first shown for $k=2$ independently by Buhrman et al. ['07] ... more >>>

TR17-035 | 23rd February 2017
Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena

#### Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good

Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth-$4$ circuits, which would ... more >>>

TR18-108 | 1st June 2018
Andrzej Lingas

#### Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth

We consider normalized Boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized Boolean circuits computing Boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., ... more >>>

TR00-061 | 14th August 2000

#### Small PCPs with low query complexity

Most known constructions of probabilistically checkable proofs (PCPs)
either blow up the proof size by a large polynomial, or have a high
(though constant) query complexity. In this paper we give a
transformation with slightly-super-cubic blowup in proof size, with a
low query complexity. Specifically, the verifier probes the proof ... more >>>

TR97-053 | 10th November 1997
Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim

#### Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs

Revisions: 2

We show the following Reduction Lemma: any
$\epsilon$-biased sample space with respect to (Boolean) linear
tests is also $2\epsilon$-biased with respect to
any system of independent linear tests. Combining this result with
the previous constructions of $\epsilon$-biased sample space with
respect to linear tests, we obtain the first efficient
more >>>

TR18-078 | 23rd April 2018
Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

#### Small Set Expansion in The Johnson Graph

This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers
t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if
their intersection is of size t. The Johnson graph arises often ... more >>>

TR14-095 | 24th July 2014
Mark Braverman, Ankit Garg

#### Small value parallel repetition for general games

Revisions: 1

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. We use information theoretic techniques in our proof. Our proofs also extend to the high value regime (value close to 1) ... more >>>

TR13-034 | 2nd March 2013
Louay Bazzi, Nagi Nahas

#### Small-bias is not enough to hit read-once CNF

Small-bias probability spaces have wide applications in pseudorandomness which naturally leads to the study of their limitations. Constructing a polynomial complexity hitting set for read-once CNF formulas is a basic open problem in pseudorandomness. We show in this paper that this goal is not achievable using small-bias spaces. Namely, we ... more >>>

TR17-156 | 15th October 2017
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

#### Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications

The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $\mathrm{P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted $\mathrm{IMM}_{d}$, and show ... more >>>

TR18-077 | 23rd April 2018
Boaz Barak, Pravesh Kothari, David Steurer

#### Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture

Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khot's 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain Grassmanian agreement tester''.
In this work, we show that the hypothesis of Dinur et al follows from a ... more >>>

TR19-023 | 25th February 2019

#### Smooth and Strong PCPs

Revisions: 3

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and incorrect claims are rejected with high probability (regardless of the given alleged proof). We consider two possible features of PCPs:
- ... more >>>

TR15-131 | 10th August 2015
Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson

#### Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can ... more >>>

TR07-039 | 27th March 2007
Bodo Manthey, Till Tantau

#### Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise

Revisions: 1

Binary search trees are a fundamental data structure and their height
plays a key role in the analysis of divide-and-conquer algorithms like
quicksort. Their worst-case height is linear; their average height,
whose exact value is one of the best-studied problems in average-case
complexity, is logarithmic. We analyze their smoothed height ... more >>>

TR05-063 | 24th June 2005
Bodo Manthey, Rüdiger Reischuk

#### Smoothed Analysis of the Height of Binary Search Trees

Revisions: 2

Binary search trees are one of the most fundamental data structures. While the
height of such a tree may be linear in the worst case, the average height with
respect to the uniform distribution is only logarithmic. The exact value is one
of the best studied problems in average case ... more >>>

TR08-036 | 14th March 2008
Venkatesan Guruswami, Atri Rudra

#### Soft decoding, dual BCH codes, and better list-decodable eps-biased codes

We construct binary linear codes that are efficiently list-decodable
up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits
into $n = {\rm poly}(k/\eps)$ bits and are constructible and
list-decodable in time polynomial in $k$ and $1/\eps$ (in
particular, in our results $\eps$ need ... more >>>

TR16-024 | 22nd February 2016
Patrick Scharpfenecker, Jacobo Toran

#### Solution-Graphs of Boolean Formulas and Isomorphism

The solution graph of a Boolean formula on n variables is the subgraph of the hypercube Hn induced by the satisfying assignments of the formula. The structure of solution graphs has been the object of much research in recent years since it is important for the performance of SAT-solving procedures ... more >>>

TR04-008 | 27th November 2003
Vikraman Arvind, Jacobo Toran

#### Solvable Group Isomorphism is (almost) in NP\cap coNP

The Group Isomorphism problem consists in deciding whether two input
groups $G_1$ and $G_2$ given by their multiplication tables are
isomorphic. We first give a 2-round Arthur-Merlin protocol for the
Group Non-Isomorphism problem such that on input groups $(G_1,G_2)$
of size $n$, Arthur uses ... more >>>

TR08-089 | 28th September 2008
Noam Berger, Kapur Nevin, Schulman Leonard, Vazirani Vijay

#### SOLVENCY GAMES

Abstract. We study the decision theory of a maximally risk-averse investor | one whose objec-
tive, in the face of stochastic uncertainties, is to minimize the probability of ever going broke. With
a view to developing the mathematical basics of such a theory, we start with a very simple model
more >>>

TR14-096 | 29th July 2014
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

#### Solving Linear Equations Parameterized by Hamming Weight

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:
1. Does $Ax=b$ have a solution of weight at most $t$?
2. Does $Ax=b$ have a solution of weight exactly $t$?
3. Does $Ax=b$ have a ... more >>>

TR04-043 | 20th May 2004
Luca Trevisan

#### Some Applications of Coding Theory in Computational Complexity

Error-correcting codes and related combinatorial constructs
play an important role in several recent (and old) results
in computational complexity theory. In this paper we survey
results on locally-testable and locally-decodable error-correcting
codes, and their applications to complexity theory and to
cryptography.

Locally decodable codes are error-correcting codes ... more >>>

TR95-044 | 18th September 1995
Carsten Damm, Stasys Jukna, Jiri Sgall

#### Some Bounds on Multiparty Communication Complexity of Pointer Jumping

We introduce the model of conservative one-way multiparty complexity
and prove lower and upper bounds on the complexity of pointer jumping.

The pointer jumping function takes as its input a directed layered
graph with a starting node and layers of nodes, and a single edge ... more >>>

TR12-048 | 25th April 2012

#### Some closure features of locally testable affine-invariant properties

We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and "lifts". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The "lift" is a less natural ... more >>>

TR18-052 | 16th March 2018
Chi-Ning Chou, Mrinal Kumar, Noam Solomon

#### Some Closure Results for Polynomial Factorization and Applications

In a sequence of fundamental results in the 80's, Kaltofen showed that factors of multivariate polynomials with small arithmetic circuits have small arithmetic circuits. In other words, the complexity class $VP$ is closed under taking factors. A natural question in this context is to understand if other natural classes of ... more >>>

TR16-038 | 15th March 2016
Meena Mahajan, Nitin Saurabh

#### Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

Revisions: 2

We provide a list of new natural VNP-intermediate polynomial
families, based on basic (combinatorial) NP-complete problems that
are complete under \emph{parsimonious} reductions. Over finite
fields, these families are in VNP, and under the plausible
hypothesis $\text{Mod}_pP \not\subseteq P/\text{poly}$, are neither VNP-hard (even under
oracle-circuit reductions) nor in VP. Prior to ... more >>>

TR00-024 | 16th May 2000
Amihood Amir, Richard Beigel, William Gasarch

#### Some Connections between Bounded Query Classes and Non-Uniform Complexity

Let A(x) be the characteristic function of A. Consider the function
F_k^A(x_1,...,x_k) = A(x_1)...A(x_k). We show that if F_k^A can be
computed with fewer than k queries to some set X, then A can be
computed by polynomial size circuits. A generalization of this result
has applications to bounded query ... more >>>

TR12-018 | 24th February 2012
Joerg Flum, Moritz Müller

#### Some definitorial suggestions for parameterized proof complexity

We introduce a (new) notion of parameterized proof system. For parameterized versions of standard proof systems such as Extended Frege and Substitution Frege we compare their complexity with respect to parameterized simulations.

more >>>

TR04-075 | 21st July 2004
Michael Schmitt

#### Some dichotomy theorems for neural learning problems

The computational complexity of learning from binary examples is
investigated for linear threshold neurons. We introduce
combinatorial measures that create classes of infinitely many
learning problems with sample restrictions. We analyze how the
complexity of these problems depends on the values for the measures.
... more >>>

TR01-096 | 21st November 2001
Jörg Rothe

#### Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial

Revisions: 1

In this tutorial, selected topics of cryptology and of
computational complexity theory are presented. We give a brief overview
of the history and the foundations of classical cryptography, and then
move on to modern public-key cryptography. Particular attention is
paid to cryptographic protocols and the problem of constructing ... more >>>

TR15-005 | 5th January 2015
Chin Ho Lee, Emanuele Viola

#### Some limitations of the sum of small-bias distributions

Revisions: 1

We exhibit $\epsilon$-biased distributions $D$
on $n$ bits and functions $f\colon \{0,1\}^n \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

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

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 >>> 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, Vinodchandran Variyam #### 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 Vinodchandran Variyam #### Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs. 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, Vinodchandran Variyam

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

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

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

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