The standard LP relaxation of the
asymmetric traveling salesman problem has been conjectured to have a
constant integrality gap in the metric case. We prove this conjecture
when restricted to shortest path metrics of node-weighted digraphs. Our
arguments are constructive and give a constant factor approximation
algorithm for these metrics. We remark that the considered
case is more general than the directed analog of the special case of the
symmetric traveling salesman problem for which there were recent
improvements on Christofides' algorithm. The main idea of our
approach is to first consider an easier problem obtained by
significantly relaxing the general connectivity requirements into local
connectivity conditions. For this relaxed problem, it
is quite easy to give an algorithm with a guarantee of 3 on
node-weighted shortest path metrics. More surprisingly, we then show
that any algorithm (irrespective of the metric) for the relaxed problem
can be turned into an algorithm for the asymmetric traveling
salesman problem by only losing a small constant factor in the
performance guarantee. This leaves open the intriguing task
of designing a "good" algorithm for the relaxed problem on
general metrics.
We show that the integrality gap of
the natural LP relaxation of the Asymmetric Traveling Salesman Problem
is polyloglog(n). In other words, there is a polynomial time algorithm
that approximates the value of the optimum tour within a factor of
polyloglog(n), where polyloglog(n) is a bounded degree polynomial of
loglog(n).We prove this by showing that any k-edge-connected unweighted
graph has a polyloglog(n)/k-thin spanning tree.Our main new ingredient
is a procedure, albeit an exponentially sized convex program, that
"transforms" graphs that do not admit any spectrally thin trees into
those that provably have spectrally thin trees. More precisely, given a
k-edge-connected graph G=(V,E) where k>= 7log(n),we show that there
is a matrix D that "preserves" the structure of all cuts of G
such that for a subset F of E that induces an Omega(k)-edge-connected
graph, the effective resistance of every edge in F w.r.t. D is at most
polylog(k)/k. Then, we use our recent extension of the seminal work of
Marcus, Spielman, and Srivastava [MSS13] to prove the existence of
a polylog(k)/k-spectrally thin tree with respect to D. Such a
treeis polylog(k)/k-combinatorially thin with respect to G as D
preserves the structure of cuts of G.
In this work we study the
quantitative relation between VC-dimension and two other basic
parameters related to learning and teaching. Namely, the quality of
sample compression schemes and of teaching sets for classes of low
VC-dimension. Let C be a binary concept class of size m and
VC-dimension d. Prior to this work, the best known upper
bounds for both parameters were log(m), while the best lower bounds are
linear in d. We present significantly better upper bounds on both as
follows.We construct sample compression schemes of size exp(d) for C.
This resolves a question of Littlestone and Warmuth (1986).Roughly
speaking, we show that given an arbitrary set of labeled examples from
an unknown concept in C, one can retain only a subset of exp(d) of them,
in a way that allows to recover the labels of all other examples in the
set, using additional exp(d) information bits.We further show that
there always exists a concept c in C with a teaching set (i.e. a list of
c-labeled examples uniquely identifying c in C) of size exp(d)
loglog(m). This problem was studied by Kuhlmann (1999). Our construction
also implies that the recursive teaching (RT) dimension of C is at most
exp(d) loglog(m) as well. The RT-dimension was suggested byZilles et
al. and Doliwa et al. (2010). The same notion (under the name partial-ID
width) was independently studied by Wigderson and Yehudayoff (2013). An
upper bound on this parameter that depends only on d is known just for
the very simple case d=1, and is open even for d=2. We also make small
progress towards this seemingly modest goal.
We show a directed and robust
analogue of a boolean isoperimetric type theorem of
Talagrand. As an application, wegive a monotonicity testing
algorithm that makes, up to polylog factors, (square root of
n)/epsilon^2 non-adaptive queries to a function f:{0,1}^n
-> {0,1},always accepts a monotone function and rejects a function
that is epsilon-far from being monotone with constant probability.
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping:
Classic similarity measures of strings are longest common subsequence
and Levenshtein distance (i.e., the classic edit distance). A classic
similarity measure of curves is dynamic time warping. These measures can
be computed by simple O(n^2) dynamic programming algorithms, and
despite much effort no algorithms with significantly better running time
are known. We prove that, even restricted to binary
strings or one-dimensional curves, respectively, these measures do not
have strongly subquadratic time algorithms, i.e., no algorithms with
running time O(n^{2-\eps}) for any \eps > 0, unless the Strong
Exponential Time Hypothesis fails. We generalize the result to edit
distance for arbitrary fixed costs of the four operations (deletion in
one of the two strings, matching, substitution), by identifying trivial
cases that can be solved in constant time, and proving quadratic-time
hardness on binary strings for all other cost choices. This
improves and generalizes the known hardness result for Levenshtein
distance [Backurs,Indyk STOC'15] by the restriction to binary strings
and the generalization to arbitrary costs, and adds important problems
to a recent line of research showing conditional lower bounds for a
growing number of quadratic time problems.As our main technical
contribution, we introduce a framework for proving quadratic-time
hardness of similarity measures. To apply the framework it suffices to
construct a single gadget, which encapsulates all the expressive power
necessary to emulate a reduction from
satisfiability. Finally, we prove quadratic-time hardness for
longest palindromic subsequence and longest tandem subsequence via
reductions from longest common subsequence, showing that conditional
lower bounds based on the Strong Exponential Time Hypothesis also apply
to string problems that are not necessarily similarity measures.
Tight Hardness Results for LCS and other Sequence Similarity Measures:
Two important similarity measures between sequences are the longest
common subsequence (LCS) and the dynamic time warping distance (DTWD).
The computations of these measures for two given sequences are central
tasks in a variety of applications. Simple dynamic programming
algorithms solve these tasks in O(n^2) time, and despite an extensive
amount of research, no algorithms with significantly better worst case
upper bounds are known.In this paper, we show that for any constant
epsilon>0, an O(n^(2-epsilon)) time algorithm for computing the LCS
or the DTWD of two sequences of length n over a constant size alphabet,
refutes the popular Strong Exponential Time Hypothesis (SETH).
The CFG recognition problem is:
given a context-free grammar G and a string w of length n, decide if w
can be obtained from G. This is the most basic parsing question and is a
core computer science problem. Valiant's parser from 1975 solves the
problem in O(n^omega) time, where omega is the exponent of matrix
multiplication. The best combinatorial algorithms have mildly subcubic
O(n^3/\log^3{n}) complexity. Evidence for the nonexistence of efficient
algorithms was given in a result of Lee (JACM'01), who showed that any
algorithm for a more general parsing problem with running time O(|G|
n^{3-eps}), that works even in the unusual case that |G|=Omega(n^6), can
be converted into a surprising subcubic algorithm for Boolean Matrix
Multiplication. However, nothing was known for the more relevant case of
constant size grammars. In this work, we make the first progress on the
constant size grammar case in 40 years, and prove that any improvement
on Valiant's algorithm, either in terms of runtime or by avoiding the
inefficiencies of fast matrix multiplication, would imply a breakthrough
algorithm for the k-Clique problem: given a graph of n nodes, decide if
there are k that form a clique. Besides classifying the complexity of a
fundamental problem, our reduction has led us to similar lower bounds
for more modern and well-studied cubic time problems for which faster
algorithms are highly desirable in practice: RNA Folding, a central
problem in computational biology, and Dyck Language Edit Distance,
answering an open question of Saha (FOCS'14).
Given a context free language G
over alphabet \Sigma and a string s, the language edit distance problem
seeks the minimum number of edits (insertions, deletions and
substitutions) required to convert s into a valid member of the language
L(G). The well-known dynamic programming algorithm solves this problem
in cubic time in string length [Aho, Peterson 1972, Myers
1985]. Despite its numerous applications, to date there exists no
algorithm that computes the exact or approximate language edit distance
problem in true subcubic time.In this paper we give the first such truly
sub-cubic algorithm that computes language edit distance almost
optimally. We further solve the local alignment problem; for all
substrings of s, we can estimate their language edit distance
near-optimally in same time with high probability. Next, we design the
very first subcubic algorithm that given an arbitrary stochastic context
free grammar, and a string returns a nearly-optimal maximum likelihood
parsing of that string. Stochastic context free grammars significantly
generalize hidden Markov models; they lie at the foundation of
statistical natural language processing, and have found widespread
applications in many other fields.To complement our upper bound result,
we show that exact computation of maximum likelihood parsing of
stochastic grammars or language edit distance in true subcubic time will
imply a truly subcubic algorithm for all-pairs shortest paths, a
long-standing open question. This will result in a
breakthrough for a large range of problems in graphs and matrices due to
subcubic equivalence. By a known lower bound result [Lee 2002], and a
recent development [Abboud et al. 2015] even the much simpler problem of
parsing a context free grammar requires fast matrix multiplication
time. Therefore any nontrivial multiplicative approximation algorithms
for either of the two problems in time less than matrix-multiplication
are unlikely to exist.
We show how to compute any
symmetric Boolean function on n variables over any field (as well as the
integers) with a probabilistic polynomial of degree O(sqrt(n
log(1/epsilon))) and error at most epsilon.The degree dependence on n
and epsilon is optimal, matching a lower bound of Razborov (1987) and
Smolensky (1987) for the MAJORITY function. The proof is constructive: a
low-degree polynomial can be efficiently sampled from the
distribution.This polynomial construction is combined with other
algebraic ideas to give the first subquadratic time algorithm for
computing a (worst-case) batch of Hamming distances in superlogarithmic
dimensions, exactly. To illustrate, let c(n) : N -> N. Suppose we are
given a database D of n vectors in {0,1}^(c(n) log n) and a collection
of n query vectors Q in the same dimension. For all u in Q, we wish to
compute a v in D with minimum Hamming distance from u. We solve this
problem in n^(2-1/O(c(n) log^2 c(n))) randomized time. Hence, the
problem is in ``truly subquadratic'' time for O(log n) dimensions, and
in subquadratic time for d = o((log^2 n)/(log log n)^2). We apply the
algorithm to computing pairs with maximum inner product, closest pair in
l_1 for vectors with bounded integer entries, and pairs with maximum
Jaccard coefficients.
In this paper, we consider the
following \emph{inverse maintenance problem}: given $A \in R^{n\times
d}$ and a number of rounds $r$, at round $k$, we receive a $n\times n$
diagonal matrix $D^{(k)}$ and we wish to maintain an efficient linear
system solver for $A^{T}D^{(k)}A$ under the assumption $D^{(k)}$ does
not change too rapidly. Thisinverse maintenance problem is the
computational bottleneck in solving multiple optimization problems. We
show how to solve this problem with
$\tilde{O}\left(nnz(A)+d^{\omega}\right)$ preprocessing time and
amortized $\tilde{O}(nnz(A)+d^{2})$ time per round, improving upon
previous running times.Consequently, we obtain the fastest known running
times for solving multiple problems including, linear programming,
computing a rounding of a polytope, and sampling a point in a polytope.
In particular given a feasible point in a linear program with $n$
variables, $d$ constraints, and constraint matrix $A \in R^{d\times n}$,
we show how to solvethe linear program in time
$\tilde{O}((nnz(A)+d^{2})\sqrt{d}\log(\epsilon^{-1}))$. We achieve our
results through a novel combination of classic numerical techniques of
low rank update, preconditioning, and fast matrix multiplication as well
as recent work on subspace embeddings and spectral sparsification that
we hope will be of independent interest.
We present the first almost-linear
time algorithm for constructing linear-sized spectral sparsification for
graphs. This improves all previous constructions of
linear-sized spectral sparsification, which requires $\Omega(n^2)$
time.A key ingredient in our algorithm is a novel combination of two
techniques used in literature for constructing spectral sparsification:
Random sampling by effective resistance, and adaptive constructions
based on barrier functions.
Matrix factorization is a popular
approach for large-scale matrix completion. In this approach, the
unknown low-rank matrix is expressed as the product of two much smaller
matrices so that the low-rank property is automatically fulfilled. The
resulting optimization problem, even with huge size, can be solved (to
stationary points) very efficiently through standard optimization
algorithms such as alternating minimization and stochastic gradient
descent (SGD).However, due to the non-convexity caused by the
factorization model, there is a limited theoretical understanding of
whether these algorithms will generate a good solution. In this paper,
we establish a theoretical guarantee for the factorization based
formulation to correctly recover the underlying low-rank matrix. In
particular, we show that under similar conditions to those in previous
works,many standard optimization algorithms converge to the global
optima of the factorization based formulation, and recover the true
low-rank matrix. A major difference of our work from the existing
results is that we do not need resampling (i.e., using independent
samples at each iteration) in either the algorithm or its analysis. To
the best of our knowledge, our result is the first one that provides
exact recovery guarantee for many standard algorithms such as gradient
descent, SGD and block coordinate gradient descent.
Independent component analysis
(ICA) is the problem of efficiently recovering a matrix A in R^{n times
n} from i.i.d. observations of X=AS where S in R^n is a random vector
with mutually independent coordinates.This problem has been intensively
studied, but all existing efficient algorithms with provable guarantees
require that the coordinates Si have finite fourth moments.We consider
the heavy-tailed ICA problem where we do not make this assumption, about
the second moment.This problem also has received considerable attention
in the applied literature.In the present work, we first give a provably
efficient algorithm that works under the assumption that for constant
gamma > 0$, each Si has finite (1+gamma)-moment, thus substantially
weakening the moment requirement condition for the ICA problem to be
solvable.We then give an algorithm that works under the assumption that
matrix A has orthogonal columns but requires no moment assumptions.Our
techniques draw ideas from convex geometry and exploit standard
properties of the multivariate spherical Gaussian distribution in a
novel way.
In the subspace approximation
problem, we seek a $k$-dimensional subspace $F$ of $\mathbb{R}^d$ that
minimizesthe sum of $p$-th powers of Euclidean distances to a given set
of $n$ points $a_1, \ldots, a_n \in \mathbb{R}^d$, for $p \geq 1$. More
generally than minimizing $\sum_i \dist(a_i,F)^p$,we may wish to
minimize $\sum_i M(\dist(a_i,F))$ for some loss function $M()$, for
example, $M$-Estimators, whichinclude the Huber and Tukey loss
functions. Such subspaces provide alternativesto the singular value
decomposition (SVD), which is the $p=2$ case, findingsuch an $F$ that
minimizes the sum of squares of distances. For $p \in [1,2)$,and for
typical $M$-Estimators, the minimizing $F$ gives a solution that is more
robust tooutliers than that provided by the SVD.We give several
algorithmic results for these robust subspace approximation problems.We
state our results as follows, thinking of the $n$ points as forming an
$n \times d$ matrix $A$, and letting $\nnz(A)$denote the number of
non-zero entries of $A$. Our results hold for $p\in [1,2)$.We use
$\poly(n)$ to denote $n^{O(1)}$ as
$n\rightarrow\infty$.\begin{enumerate}\item For minimizing $\sum_i
\dist(a_i,F)^p$, we give an algorithm running in\[O(\nnz(A) +
(n+d)\poly(k/\eps) + \exp(\poly(k/\eps)))\]time which outputs a
$k$-dimensional subspace $F$ whose cost is at most a $(1+\eps)$-factor
larger than the optimum.\item We show that the problem of minimizing
$\sum_i \dist(a_i, F)^p$ is NP-hard, even to output a
$(1+1/\poly(d))$-approximation. This extends work of Deshpande et al.
(SODA, 2011) which could onlyshow NP-hardness or UGC-hardness for $p
> 2$; their proofs critically rely on $p > 2$. Our work resolves
an open questionof [Kannan Vempala, NOW, 2009]. Thus, there cannot be an
algorithm running in time polynomial in $k$ and $1/\eps$ unless P =
NP.Together with prior work, this implies that the problem is NP-hard
for all $p \neq 2$. \item For loss functions for a wide class of
$M$-Estimators, we give a problem-size reduction:for a parameter
$K=(\log n)^{O(\log k)}$, our reduction takes\[O(\nnz(A)\log n +
(n+d)\poly(K/\eps))\]time to reduce the problem to a constrained version
involving matrices whose dimensionsare $\poly(K\eps^{-1}\log n)$. We
also give bicriteria solutions.\item Our techniques lead to the first
$O(\nnz(A) + \poly(d/\eps))$ time algorithms for
$(1+\eps)$-approximateregression for a wide class of convex
$M$-Estimators. This improves prior results \cite{cw15}, which were
$(1+\eps)$-approximation for Huber regression only,and
$O(1)$-approximation for a general class of
$M$-Estimators.\end{enumerate}
We show that unbounded fan-in
boolean formulas of depth d + 1 and size s have average sensitivity
O(log s/d)^d. In particular, this gives a tight 2^Ω(d(n^{1/d}−1)) lower
bound on the size of depth d + 1 formulas computing the PARITY
function. These results strengthen the corresponding O(logs)d
and 2^Ω(n^{1/d}) bounds for circuits due to Boppana (1997) and Hastad
(1986). Our proof technique studies a random process associated with
formulas, in which the Switching Lemma is efficiently applied to
subformulas.
The threshold degree of a Boolean
function f is the minimum degree of a real polynomial p that represents f
in sign: f(x)=sgn p(x). Introduced in the seminal work of Minsky and
Papert (1969), this notion is central to some of the strongest
algorithmic and complexity-theoretic results for constant-depth
circuits. One problem that has remained open for several decades, with
applications to computational learning and communication complexity, is
to determine the maximum threshold degree of a polynomial-size
constant-depth circuit in n variables. The best lower bound prior to
our work was Omega(n^((d-1)/(2d-1))) for circuits of depth d. We obtain a
polynomial improvement for every depth d, with a lower bound of
Omega(n^(3/7)) for depth 3 and Omega(n^(1/2)) for depth d>=4. The
proof contributes an approximation-theoretic technique of independent
interest, which exploits asymmetry in circuits to prove their hardness
for polynomials.
Kayal has recently introduced the
method of shifted partial derivatives as a way to give the first
exponential lower bound for computing an explicit polynomial as a sum of
powers of constant-degree polynomials. This method has
garnered further attention because of the work of Gupta, Kamath, Kayal
and Saptharishi who used this method to obtain lower bounds that
approach the "chasm at depth-4". In this work, we investigate to what
extent this method can be used to obtain deterministic polynomial
identity testing (PIT) algorithms, which are algorithms that decide
whether a given algebraic circuit computes the zero
polynomial. In particular, we give a poly(s)^(log s)-time
deterministic black-box PIT algorithm for a size-s sum of powers of
constant-degree polynomials. This is the first
sub-exponential deterministic PIT algorithm for this model of
computation and the first PIT algorithm based on the method of shifted
partial derivatives.We also study the problem of divisibility testing,
which when given multivariate polynomials f and g (as algebraic
circuits) asks to decide whether f divides g. Using
Strassen's technique for the elimination of divisions, we show that one
can obtain deterministic divisibility testing algorithms via
deterministic PIT algorithms, and this reduction does not dramatically
increase the complexity of the underlying algebraic
circuits. Using this reduction, we show that deciding
divisibility of a constant-degree polynomial f into a sparse polynomial g
reduces to PIT of sums of a monomial multiplied by a power of
constant-degree polynomials. We then extend the method of
shifted partial derivatives to give a poly(s)^(log s)-time deterministic
black-box PIT algorithm for this model of computation, and thus derive a
corresponding deterministic divisibility algorithm. This is the first
non-trivial deterministic algorithm for this problem.Previous work on
multivariate divisibility testing due to Saha, Saptharishi and Saxena
gave algorithms for when f is linear and g is sparse, and essentially
worked via PIT algorithms for read-once (oblivious) algebraic branching
programs (roABPs). We give explicit sums of powers of quadratic
polynomials that require exponentially-large roABPs in a strong sense,
showing that techniques known for roABPs have limited applicability in
our regime.Finally, by combining our results with the algorithm of
Forbes, Shpilka and Saptharishi we obtain poly(s)^(loglog s)-time
deterministic black-box PIT algorithms for various models (translations
of sparse polynomials, and sums of monomials multiplied by a power of a
linear polynomial) where only \poly(s)^(Theta(log s))-time such
algorithms were previously known.
We consider the pebble game on DAGs
with bounded fan-in introduced in [Paterson and Hewitt '70] and the
reversible version of this game in [Bennett '89], and study the question
of how hard it is to decide exactly or approximately the number of
pebbles needed for a given DAG in these games.We prove that the problem
of deciding whether s pebbles suffice to reversibly pebble a DAG G is
PSPACE-complete, as was previously shown for the standard pebble game in
[Gilbert, Lengauer and Tarjan '80]. Via two different graph product
constructions we then strengthen these results to establish that both
standard and reversible pebbling space are PSPACE-hard to approximate to
within any additive constant. To the best of our knowledge,
these are the first hardness of approximation results for pebble games
in an unrestricted setting (even for polynomial time). Also, since [Chan
'13] proved that reversible pebbling is equivalent to the games in
[Dymond and Tompa '85] and [Raz and McKenzie '99], our results apply to
the Dymond--Tompa and Raz--McKenzie games as well, and from the same
paper it follows that resolution depth is PSPACE-hard to determine up to
any additive constant.We also obtain a multiplicative logarithmic
separation between reversible and standard pebbling space. This improves
on the additive logarithmic separation previously known and could
plausibly be tight, although we are not able to prove this.We leave as
an interesting open problem whether our additive hardness of
approximation result could be strengthened to a multiplicative bound if
the computational resources are decreased from polynomial space to the
more common setting of polynomial time.
We revisit the question of
constructing secure general-purpose indistinguishability
obfuscation,with a security reduction based on explicit computational
assumptions over multilinear maps.Previous to our work, such reductions
were only known to exist based on meta-assumptions and/or ad-hoc
assumptions: In the original constructive work of Garg et al. (FOCS
2013), the underlying explicitcomputational assumption encapsulated an
exponential family of assumptions for each pair of circuits to be
obfuscated.In the more recent work of Pass et al. (Crypto 2014), the
underlying assumption is a \emph{meta-assumption} thatalso encapsulates
an exponential family of assumptions, and this meta-assumption is
invoked in a manner thatcaptures the specific pair of circuits to be
obfuscated. The assumptions underlying both these works
substantiallycapture (either explicitly or implicitly) the actual
structure of the obfuscation mechanism itself.In our work, we provide
the first construction of general-purpose indistinguishability
obfuscationproven secure via a reduction to a natural computational
assumption overmultilinear maps, namely, the Multilinear Subgroup
Elimination Assumption.This assumption does not depend on the circuits
to be obfuscated (except for its size),and does not correspond to the
underlying structure of our obfuscator. The technical heart of our
paperis our reduction, which gives a new way to argue about the security
of indistinguishability obfuscation.
Indistinguishability obfuscation
(IO) is a tremendous notion, powerful enough to give rise to almost any
known cryptographic object. So far, candidate IO constructions were
based on specific assumptions on algebraic objects called multi-linear
graded encodings.We present a generic construction of
indistinguishability obfuscation from public-key functional encryption
with succinct ciphertexts and sub-exponential security. This shows the
equivalence of indistinguishability obfuscation and public-key
functional encryption, a primitive that has so far seemed to be much
weaker, lacking the power and the staggering range of applications of
indistinguishability obfuscation.As an application, we obtain a new
candidate IO construction based on the functional encryption scheme of
Garg, Gentry, Halevi, and Zhandry [Eprint 14] under their assumptions on
multi-linear graded encodings. We also show that, under the Learning
with Errors assumptions, our techniques imply that any
indistinguishability obfuscator can be converted to one where obfuscated
circuits are of linear size in the size of the original circuit plus a
polynomial overhead in its depth.Our reduction highlights the importance
of ciphertext succinctness in functional encryption schemes, which we
hope will serve as a pathway to new IO constructions based on solid
cryptographic foundations.
Recent breakthroughs in
cryptography have positioned indistinguishability obfuscation as a
"central hub" for almost all known cryptographic tasks, and as an
extremely powerful building block for new cryptographic tasks resolving
long-standing and foundational open problems. However, constructions
based on indistinguishability obfuscation almost always rely on
non-black-box techniques, and thus the extent to which it can be used as
a building block in cryptographic constructions has been completely
unexplored so far.We present a framework for proving meaningful negative
results on the power of indistinguishability obfuscation. By
considering indistinguishability obfuscation for oracle-aided circuits,
we capture the common techniques that have been used so far in
constructions based on indistinguishability obfuscation. These include,
in particular, non-black-box techniques such as the punctured
programming approach of Sahai and Waters (STOC '14) and its variants, as
well as sub-exponential security assumptions.Within our framework we
prove the first negative results on the power of indistinguishability
obfuscation and of the tightly related notion of functional encryption.
Our results are as follows:-- There is no fully black-box construction
of a collision-resistant function family from an indistinguishability
obfuscator for oracle-aided circuits.-- There is no fully black-box
construction of a key-agreement protocol with perfect completeness from a
private-key functional encryption scheme for oracle-aided
circuits.Specifically, we prove that any such potential constructions
must suffer from an exponential security loss, and thus our results
cannot be circumvented using sub-exponential security assumptions. Our
framework captures constructions that may rely on a wide variety of
primitives in a non-black-box manner (e.g., obfuscating or generating a
functional key for a function that uses the evaluation circuit of a
puncturable pseudorandom function), and we only assume that the
underlying indistinguishability obfuscator or functional encryption
scheme themselves are used in a black-box manner.
Garbled RAM, introduced by Lu and
Ostrovsky, enables the task of garbling a RAM (Random Access Machine)
program directly, there by avoiding the inefficient process of first
converting it into a circuit. Garbled RAM can be seen as a RAM analogue
of Yao's garbled circuit construction, except that known realizations of
Garbled RAM make non-black-box use of the underlying cryptographic
primitives.In this paper we remove this limitation and provide the first
black-box construction of Garbled RAM with polylogarithmic overhead.
Our scheme allows for garbling multiple RAM programs being executed on a
persistent database and its security is based only on the existence of
one-way functions. We also obtain the first secure RAM computation
protocol that is both constant round and makes only black-box use of
one-way functions in the Oblivious Transfer hybrid model.
Theoretical study of optimization
problems in wireless communication often deals with zero-dimensional
tasks.For example, the power control problem requires computing a power
assignmentguaranteeing that each transmitting station is
successfullyreceived at a single receiver point.This paper aims at
addressing communication applications that require handling
2-dimensional tasks (e.g., guaranteeing successful transmission inentire
regions rather than in specific points).A natural approach to such
tasks is to discretize the $2$-dimensional optimization domain, e.g., by
sampling points within the domain.This approach, however, might incur
high time and memory requirements,and moreover, it cannot guarantee
exact solutions.Towards this goal, we establish the minimum principle
for the SINRfunction with free-space path loss (i.e., when the signal
decays in proportion to the square of the distance between the
transmitter and receiver).We then utilize it as a discretization
technique for solvingtwo-dimensional problems in the SINR model.This
approach is shown to be useful for handling optimization problems over
two dimensions (e.g., power control, energy minimization);in providing
tight bounds on the number of null-cells in the reception map;and in
approximating geometrical and topological propertiesof the wireless
reception map (e.g., maximum inscribed sphere).Essentially, the minimum
principle allows us to reduce the dimensionof the optimization domain
without losing anything in the accuracyor quality of the solution.More
specifically, when the two dimensional optimization domain is bounded
and free from any interfering station, the minimum principle implies
thatit is sufficient to optimize over the boundary of the domain,as the
``hardest" points to be satisfied reside on boundaryand not in the
interior.We believe that the minimum principle, as well as the interplay
betweencontinuous and discrete analysis presented in this paper,may
pave the way to future study of algorithmic SINR in higher dimensions.
Motivated by the need for designing
efficient and robust fully-distributed computation in highly
dynamic networks such as Peer-to-Peer (P2P) networks, we study
distributed protocols for constructing and maintaining
dynamic network topologies with good expansion properties. Our goal is
to maintain a sparse (bounded degree) expander
topology despite heavy churn (i.e.,
nodes joining and leaving the network continuously over
time). We assume that the churn is controlled by
an adversary that has complete knowledge and
control of what nodes join and leave and at what
time and has unlimited computational power, but
is oblivious to the random choices made by the
algorithm. Our main contribution is a randomized distributed
protocol that guarantees with high probability the
maintenance of a constant degree graph with high
expansion even under continuous high adversarial churn. Our
protocol can tolerate a churn rate ofup to O(n/polylog(n))
per round (where n is the stable network size). Ourprotocol
is efficient, lightweight, and scalable, and it incurs
onlyO(polylog(n)) overhead for topology
maintenance: only polylogarithmic(in
n) bits needs to be processed and sent by each
node per round and anynode's computation cost per round is also
polylogarithmic. The given protocolis a fundamental
ingredient that is needed for the design of efficientfully-distributed
algorithms for solving fundamental distributed computingproblems such as
agreement, leader election, search, and storage in
highlydynamic P2P networks and enables fast and scalable algorithms for
theseproblems that can tolerate a large amount of churn.
We show how to represent a planar
digraph in linear space so that reachability queries can be answered in
constant time. The data structure can be constructed in linear time.
This representation of reachability is thus optimal in both time and
space, and has optimal construction time. The previous bestsolution used
O(n log n) space for constant query time [Thorup FOCS’01].
We describe a fully dynamic
linear-space data structure for point location in connected planar
subdivisions, or more generally vertical ray shooting among
non-intersecting line segments, that supports queries in $O(\log
n(\log\log n)^2)$ time and updates in $O(\log n\log\log n)$ time. This
is the first data structure that achieves close to logarithmic query and
update time simultaneously, ignoring $\log\log n$ factors. We further
show how to reduce the query time to $O(\log n\log\log n)$ in the RAM
model with randomization. Alternatively, the query time can be lowered
to $O(\log n)$ if the update time is increased to
$O(\log^{1+\varepsilon}n)$ for any constant $\varepsilon>0$, or vice
versa.
The dynamic optimality conjecture
is perhaps the most fundamental open question about binary search trees
(BST). It postulates the existence of an asymptotically optimal online
BST, i.e. one that is constant factor competitivewith any BST on any
input access sequence. The two main candidates for dynamic optimality in
the literature are splay trees [Sleator and Tarjan, 1985], and Greedy
[Lucas, 1988; Munro, 2000; Demaine et al. 2009]. Despite BSTsbeing among
the simplest data structures in computer science, and despite extensive
effort over the past three decades, the conjecture remains elusive.
Dynamic optimality is trivial for almost all sequences: the optimum
access cost of most length-n sequences is Theta(n log n), achievable by
any balanced BST. Thus, the obvious missing step towards the conjecture
is an understanding of the “easy” access sequences, and indeed the most
fruitful research direction so far has been the study of specific
sequences, whose “easiness” is captured by a parameter of interest. For
instance, splay provably achieves the bound of O(nd) when d roughly
measures the distances between consecutive accesses (dynamic finger),
the average entropy (static optimality), or the delays between multiple
accesses of an element (working set). The difficulty of proving dynamic
optimality is witnessed by other highly restricted special cases that
remain unresolved; one prominent example is the traversal conjecture
[Sleator and Tarjan, 1985], which states that preorder sequences (whose
optimum is linear) are linear-time accessed by splay trees; no online
BST is known tosatisfy this conjecture.In this paper, we prove two
different relaxations of the traversal conjecture for Greedy: (i) Greedy
is almost linear for preorder traversal, (ii) if a linear-time
preprocessing is allowed, Greedy is in fact linear. These statementsare
corollaries of our more general results that express the complexity of
access sequences in terms of a pattern avoidance parameter k. Pattern
avoidance is a well-established concept in combinatorics, and the
classes of input sequences thus defined are rich, e.g. the k = 3 case
includes preorder sequences. For any sequence X with parameter k, our
most general result shows that Greedy achieves the cost
n*2^(alpha(n))^O(k) where alpha is the inverse Ackermann function.
Furthermore, a broad subclass of parameter-k sequences has a natural
combinatorial interpretation as k-decomposable sequences. For this class
of inputs, we obtain an n*2^O(k) bound for Greedy when preprocessing is
allowed. For k = 3, these results imply (i) and (ii). To our knowledge,
these are the first upper bounds for Greedy that are not known to hold
for any other online BST. To obtain these results we identify an
input-revealing property of Greedy. Informally, this means that the
execution log partially reveals the structure of the access sequence.
This property facilitates the use of rich technical tools from forbidden
submatrix theory.Further studying the intrinsic complexity of
k-decomposable sequences, we make several observations. First, in order
to obtain an offline optimal BST, it is enough to bound Greedy on
non-decomposable access sequences.Furthermore, we show that the optimal
cost for k-decomposable sequences is Theta(n log k), which is well below
the proven performance of all known BST algorithms. Hence, sequences in
this class can be seen as a "candidatecounterexample" to dynamic
optimality.
During the last decade, the matroid
secretary problem (MSP) became one of the most prominent classes of
online selection problems. The interest in MSP is twofold: on the one
hand, there are many interesting applications of MSP; and on the other
hand, there is strong hope that MSP admits O(1)-competitive algorithms,
which is the claim of the well-known matroid secretary conjecture.
Partially linked to its numerous applications in mechanism design,
substantial interest arose also in the study of nonlinear versions of
MSP, with a focus on the submodular matroid secretary problem (SMSP).
The fact that submodularity captures the property of diminishing
returns, a very natural property for valuation functions, is a key
reason for the interest in SMSP. So far, O(1)-competitive algorithms
have been obtained for SMSP over some basic matroid classes. This
created some hope that, analogously to the matroid secretary conjecture,
one may even obtain O(1)-competitive algorithms for SMSP over any
matroid. However, up to now, most questions related to SMSP remained
open, including whether SMSP may be substantially more difficult than
MSP; and more generally, to what extend MSP and SMSP are related.Our
goal is to address these points by presenting general black-box
reductions from SMSP to MSP. In particular, we show that any
O(1)-competitive algorithm for MSP, even restricted to a particular
matroid class, can be transformed in a black-box way to an
O(1)-competitive algorithm for SMSP over the same matroid class. This
implies that the matroid secretary conjecture is equivalent to the same
conjecture for SMSP. Hence, in this sense SMSP is not harder than MSP.
Also, to find O(1)-competitive algorithms for SMSP over a particular
matroid class, it suffices to consider MSP over the same matroid class.
Using our reductions we obtain many first and improved O(1)-competitive
algorithms for SMSP over various matroid classes by leveraging known
algorithms for MSP. Moreover, our reductions imply an
O(loglog(rank))-competitive algorithm for SMSP, thus, matching the
currently best asymptotic algorithm for MSP, and substantially improving
on the previously best O(log(rank))-competitive algorithm for SMSP.
Many scheduling problems can be
viewed as allocating rates to jobs, subject to convex packing
constraints on the rates. In this paper, we consider the problem of rate
allocation when jobs of unknown size arrive online (non-clairvoyant
setting), with the goal of minimizing weighted delay or flow time.
Though this problem has strong lower bounds on competitive ratio in its
full generality, we show positive results for natural and fairly broad
sub-classes. More specifically, the subclasses we consider not only
generalize several well-studied models such as scheduling with speedup
curves and related machine scheduling, but also capture as
special cases hitherto unstudied scheduling problems such as routing
multi-commodity flows, routing multicast (video-on-demand) trees,
and multi-dimensional resource allocation. We establish
several first positive results by making connections with two disparate
disciplines: Economics and Queueing theory. First, we view the
instantaneous allocation of rates as a resource allocation problem. We
analyze the natural proportional fairness algorithm from economics. To
do this, we extend results from market clearing literature, particularly
the Eisenberg-Gale markets and the notions of Walrasian equilibria and
Gross Substitutes. This yields the first constant competitive algorithm
with constant speed augmentation for single-sink flow routing, routing
multicast trees, and multidimensional resource allocation with
substitutes resources. Next, we consider the general scheduling problem
with packing constraints on rates, but with the restriction that the
number of different {\em job types} is fixed. We model this problem as a
non-stochastic queueing problem. We generalize a natural algorithm from
queueing literature and analyze it by extending queueing theoretic
ideas. We show that the competitive ratio, for any constant speed,
depends polynomially only on the number of job types. Further, such a
dependence on the number of job types is unavoidable for non-clairvoyant
algorithms. This yields the first algorithm for scheduling
multicommodity flows whose competitive ratio depends polynomially on the
size of the underlying graph, and not on the number of jobs.
Modern data centers face a key
challenge of effectively serving user requests that arrive online. Such
requests are inherently multi-dimensional and characterized by demand
vectors over multiple resources such as processor cycles, storage space,
and network bandwidth. Typically, different resources require different
objectives to be optimized, and Lr norms of loads are among the most
popular objectives considered. Furthermore, the server clusters are also
often heterogeneous making the scheduling problem more challenging.To
address these problems, we consider the online vector scheduling problem
in this paper. Introduced by Chekuri and Khanna (SIAM J. of Comp.
2006), vector scheduling is a generalization of classical load
balancing, where every job has a vector load instead of a scalar load.
The scalar problem, introduced by Graham in 1966, and its many variants
(identical and unrelated machines, makespan and Lr-norm optimization,
offline and online jobs, etc.) have been extensively studied over the
last 50 years. In this paper, we resolve the online complexity of the
vector scheduling problem and its important generalizations — for all Lr
norms and in both the identical and unrelated machines settings. Our
main results are:• For identical machines, we show that the optimal
competitive ratio is Θ(log d/ log log d) by giving an online lower bound
and an algorithm with an asymptotically matching competitive ratio. The
lower bound is technically challenging, and is obtained via an online
lower bound for the minimum mono-chromatic clique problem using a novel
online coloring game and randomized coding scheme. Our techniques also
extend to asymptotically tight upper and lower bounds for general Lr
norms.• For unrelated machines, we show that the optimal competitive
ratio is Θ(log m + log d) by giving an online lower bound that matches a
previously known upper bound. Unlike identical machines, however,
extending these results, particularly the upper bound, to general Lr
norms requires new ideas. In particular, we use a carefully constructed
potential function that balances the individual Lr objectives with the
overall (convexified) min-max objective to guide the online algorithm
and track the changes in potential to bound the competitive ratio.
We present the first non-trivial
online algorithms for the non-uniform, multicommodity buy-at-bulk
(MC-BB) network design problem. Our competitive ratios qualitatively
match the best known approximation factors for the corresponding offline
problems. In particular, we show:1. A polynomial time online
algorithm with a poly-logarithmic competitive ratio for the MC-BB
problem in undirected edge-weighted graphs.2. A quasi-polynomial time
online algorithm with a poly-logarithmic competitive ratio for the MC-BB
problem in undirected node-weighted graphs.3. For any fixed epsilon
> 0, a polynomial time online algorithm with a competitive
ratio of O(k^{1/2+epsilon} polylog(n)) (where k is the number of
demands) for MC-BB in directed graphs.4. Algorithms with matching
competitive ratios for the prize-collecting variants of all the above
problems.Prior to our work, a logarithmic competitive ratio wasknown for
undirected, edge-weighted graphs only for the special case of uniform
costs (Awerbuch and Azar,FOCS 1997), and a polylogarithmic competitive
ratio was known for the edge-weighted single-sink problem (Meyerson,
SPAA 2004). To the best of our knowledge, no previous online algorithm
was known, even for uniform costs, in the node-weighted and directed
settings. Our main engine for the results above is an online reduction
theorem of MC-BB problems to their single-sink (SS-BB) counterparts. We
use the concept of junction-tree solutions (Chekuri et al., FOCS 2006)
that play an important role in solving the offline versions of the
problem via a greedy subroutine -- an inherently offline procedure. Our
main technical contribution is in designing an online algorithm using
only the existence of good junction-trees to reduce an MC-BB instance to
multiple SS-BB sub-instances. Along the way, we also give the first
non-trivial online node-weighted/directed single-sink buy-at-bulk
algorithms. In addition to the new results, our generic reduction also
yields new proofs of recent results for the online node-weighted Steiner
forest and online group Steiner forest problems.
We give a 2^{n+o(n)}-time and space
randomized algorithm for solving the exact Closest Vector Problem (CVP)
on n-dimensional Euclidean lattices. This improves on the
previous fastest algorithm, the deterministic \tilde{O}(4^n)-time and
\tilde{O}(2^n)-space algorithm of Micciancio and Voulgaris.We achieve
our main result in three steps. First, we show how to modify the
sampling algorithm due to Aggarwal, Dadush, Regev, and
Stephens-Davidowitz (ADRS) to solve the problem of discrete Gaussian
sampling over lattice shifts, L-t, with very low parameters. While the
actual algorithm is a natural generalization of ADRS, the analysis uses
substantial new ideas. This yields a 2^{n+o(n)}-time algorithm for
approximate CVP with the very good approximation factor \gamma =
1+2^{-o(n/\log n)}. Second, we show that the approximate
closest vectors to a target vector can be grouped into
"lower-dimensional clusters," and we use this to obtain a recursive
reduction from exact CVP to a variant of approximate CVP that "behaves
well with these clusters." Third, we show that our discrete Gaussian
sampling algorithm can be used to solve this variant of approximate
CVP.The analysis depends crucially on some new properties of the
discrete Gaussian distribution and approximate closest vectors, which
might be of independent interest.
In recent years, a number of works
have studied methods for computing the Fourier
transform in sublinear time if the output
is sparse. Most of these have focused
on the discrete setting, even though in many
applications the input signal is continuous
and naive discretization significantly worsens
the sparsity level. We present an algorithm for
robustly computing sparse Fourier transforms in
the continuous setting. Let $x(t) = x^*(t) +
g(t)$, where $x^*$ has a $k$-sparse Fourier
transform and $g$ is an arbitrary noise
term. Given sample access to $x(t)$ for
some duration $T$, we show how to find a
$k$-Fourier-sparse reconstruction $x'(t)$
with \[ \frac{1}{T}\int_0^T
\abs{x'(t) - x(t)}^2 \mathrm{d} t \lesssim \frac{1}{T}\int_0^T
\abs{g(t)}^2
\mathrm{d}t. \] The sample
complexity is linear in $k$ and logarithmic in
the signal-to-noise ratio and the frequency
resolution. Previous results with
similar sample complexities could not tolerate
an infinitesimal amount of i.i.d. Gaussian noise,
and even algorithms with higher sample
complexities increased the noise by a polynomial
factor. We also give new results for how precisely
the individual frequencies of $x^*$ can be
recovered.
The algorithmic tasks of computing
the Hamming distance between a given pattern P of length m and each
location in a text T of length n is one of the most fundamental
algorithmic tasks in string algorithms. Karloff [IPL 1999] showed that
if one is willing to suffer a 1+epsilon approximation, then it is
possible to solve the problem with high probability, in O~(n/epsilon^2)
time.Due to related lower bounds for computing the Hamming distance of
two strings in the one-way communication complexity model, it is
strongly believed that obtaining an algorithm for solving the
approximation version cannot be done much faster as a function of
1/epsilon. We show here that this belief is false by introducing a new
O~(n/epsilon) time algorithm that succeeds with high probability.The
main idea behind our algorithm, which is common in sparse recovery
problems, is to reduce the variance of a specific randomized experiment
by (approximately) separating heavy hitters from non-heavy hitters.
However, while known sparse recovery techniques work very well on
vectors, they do not seem to apply here, where we are dealing
withmismatches between pairs of characters.We introduce two main
algorithmic ingredients. The first is a new sparse recovery method that
applies for pair inputs (such as in our setting). The second is a new
construction of hash/projection functions, for which have whichallows us
to count the number of projections that induce mismatchesbetween two
characters exponentially faster than brute force. We expect that these
algorithmic techniques will be of independent interest.
We consider the problem of
estimating the number of triangles in a graph. This problem has been
extensively studied in both theory and practice,
but all existing algorithms read the entire graph. In this work we
design a {\em sublinear-time\/} algorithm for approximating the number
of triangles in a graph, where the algorithm is given query access to
the graph. The allowed queries are degree queries, vertex-pair queries
and neighbor queries. We show that for any given
approximation parameter 0\textless epsilon\textless1, the algorithm
provides an estimate hat\{t\} such that with high constant probability,
(1-epsilon) t\textless hat\{t\}\textless(1+epsilon)t, where t is the
number of triangles in the graph G. The expected query complexity of the
algorithm is O(n/t\textasciicircum \{1/3\} + min \{m,
m\textasciicircum\{3/2\}/t\}) poly(log n, 1/epsilon), where n
is the number of vertices in the graph and m is the number of edges,
and the expected running time is (n/t\textasciicircum \{1/3\} +
m\textasciicircum\{3/2\}/t) poly(log n, 1/epsilon). We also
prove that Omega(n/t\textasciicircum \{1/3\} + min \{m,
m\textasciicircum\{3/2\}/t\}) queries are necessary,
thus establishing that the query complexity of this algorithm
is optimal up to polylogarithmic factors in n (and the dependence on
1/epsilon).
Network interdiction problems are a
natural way to study the sensitivity of a network optimization problem
with respect to the removal of a limited set of edges or vertices. One
of the oldest and best-studied interdiction problems is minimum spanning
tree (MST) interdiction. Here, an undirected multigraph with
nonnegative edge weights and positive interdiction costs on its edges is
given, together with a positive budget B. The goal is to find a subset
of edges R, whose total interdiction cost does not exceed B, such that
removing R leads to a graph where the weight of an MST is as large as
possible. Frederickson and Solis-Oba (SODA 1996) presented an O(log
m)-approximation for MST interdiction, where m is the number of edges.
Since then, no further progress has been made regarding approximations,
and the question whether MST interdiction admits an O(1)-approximation
remained open.We answer this question in the affirmative, by presenting a
14-approximation that overcomes two main hurdles that hindered further
progress so far. Moreover, based on a well-known 2-approximation for the
metric traveling salesman problem (TSP), we show that our
O(1)-approximation for MST interdiction implies an O(1)-approximation
for a natural interdiction version of metric TSP.
We describe algorithms for the
problem of minimum distortion embeddings of finite metric spaces into
the real line (or a finite subset of the line). The time complexities of
our algorithms are parametrized by the values of the minimum
distortion, $\delta$, and the spread, $\Delta$, of the point set we are
embedding.We consider the problem of finding the minimum distortion
bijection between two finite subsets of the Euclidean line. This problem
was known to have an exact polynomial time solution when $\delta$ is
below a specific small constant, and hard to approximate within a factor
of $\delta^{1-\epsilon}$, when $\delta$ is polynomially large. Let $D$
be the largest adjacent pair distance, a value potentially much smaller
than $\Delta$. Then we provide a $\delta^{O(\delta^2 \log^2 D)}
n^{O(1)}$ time exact algorithm for this problem, which in particular
yields a quasipolynomial running time for constant $\delta$, and
polynomial $D$.For the more general problem of embedding any finite
metric space $(X,d_X)$ into a finite subset of the line, $Y$, we provide
a $\Delta^{O(\delta^2)} (mn)^{O(1)}$ time $O(1)$-approximation
algorithm (where $|X|=n$ and $|Y|=m$), which runs in polynomial time
provided $\delta$ is a constant and $\Delta$ is polynomial. This in turn
allows us to get a $\Delta^{O(\delta^2)} (n)^{O(1)}$ time
$O(1)$-approximation algorithm for embedding $(X,d_X)$ into the
continuous real line.
A single-sink {\em confluent flow}
is a routing of multiple demands to a sink $r$ such thatany
flow exiting a node $v$ must use a single arc. Hence, a confluent flow
routes on a tree within the network.In uncapacitated (or
uniform-capacity) networks, there is an O(1)-approximation algorithm for
demand maximizationand a logarithmic approximation algorithm for
congestion minimization (Chen et al.).We study the case of capacitated
networks, where each node $v$ has its own capacity $\mu(v)$.Indeed, it
was recently shown that demand maximization is inapproximable to within
polynomial factorsin capacitated networks (Shepherd and Vetta). We
circumvent this lower bound in two ways.First, we prove that there is a
polylogarithmicapproximation algorithm fordemand maximization in
networks that satisfy the ubiquitous {\em no-bottleneck assumption}
(nba).Second, we show a bicriteria result for capacitated
networkswithout the \nba: there is a polylog factorapproximation
guarantee fordemand maximization provided we allow congestion 2.We model
the capacitated confluent flows problem using a multilayer linear
programming formulation.At the heart of our approach for demand
maximization is a rounding procedure for flows on multilayer
networkswhich can be viewed as a proposal algorithm for an
extension of stable matchings.In addition, the demand maximization
algorithms require, as a subroutine, an algorithm forapproximate
congestion minimization in a special class of capacitated networks that
may be of independentinterest. Specifically, we present apolylogarithmic
approximation algorithm forcongestion minimization in monotonic
networks -- those networks with theproperty that $\mu(u) \le \mu(v)$ for
each arc $(u,v)$.
It has long been known that
d-dimensional Euclidean point sets admit (1+ε)-stretch spanners with
lightness W_E = (1/ε)^O(d), that is the total edge weight is at most W_E
times the weight of the minimum spanning tree of theset [DHN93].
Whether or not a similar result holds for metric spaces with low
doubling dimension has remainedan open problem. In this paper, we
resolve the question in the affirmative, and show that doubling spaces
admit(1 + ε)-stretch spanners with lightness WD = (ddim /ε)O(ddim).
We introduce and construct a
pseudorandom object which we call a local correlation breaker (LCB).
Informally speaking, an LCB is a function that gets as input a sequence
of r (arbitrarily correlated) random variables and an independent
weak-source. The output of the LCB is a sequence of r random variables
with the following property. If the i'th input random variable is
uniform then the i'th output variable is uniform even given a bounded
number of any other output variables. That is, an LCB uses the
weak-source to break local correlations between random variables. Our
construction of LCBs has applications to three-source extractors,
mergers with weak-seeds, and a variant of non-malleable extractors, that
we introduce.
We continue the study of
constructing explicit extractors for independent general weak random
sources. The ultimate goal is to give a construction that matches what
is given by the probabilistic method --- an extractor for two
independent n-bit weak random sources with min-entropy as small as log
n+O(1). Previously, the best known result in the two-source case is an
extractor by Bourgain {Bourgain05}, which works for min-entropy 0.49n;
and the best known result in the general case is an earlier work of the
author {Li13b}, which gives an extractor for a constant number of
independent sources with min-entropy polylog(n). However, the constant
in the construction of {Li13b} depends on the hidden constant in the
best known seeded extractor, and can be large; moreover the error in
that construction is only 1/poly(n).In this paper, we make two important
improvements over the result in {Li13b}. First, we construct an
explicit extractor for three independent sources on n bits with
min-entropy k >= polylog(n). In fact, our extractor works for one
source with poly-logarithmic min-entropy and another independent block
source with two blocks each having poly-logarithmic min-entropy. This
significantly improves previous constructions, and the next step would
be to break the 0.49n barrier in two-source extractors. Second, we
improve the error of the extractor from 1/poly(n) to 2^{-k^{Omega(1)}},
which is almost optimal and crucial for cryptographic applications. Some
of our techniques may be of independent interests.
We prove a new asymptotic expansion
in the central limit theorem for sums of discrete independent random
variables. The classical central limit theorem asserts that if Xi is a
sequence of n i.i.d. random variables, then S= sum Xi converges to a
Gaussian whose first two momentsmatch those of S. Further, the rate of
convergence is 1/n^0.5Roughly speaking, asymptotic expansions of the
central limit theorem show that by considering a family of limiting
distributions specified by k moments (k=2 corresponds toGaussians) and
matching the first k moments of S to such a limiting distribution, one
can achieve a convergence of n^-(k-1)/2. While such asymptotic
expansions have been known since Cramer, they did not apply to discrete
and non-identical random variables. Further, the error bounds in nearly
all cases was non-explicit (in their dependence on Xi), thus limiting
their applicability. In this work, we prove a new asymptotic expansions
of the central limit theoremwhich applies to discrete and non-identical
random variables and the error bounds are fully explicit.Given the wide
applicability of the central limit theorem in probability theory and
theoretical computer science, we believe that this new asymptotic
expansion theorem will beapplicable in several settings. As a main
application in this paper, we give an application in derandomization:
Namely, we construct PRGs for the class of combinatorial sums, a class
of functions first studied by [GMRZ13] and which generalize many
previously studied classes such as combinatorial rectangles,
small-biased spaces and modular sums among others. A function f is said
to be a combinatorial sum if there exists functions f1, .., fn mapping
to Boolean outputs such that f(x1, ..., xn) =f1(x1) +.. +
fn(xn). For this class, we give a seed length of O(log m +
log^1.5(n/epsilon)), thus improving upon previous results.
We present a new approach to
constructing unconditional pseudorandom generators against classes of
functions that involve computing a linear function of the inputs. We
give an explicit construction of a pseudorandom generator that fools the
discrete Fourier transforms of linear functions with seed-length that
is nearly logarithmic (up to polyloglog factors) in the input size and
the desired error parameter. Our result gives a single pseudorandom
generator that fools several important classes of tests computable in
logspace that have been considered in the literature, including
halfspaces (over general domains), modular tests and combinatorial
shapes. For all these classes, our generator is the first that achieves
near logarithmic seed-length in both the input length and the error
parameter. Getting such a seed-length is a natural challenge in its own
right, which needs to be overcome in order to derandomize RL — a central
question in complexity theory.Our construction combines ideas from a
large body of prior work, ranging from a classical construction of [1]
to the recent gradually increasing independence paradigm of [2]–[4],
while also introducing some novel analytic machinery which might find
other applications.
Submodular and fractionally
subadditive (or equivalently XOS) functions play a fundamental role in
combinatorial optimization, algorithmic game theory and machine
learning. Motivated by learnability of these classes of functions from
random examples, we consider the question of how well such functions can
be approximated by low-degree polynomials in L_2 norm over the uniform
distribution. This question is equivalent to understanding of the
concentration of Fourier weight on low-degree coefficients, a central
concept in Fourier analysis. We show that 1. For any
submodular function f:{0,1}^n -> [0,1], there is a polynomial of
degree O(log (1/epsilon) / epsilon^{4/5}) approximating f within epsilon
in L_2, and there is a submodular function that requires degree
Omega(1/epsilon^{4/5}). 2. For any XOS function f:{0,1}^n
-> [0,1], there is a polynomial of degree O(1/epsilon) and there
exists an XOS function that requires degree
Omega(1/epsilon). This improves on previous approaches that
all showed an upper bound of O(1/epsilon^2) for submodular and XOS
functions. The best previous lower bound was Omega(1/epsilon^{2/3}) for
monotone submodular functions. Our techniques reveal new structural
properties of submodular and XOS functions and the upper bounds lead to
nearly optimal PAC learning algorithms for these classes of functions.
We prove an average-case depth
hierarchy theorem for Boolean circuits over the standard basis of AND,
OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2,
there is an explicit n-variable Boolean function f, computed by a
linear-size depth-d formula, which is such that any depth-(d − 1)
circuit that agrees with f on (1/2 + o^n(1)) fraction of all inputs must
have size exp(n^Ω(1/d)). This answers an open question posed by Hastad
in his Ph.D. thesis [Has86b].Our average-case depth hierarchy theorem
implies that the polynomial hierarchy is infinite relative to a random
oracle with probability 1, confirming a conjecture of Hastad [Has86a],
Cai [Cai86], and Babai [Bab87]. We also use our result to show that
there is no “approximate converse” to the results of Linial, Mansour,
Nisan [LMN93] and Boppana [Bop97] on the total influence of
constant-depth circuits, thus answering a question posed by Kalai
[Kal12] and Hatami [Hat14].A key ingredient in our proof is a notion of
random projections which generalize random restrictions.
In this paper we improve upon the
running time for finding a point in a convex set given a separation
oracle. In particular, given a separation oracle for a convex set
$K\subset\mathbb{R}^{n}$ that is contained in a box of radius $R$ we
show how to either compute a point in $K$ or prove that $K$ does not
contain a ball of radius $\epsilon$ using an expected
$O(n\log(nR/\epsilon))$ evaluations of the oracle and additional time
$O(n^{3}\log^{O(1)}(nR/\epsilon))$. This matches the oracle complexity
and improves upon the $O(n^{\omega+1}\log(nR/\epsilon))$ additional time
of the previous fastest algorithm achieved over 25 years ago by Vaidya
for the current value of the matrix multiplication constant $\omega
We prove a superlogarithmic lower
bound on the conondeterministic communication complexity of the Clique
vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS
1991). As a corollary, this implies superpolynomial lower bounds for the
Alon--Saks--Seymour conjecture in graph theory. Our approach is to
first exhibit a query complexity separation for the decision tree
analogue of the UP vs. coNP question---namely, unambiguous DNF width vs.
CNF width---and then "lift" this separation over to communication
complexity using a result from prior work.
We prove new upper and lower bounds
on the sample complexity of (epsilon, delta) differentially private
algorithms for releasing approximate answers to threshold functions. A
threshold function c_x over a totally ordered domain X evaluates to
c_x(y) = 1 if y = Omega(log^∗ |X|), which grows with the size of the
domain. Inspired by the techniques used to prove this lower bound, we
give an algorithm for releasing thresholds with n = Omega(l \cdot log^∗
|X|).To obtain our results, we give reductions in both directions from
releasing and properly learning thresholds and the simpler interior
point problem. Given a database D of elements from X, the interior point
problem asks for an element between the smallest and largest elements
in D. We introduce new recursive constructions for bounding the sample
complexity of the interior point problem, as well as further reductions
and techniques for proving impossibility results for other basic
problems in differential privacy.
The privacy risks inherent in the
release of a large number of summary statistics were illustrated by
Homer et al. (PLoS Genetics, 2008), who considered the case of 1-way
marginals of SNP allele frequencies obtained in a genome-wide
association study: Given a large number of minor allele frequencies from
a case group of individuals diagnosed with a particular disease,
together with the genomic data of a single target individual and
statistics from a sizable reference dataset independently drawn from the
same population, an attacker can determine with high confidence whether
or not the target is in the case group. In this work we describe and
analyze a simple attack that succeeds even if the summary statistics are
significantly distorted, whether due to measurement error or noise
intentionally introduced to protect privacy. Our attack only
requires that the vector of distorted summary statistics is close to the
vector of true marginals in L1 norm. Moreover, the reference
pool required by previous attacks can be replacedby a single sample
drawn from the underlying population. The new attack, which is not
specific to genomics and which handles Gaussian as well as Bernouilli
data, significantly generalizes recent lower bounds on the noise needed
to ensure differential privacy (Bun, Ullman, and Vadhan, STOC 2014;
Steinke and Ullman, 2015), obviating the need for the attacker to
control the exact distribution of the data.
New phase transition phenomena have
recently been discovered for the stochastic block model, for the
special case of two non-overlapping symmetric communities. This gives
raise in particular to new algorithmic challenges driven by the
thresholds. This paper investigates whether a general phenomenon takes
place for multiple communities, without imposing symmetry.In the general
stochastic block model SBM(n,p,W), n vertices are split into k
communities of relative size {p_i}_{i \in [k]}, and vertices in
community i and j connect independently with probability {W_{i,j}}_{i,j
\in [k]}. This paper investigates the partial and exact recovery
of communities in the general SBM (in the constant and
logarithmic degree regimes), and uses the generality of the results to
tackle overlapping communities.The contributions of the paper are: (i)
an explicit characterization of the recovery threshold in the general
SBM in terms of a new f-divergence function D_+, which generalizes the
Hellinger and Chernoff divergences, and which provides an operational
meaning to a divergence function analog to the KL-divergence in the
channel coding theorem, (ii) the development of an algorithm that
recovers the communities all the way down to the optimal threshold and
runs in quasi-linear time, showing that exact recovery has no
information-theoretic to computational gap for multiple communities,
(iii) the development of an efficient algorithm that detects communities
in the constant degree regime with an explicit accuracy bound that can
be made arbitrarily close to 1 when a prescribed signal-to-noise ratio
(defined in term of the spectrum of diag(p)W tends to infinity.
Let P be a k-ary predicate over a
finite alphabet. Consider a random CSP(P) instance I over n variables
with m constraints. When m >> n the instance will be unsatisfiable
with high probability and we want to find a certificate of
unsatisfiability. When P is the 3-ary OR predicate, this is the
well-studied problem of refuting random 3-SAT formulas and an efficient
algorithm is known only when m >> n^{3/2}. Understanding the
density required for refutation of other predicates is important in
cryptography, proof complexity, and learning theory. Previously, it was
known that for a k-ary predicate, having m >> n^{\lceil k/2\rceil}
constraints suffices for refutation. We give a criterion for predicates
that often yields efficient refutation algorithms at much lower
densities. Specifically, if P fails to support a t-wise uniform
distribution, then there is an efficient algorithm that refutes random
CSP(P) instances whp when m >> n^{t/2}. Indeed, our algorithm will
``somewhat strongly" refute the instance I, certifying Opt(I) \le
1−\Omega_k(1), if t=k then we get the strongest possible refutation,
certifying Opt(I) \le E[P]+o(1). This last result is new even in the
context of random k-SAT. Regarding the optimality of our m \gg nt/2
requirement, prior work on SDP hierarchies has given some evidence that
efficient refutation of random CSP(P) may be impossible when m\ll nt/2.
Thus there is an indication our algorithm's dependence on m is optimal
for every P, at least in the context of SDP hierarchies. Along these
lines, we show that our refutation algorithm can be carried out by the
O(1)-round SOS SDP hierarchy. Finally, as an application of our result,
we falsify assumptions used to show hardness-of-learning results in
recent work of Daniely, Linial, and Shalev-Shwartz.
We prove a near optimal
round-communication tradeoff for the two-party quantum communication
complexity of disjointness. For protocols with r rounds, we prove a
lower bound of Omega(n/r) on the communication required for computing
disjointness of input size n, which is optimal up to logarithmic
factors. The previous best lower bound was Omega(n/rˆ2) due to Jain,
Radhakrishnan and Sen. Along the way, we develop several tools for
quantum information complexity, one of which is a lower bound for
quantum information complexity in terms of the generalized discrepancy
method. As a corollary, we get that the quantum communication complexity
of any boolean function f is at most 2ˆO(QIC(f)), where QIC(f) is the
prior-free quantum information complexity of f (with error 1/3).
We present an algorithm for sparse
Hamiltonian simulation whose complexity is optimal (up to log factors)
as a function of all parameters of interest. Previous algorithms had
optimal or near-optimal scaling in some parameters at the cost of poor
scaling in others. Hamiltonian simulation via a quantum walk has optimal
dependence on the sparsity at the expense of poor scaling in the
allowed error. In contrast, an approach based on fractional-query
simulation provides optimal scaling in the error at the expense of poor
scaling in the sparsity. Here we combine the two approaches, achieving
the best features of both. By implementing a linear combination of
quantum walk steps with coefficients given by Bessel functions, our
algorithm's complexity (as measured by the number of queries and 2-qubit
gates) is logarithmic in the inverse error, and nearly linear in the
product tau of the evolution time, the sparsity, and the magnitude of
the largest entry of the Hamiltonian. Our dependence on the error is
optimal, and we prove a new lower bound showing that no algorithm can
have sublinear dependence on tau.
We present an efficient decoding
algorithm for constant rate quantum hypergraph-product LDPC codes which
provably corrects adversarial errors of weight proportional to the code
minimum distance, or equivalently to the square-root of the
blocklength.The algorithm runs in time linear in the number of qubits,
which makes its performance the strongest to date for linear-time
decoding of quantum codes. The algorithm relies on expanding properties,
not of the quantum code's factor graph directly, but of the factor
graph of the original classical code it is constructed from.
A local tester for a code
probabilistically views a small set of coordinates of a given word and
based on this local view accepts codewords with probability one while
rejecting words far from the code with constant probability. A local
tester for a code is said to be ``robust'' if the local views of the
tester are far from acceptable views when the word being tested is far
from the code. Robust testability of codes play a fundamental role in
constructions of probabilistically checkable proofs where robustness is a
critical element in composition. In this work we consider a broad class
of codes, called lifted codes, that include codes formed by low-degree
polynomials, and show that an almost natural test, extending a
low-degree test proposed by Raz and Safra (STOC 1997), is robust. Our
result is clean and general --- the robustness of the test depends only
on the distance of the code being lifted, and is positive whenever the
distance is positive.We use our result to get the first robust
low-degree test that works when the degree of the polynomial being
tested is more than half the field size. Our results also show that the
high-rate codes of Guo et al.\ (ITCS 2013) are robustly locally testable
with sublinear query complexity. Guo et al. also show several other
interesting classes of locally testable codes that can be derived from
lifting and our result shows all such codes have robust testers, at the
cost of a quadratic blowup in the query complexity of the
tester. Of technical interest is an intriguing relationship between
tensor product codes and lifted codes that we explore and exploit.
We show that equivalence of
deterministic top-down tree-to-string transducersis decidable, thus
solving a long standing open problem in formal language theory.We also
present efficient algorithms for subclasses:polynomial time for total
transducers with unary output alphabet (over a given top-down regular
domain language), and co-randomized polynomial time for linear
transducers;these results are obtained using techniques from
multi-linear algebra.For our main result, we prove that equivalence can
be certified by means of inductive invariants using polynomial
ideals. This allows us to construct two semi-algorithms, one
searching for aproof of equivalence, one for a witness of
non-equivalence.
Over the past two decades the main
focus of research into first-order (FO) model checking algorithms have
been sparse relational structures - culminating in the FPT-algorithm by
Grohe, Kreutzer and Siebertz forFO model checking of nowhere dense
classes of graphs [STOC'14], with dense structures starting to attract
attention only recently. Bova, Ganian and Szeider
[CSL-LICS'14] initiated the study of the complexity of FO model
checkingon partially ordered sets (posets). Bova, Ganian and
Szeider showed that model checking {\em existential} FO logic is
fixed-parameter tractable (FPT) on posets of bounded width, where the
width of a poset is the size of the largest antichain in the
poset. The existence of an FPT algorithm for general FO model
checking on posets of bounded width, however, remained
open. We resolve this question in the positive by giving an
algorithm that takes as its input an n-element poset P of width w and an
FO logic formula phi, and determines whether phi holds on P in time
f(phi,w).n^2
We study the satisfiability of
ordering constraint satisfaction problems (CSPs) above average. We prove
the conjecture of Gutin, van Iersel, Mnich, and Yeo that the
satisfiability above average of ordering CSPs of arity k is
fixed-parameter tractable for every k. Previously, this was only known
for k=2 and k=3. We also generalize this result to more general classes
of CSPs, including CSPs with predicates defined by linear equations.To
obtain our results, we prove a new Bonami-type inequality for the
Efron—Stein decomposition. The inequality applies to functions defined
on arbitrary product probability spaces. In contrast to other
variants of the Bonami Inequality, it does not depend on the mass of
the smallest atom in the probability space. We believe that this
inequality is of independent interest.
We identify and study relevant
structural parameters for the problem of counting perfect matchings in a
given input graph G. These generalize the well-known tractable planar
case, and they include the genus of G, its apex number (the minimum
number of vertices whose removal renders G planar), and its Hadwiger
number (the size of a largest clique minor).To study these parameters,
we first introduce the notion of combined matchgates, a general
technique that bridges parameterized counting problems and the theory of
so-called Holants and matchgates: Using combined matchgates, we can
simulate certain non-existing gadgets F as linear combinations of t=O(1)
existing gadgets. If a graph G features k occurrences of F, we can then
reduce G to t^k graphs that feature only existing gadgets, thus
enabling parameterized reductions.As applications of this technique, we
simplify known 4^g*n^3 time algorithms for counting perfect matchings on
graphs of genus g. Orthogonally to this, we show #W[1]-hardness of the
permanent on k-apex graphs, implying its #W[1]-hardness under the
Hadwiger number. Additionally, we rule out n^o(k/log k) time algorithms
under the counting exponential-time hypothesis #ETH.Finally, we use
combined matchgates to prove parity-W[1]-hardness of evaluating the
permanent modulo 2^k, complementing an O(n^4k) time algorithm by Valiant
and answering an open question of Björklund. We also obtain a lower
bound of n^Omega(k/log k) under the parity version of the
exponential-time hypothesis.
We give an algorithm that, for
every fixed k, decides isomorphism of graphs of rank width at
most k in polynomial time. As the rank width of a graph is
bounded in terms of its clique width, we also obtain a
polynomial time isomorphism test for graph classes of bounded
clique width.
We show that deterministic
communication complexity can be superlogarithmic in the partition number
of the associated communication matrix. We also obtain near-optimal
deterministic lower bounds for the Clique vs. Independent Set problem,
which in particular yields new lower bounds for the log-rank conjecture.
All these results follow from a simple adaptation of a
communication-to-query simulation theorem of Raz and McKenzie
(Combinatorica 1999) together with lower bounds for the analogous query
complexity questions.
There has been a resurgence of
interest in lower bounds whose truth rests on the conjectured hardness
of well known computational problems. These conditional lower bounds
have become important and popular due to the painfully slow progress on
proving strong unconditional lower bounds. Nevertheless, the long term
goal is to replace these conditional bounds with unconditional ones. In
this paper we make progress in this direction by studying the cell probe
complexity of two conjectured to be hard problems of particular
importance: matrix-vector multiplication and a version of dynamic set
disjointness known as \Patrascu's Multiphase Problem. We give improved
unconditional lower bounds for these problems as well as introducing new
proof techniques of independent interest. These include a technique
capable of proving strong threshold lower bounds of the following form:
If we insist on having a very fast query time, then the update time has
to be slow enough to compute a lookup table with the answer to every
possible query. This is the first time a lower bound of this type has
been proven.
We prove that it is NP-hard to
approximate the non-commutative Grothendieck problem to within any
constant factor larger than one-half, which matches the approximation
ratio of the algorithm of Naor, Regev, and Vidick (STOC’13). Our proof
uses an embedding of finite-dimensional Hilbert spaces into the space of
matrices endowed with the trace norm with the property that the image
of standard basis vectors is longer than that of unit vectors with no
large coordinates.
The vertex cover problem is one of
the most important and intensively studied combinatorial optimization
problems. Khot and Regevproved that the problem is NP-hard to
approximate within a factor2 - epsilon, assuming the Unique Games
Conjecture (UGC). This istight because the problem has an easy
2-approximation algorithm.Without resorting to the UGC, the best
inapproximability result for theproblem is due to Dinur and Safra:
vertex cover is NP-hard to approximate within a factor 1.3606. We prove
the following unconditional result about linear programming
(LP)relaxations of the problem: every LP relaxation that approximates
vertex cover within a factor of 2-epsilon has super-polynomially many
inequalities. As a direct consequence of our methods, we also establish
that LP relaxations (as well as SDP relaxations) that approximate the
independent set problem within any constant factor have
super-polynomially many inequalities.
We develop a new approach for
uniform generation of combinatorial objects, and apply it to derive a
uniform sampler A for d-regular graphs. A can be implemented such that
each graph is generated in expected time O(nd^3), provided that d
grows more slowly than the square root of n. Our result significantly
improves the previously best uniform sampler, which works efficiently
only when d is about the one-third power of n, with essentially the same
running time for the same d. We also give a linear-time approximate
sampler B, which generates a random d-regular graph whose distribution
differs from the uniform by o(1) in total variation distance, when d
grows more slowly than the square root of n.
We study the computational
complexity of several natural problems arising in statistical physics
and combinatorics. In particular, we consider the following problems:
the mean magnetization and mean energy of the Ising model (both the
ferromagnetic and the anti-ferromagnetic settings), the average size of
an independent set in the hard core model, and the average size of a
matching in the monomer-dimer model. We prove that for all non-trivial
values of the underlying model parameters, exactly computing these
averages is #P-hard.In contrast to previous results of Sinclair and
Srivastava (2013) for the mean magnetization of the ferromagnetic Ising
model, our approach does not use any Lee-Yang type theorems about the
complex zeros of partition functions. Indeed, it was due to
the lack of suitable Lee-Yang theorems for models such as the
anti-ferromagnetic Ising model that some of the problems we study here
were left open by Sinclair and Srivastava. In this paper, we instead use
some relatively simple and well-known ideas from the theory of
automatic symbolic integration to complete our hardness reductions.
An instance of the Valued
Constraint Satisfaction Problem (VCSP) is given by a finite set of
variables, a finite domain of labels, and a sum of functions, each
function depending on a subset of the variables. Each function can take
finite values specifying costs of assignments of labels to its variables
or the infinite value, which indicates infeasible assignments. The goal
is to find an assignment of labels to the variables that minimizes the
sum.We study (assuming that $P \ne NP$) how the complexity of this very
general problem depends on the set of functions allowed in the
instances, the so-called constraint language. The case when all allowed
functions take values in $\{0,\infty\}$ corresponds to ordinary CSPs,
where one deals only with the feasibility issue and there is no
optimization. This case is the subject of the Algebraic CSP Dichotomy
Conjecture predicting for which constraint languages CSPs are tractable
and for which NP-hard. The case when all allowed functions take only
finite values corresponds to finite-valued CSP, where the feasibility
aspect is trivial and one deals only with the optimization issue. The
complexity of finite-valued CSPs was fully classified by Thapper and
Zivny.An algebraic necessary condition for tractability of a
general-valued CSP with a fixed constraint language was recently given
by Kozik and Ochremiak. As our main result, we prove that if a
constraint language satisfies this algebraic necessary condition, and
the feasibility CSP corresponding to the VCSP with this language is
tractable, then the VCSP is tractable. The algorithm is a simple
combination of the assumed algorithm for the feasibility CSP and the
standard LP relaxation. As a corollary, we obtain that a dichotomy for
ordinary CSPs would imply a dichotomy for general-valued CSPs.
We prove a complexity dichotomy for
complex-weighted Holant problems with an arbitrary set of symmetric
constraint functions on Boolean variables.In the study of counting
complexity, such as #CSP, there are problems which are #P-hard over
general graphs but P-time solvable over planar graphs. A recurring theme
has been that a holographic reduction [Val08] to FKT precisely captures
these problems. This dichotomy answers the question: Is this
a universal strategy? Surprisingly, we discover new planar tractable
problems in the Holant framework (which generalizes #CSP) that are not
expressible by a holographic reduction to FKT. In particular, the
putative form of a dichotomy for planar Holant problems is false.
Nevertheless, we prove a dichotomy for #CSP^2, a variant of #CSP where
every variable appears even times, that the presumed universality holds
for #CSP^2. This becomes an important tool in the proof of the full
dichotomy, which refutes this universality in general. The full
dichotomy says that the new P-time algorithms and the strategy of
holographic reductions to FKT together are universal for these locally
defined counting problems.As a special case of our new planar tractable
problems, counting perfect matchings (#PM) over k-uniform hypergraphs is
P-time computable when the incidence graph is planar and k >= 5. The
same problem is #P-hard when k=3 or k=4, also a consequence of the
dichotomy. More generally, over hypergraphs with specified hyperedge
sizes and the same planarity assumption, #PM is P-time computable if the
greatest common divisor (gcd) of all hyperedge sizes is at least 5.
A non-backtracking walk on a graph
is a directed path such that noedge is the inverse of its preceding
edge. The non-backtracking matrixof a graph is indexed by its directed
edges and can be used to countnon-backtracking walks of a given length.
It has been used recently inthe context of community detection and has
appeared previously inconnection with the Ihara zeta function and in
some generalizations ofRamanujan graphs. In this work, we study the
largest eigenvalues ofthe non-backtracking matrix of the Erdos-Renyi
random graph andof the Stochastic Block Model in the regime where the
number of edgesis proportional to the number of vertices. Our results
confirm the"spectral redemption conjecture" that community detection can
be madeon the basis of the leading eigenvectors above the
feasibilitythreshold.
We prove that there exist bipartite
Ramanujan graphs of every degree and every number of
vertices.The proof is based on analyzing the expected characteristic
polynomial of a union of random perfect matchings, and
involves three ingredients: (1) a formula for the
expected characteristic polynomial of the sum of a
regular graph with a random permutation of another regular
graph, (2) a proof that this expected polynomial is real
rooted and that the family of polynomials considered in this
sum is an interlacing family, and (3) strong
bounds on the roots of the expected characteristic
polynomial of a union of random perfect
matchings, established using the framework of finite free
convolutions introduced recently by the authors.
We show that the number of
incidences between m distinct pointsand n distinct lines in R^4 is
O(2^{c sqrt{logm}} (m^{2/5}n^{4/5}+m) + m^{1/2}n^{1/2}q^{1/4}
+m^{2/3}n^{1/3}s^{1/3} + n), for a suitable absolute constantc, provided
that no 2-plane contains more than s input lines,and no hyperplane or
quadric contains more than q lines. The bound holds without the extra
factor 2^{c sqrt{log m}} when m\len^{6/7} or m \ge n^{5/3}. Except for
this possible factor, thebound is tight in the worst case.The context of
this work is incidence geometry, a topic that hasbeen widely studied
for more than three decades, with strongconnections to a variety of
topics, from range searching incomputational geometry to the Kakeya
problem in harmonic analysisand geometric measure theory. The area has
picked up considerablemomentum in the past seven years, following the
seminal works ofGuth and Katz, where the later work solves the
point-line incidence problem in three dimensions, using new toolsand
techniques from algebraic geometry. This work extends theirresult to
four dimensions. In doing so, it had to overcome many new technical
hurdles that arise from the higher-dimensional context, by developing
and adapting more advanced tools from algebraic geometry.
Smoothing properties of the noise
operator on the discrete cube and on Gaussian space haveplayed a pivotal
role in many fields. In particular, these smoothing effects
have seena broad range of applications in theoretical computer
science.We exhibit new regularization properties of the noise operator
on Gaussian space.More specifically,we show that the mass on level sets
of a probability density decays uniformlyunder the Ornstein-Uhlenbeck
semigroup. This confirms positively the Gaussian caseof
Talagrand's convolution conjecture (1989)on the discrete cube.A major
theme is our use of an It\^o process (the ``F\"ollmer drift'')which can
be seen as an entropy-optimal coupling between the Gaussian measure and
another given measure on Gaussian space.To analyze this process, we
employ stochastic calculus and Girsanov's change of measure formula.The
ideas and tools employed here provide a new perspective on
hypercontractivityin Gaussian space and the discrete cube.In particular,
our work gives a new way of studying ``small'' sets in product spaces
(e.g.,sets of size $2^{o(n)}$ in the discrete cube) using a form of
regularized online gradient descent.
Let X be a sparse random matrix of
size n by p (p >> n). We prove that if p > C n log^4
n, then with probability 1-o(1), | X^T v|_1 is close to its expectation
for all vectors v in R^n (simultaneously). The bound on p is sharp up
to the polylogarithmic factor. The study of this problem is directly
motivated by an application. Let A be an n by n matrix,
X be an n by p matrix and Y = AX. A
challenging and important problem in data analysis, motivated by
dictionary learning and other practical problems, is to recover both A
and X, given Y. Under normal circumstances, it is clear that this
problem is underdetermined. However, in the case when X is sparse and
random, Spielman, Wang and Wright showed
that one can recover both A and X efficiently from
Y with high probability, given that p (the number of
samples) is sufficiently large. Their method works for p >
C n^2 log^2 n and they conjectured that p > C n log n suffices. The
bound n log n is sharp for an obvious information theoretical
reason. The matrix concentration result verifies the Spielman
et. al. conjecture up to a log^3 n factor. Our proof of the
concentration result is based on
two ideas. The first is an economical way to apply
the union bound. The second is a refined version of Bernstein's
concentration inequality for a sum of independent
variables. Both have nothing to do with random matrices and
are applicable in general settings.
A set function on a ground set of
size $n$ is approximately modular if it satisfies every
modularity requirement to within an additive error;
approximate modularity is the set analog of
approximate linearity. In this paper we study how
close, in additive error, can approximately modular functions
be to truly modular functions. We first obtain a polynomial
time algorithm that makes $O(n^2 \log n)$ queries to any
approximately modular function to reconstruct a modular
function that is $O(\sqrt{n})$-close. We also show
an almost matching lower bound: any algorithm would
need superpolynomially many queries to construct a modular
function that is $o\left(\sqrt{n / \log
n}\right)$-close. In a striking contrast to these near-tight
computational reconstruction bounds, we then show that for
any approximately modular function, there exists a modular
function that is $O(\log n)$-close.
We show that every non-adaptive
property testing algorithm making a constant number of queries, over a
fixed alphabet, can be converted to a sample-based (as per [Goldreich
and Ron, 2015]) testing algorithm whose average number of queries is a
fixed, smaller than 1, power of n. Since the query distribution of the
sample-based algorithm is not dependent at all on the property, or the
original algorithm, this has many implications in scenarios where there
are many properties that need to be tested for concurrently, such as
testing (relatively large) unions of properties, or converting a
Merlin-Arthur Proximity proof (as per [Gur and Rothblum, 2013]) to a
proper testing algorithm.The proof method involves preparing the
original testing algorithm for a combinatorial analysis. For the
analysis we develop a structural lemma for hypergraphs that may be of
independent interest. When analyzing a hypergraph that was extracted
from a 2-sided test, it allows for finding generalized sunflowers that
provide for a large-deviation type analysis. For 1-sided tests the
bounds can be improved further by applying Janson's inequality directly
over our structures.
We give a general unified method
that can be used for $L_1$ {\em closeness testing} of a wide range of
univariate structured distribution families. More specifically, we
design a sample optimal and computationally efficient algorithm for
testingthe equivalence of two unknown (potentially arbitrary) univariate
distributions under the $\mathcal{A}_k$-distance metric:Given sample
access to distributions with density functions $p, q: I \to \R$, we want
to distinguish between the cases that $p=q$ and
$\|p-q\|_{\mathcal{A}_k} \ge \eps$ with probability at least $2/3$.We
show that for any $k \ge 2, \eps>0$, the {\em optimal} sample
complexity of the $\mathcal{A}_k$-closeness testingproblem is
$\Theta(\max\{ k^{4/5}/\eps^{6/5}, k^{1/2}/\eps^2 \})$.This is the
first $o(k)$ sample algorithm for this problem, and yieldsnew, simple
$L_1$ closeness testers, in most cases with optimal sample complexity,
for broad classes of structured distributions.
An (n,k)-Poisson Multinomial
Distribution (PMD) is the distribution of the sum of n independent
random vectors supported on the set B_k={e_1,...,e_k} of standard basis
vectors in R^k. We prove a structural characterization of these
distributions, showing that, for all epsilon > 0, any (n, k)-Poisson
multinomial random vector is epsilon-close, in total variation distance,
to the sum of a discretized multidimensional Gaussian and an
independent (poly(k/epsilon), k)-Poisson multinomial random vector. Our
structural characterization extends the multi-dimensional CLT of Valiant
and Valiant, by simultaneously applying to all approximation
requirements epsilon. In particular, it overcomes factors depending on
log n and, importantly, the minimum eigenvalue of the PMD's
covariance matrix.We use our structural characterization to obtain an
epsilon-cover, in total variation distance, of the set of all
(n,k)-PMDs, significantly improving the cover size of Daskalakis and
Papadimitriou, and obtaining the same qualitative dependence of the
cover size on n and epsilon as the k=2 cover of Daskalakis and
Papadimitriou. We further exploit this structure to show that (n,k)-PMDs
can be learned to within epsilon in total variation distance from
~O_k(1/epsilon^2) samples, which is near-optimal in terms of dependence
on epsilon and independent of n. In particular, our result
generalizes the single-dimensional result of Daskalakis, Diakonikolas
and Servedio for Poisson binomials to arbitrary dimension. Finally, as a
corollary of our results on PMDs, we give a ~O_k(1/epsilon^2) sample
algorithm for learning (n,k)-sums of independent integer random
variables (SIIRVs), which is near-optimal for constant k.
A random sampling function
Sample:U->{0,1} for a key universe U is a distinguisher with
probability P if for any given assignment of values v(x) to the keys x
in U, including at least one non-zero v(x) != 0, the sampled sum, that
is, sum{v(x) | x in U, Sample(x)=1}, is non-zerowith probability at
least P. Here the key values may come from anycommutative monoid
(addition is commutative and associative and zero is neutral). Such
distinguishers were introduced by Vazirani [PhD thesis 1986], and Naor
and Naor used them for their small bias probability spaces [STOC'90].
Constant probability distinguishers areused for testing in contexts
where the key values are not computeddirectly, yet where the sum is
easily computed. A simple example iswhen we get a stream of key value
pairs (x_1,v_1),(x_2,v_2),...,(x_n,v_n) where the same key may appear
many times. The accumulated value of key x is v(x)=sum{v_i | x_i=x}. For
space reasons, we may not be able to maintain v(x) for every key x, but
the sampled sum is easily maintained as the single value sum{v_i |
Sample(x_i)}.Here we show that when dealing with w-bit integers, if a is
a uniform odd w-bit integer and t is a uniform w-bit integer, then
Sample(x)=[ax mod 2^w
In this paper we analyze a hash
function for k-partitioning a set into bins,obtaining strong
concentration bounds for standard algorithms combiningstatistics from
each bin.This generic method was originally introduced byFlajolet and
Martin [FOCS'83] in order to save a factor Omega(k) of time perelement
over k independent samples when estimating the number of
distinctelements in a data stream. It was also used in the widely used
HyperLogLogalgorithm of Flajolet et al. [AOFA'97] and in large-scale
machine learning byLi et al. [NIPS'12] for minwise estimation of set
similarity.The main issue of k-partition, is that the contents of
different bins may behighly correlated when using popular hash
functions. This means thatmethods of analyzing the marginal distribution
for a single bin do not apply.Here we show that a tabulation based hash
function, mixed tabulation, doesyield strong concentration bounds on
the most popular applications ofk-partitioning similar to those we would
get using a truly random hashfunction.The analysis is very involved and
implies several new results of independentinterest for both simple and
double tabulation, e.g. a simple andefficient construction for
invertible bloom filters and uniform hashing ona given set.
We show that there exists a graph G
with O(n) nodes, where any forest of n nodes is a node-induced subgraph
of G. Furthermore, for constant arboricity k, the result implies the
existence of a graphwith O(n^k) nodes that contains all n-node graphs as
node-induced subgraphs, matching a Omega(n^k) lower bound. The lower
bound and previously best upper bounds were presented in Alstrup and
Rauhe (FOCS'02). Our upper bounds are obtained through a log_2(n) +
O(1) labeling scheme for adjacency queries in forests.We
hereby solve an openproblem being raised repeatedly over decades, e.g.
in Kannan, Naor, Rudich (STOC 1988), Chung (J. of Graph Theory 1990),
Fraigniaud and Korman (SODA 2010).
The Lovasz Local Lemma is a seminal
result in probabilistic combinatorics. It gives a sufficient condition
on a probability space and a collection of events for the existence of
an outcome that simultaneously avoids all of those events. Finding such
an outcome by an efficient algorithm has been an active research topic
for decades. Breakthrough work of Moser and Tardos (2009) presented an
efficient algorithm for a general setting primarily characterized by a
product structure on the probability space.In this work we present an
efficient algorithm for a much more general setting. Our main assumption
is that there exist certain functions, called resampling oracles, that
can be invoked to address the undesired occurrence of the events. We
show that, in all scenarios to which the original Lovasz Local Lemma
applies, there exist resampling oracles, although they are not
necessarily efficient. Nevertheless, for essentially all known
applications of the Lovasz Local Lemma and its generalizations, we have
designed efficient resampling oracles. As applications of these
techniques, we present new results for packings of Latin transversals,
rainbow matchings and rainbow spanning trees.
We pose and study a fundamental
algorithmic problem which we term mixture selection, arising as a
building block in a number of game-theoretic applications:Given a
function $g$ from the $n$-dimensional hypercube to the bounded interval
$[-1,1]$, and an $n \times m$ matrix $A$ with bounded entries, maximize
$g(Ax)$ over $x$ in the $m$-dimensional simplex.This problem arises
naturally when one seeks to design a lottery over items for sale in an
auction, or craft the posterior beliefs for agents in a Bayesian game
through the provision of information (a.k.a. signaling).We present an
approximation algorithm for this problem when $g$ simultaneously
satisfies two ``smoothness'' properties:Lipschitz continuity with
respect to the $L^\infty$ norm, and noise stability.The latter notion,
which we define and cater to our setting, controls the degree to which
low-probability -- and possibly correlated -- errors in the inputs of
$g$ can impact its output.The approximation guarantee of our algorithm
degrades gracefully as a function of the Lipschitz continuity and noise
stability of $g$.In particular, when $g$ is both $O(1)$-Lipschitz
continuous and $O(1)$-stable, we obtain an (additive) polynomial-time
approximation scheme (PTAS) for mixture selection.We also show that
neither assumption suffices by itself for an additive PTAS, and both
assumptions together do not suffice for an additive fully
polynomial-time approximation scheme (FPTAS).We apply our algorithm for
mixture selection to a number of different game-theoretic applications,
focusing on problems from mechanism design and optimal signaling.In
particular, we make progress on a number of open problems suggested in
prior work by easily reducing them to mixture selection:we resolve an
important special case of the small-menu lottery design problem posed by
Dughmi, Han, and Nisan;we resolve the problem of revenue-maximizing
signaling in Bayesian second-price auctions posed by Emek et al. and
Miltersen and Sheffet;we design a quasipolynomial-time approximation
scheme for the optimal signaling problem in normal form games suggested
by Dughmi;and we design an approximation algorithm for the optimal
signaling problem in the voting model of Alonso and C\^{a}mara.
For selling a single item to agents
with independent but non-identically distributed values, the revenue
optimal auction is complex. With respect to it, Hartline and
Roughgarden showed that the approximation factor of the second-price
auction with an anonymous reserve is between two and four. We consider
the more demanding problem of approximating the revenue of the ex ante
relaxation of the auction problem by posting an anonymous price (while
supplies last) and prove that their worst-case ratio is e. As a
corollary, the upper-bound of anonymous pricing or anonymous reserves
versus the optimal auction improves from four to e. We conclude that, up
to an e factor, discrimination and simultaneity are unimportant for
driving revenue in single-item auctions.
We study the optimal lottery
problem and the optimal mechanism design problem in the setting of a
single unit-demand buyer with item values drawn from independent
distributions. Optimal solutions to both problems are characterized by a
linear program with exponentially many variables.For the menu size
complexity of the optimal lottery problem, we present an explicit,
simple instance with distributions of support size 2, and show that
exponentially many lotteries are required to achieve the optimal
revenue. We also show that, when distributions have support size 2 and
share the same high value, the simpler scheme of item pricing can
achieve the same revenue as the optimal menu of lotteries. The same
holds for the case of two items with support size 2 (but not necessarily
the same high value).For the computational complexity of the optimal
mechanism design problem, we show that unless the polynomial-time
hierarchy collapses (more exactly, P^NP = P^#P), there is no universal
efficient randomized algorithm to implement an optimal mechanism even
when distributions have support size 3.
We prove that finding a Nash
equilibrium of a game is hard, assuming the existence of
indistinguishability obfuscation and one-way functions with
sub-exponential hardness. We do so by showing how these cryptographic
primitives give rise to a hard computational problem that lies in the
complexity class PPAD, for which finding Nash equilibrium is
complete.Previous proposals for basing PPAD-hardness on program
obfuscation considered a strong ``virtual black-box" notion that is
subject to severe limitations and is unlikely to be realizable for the
programs in question. In contrast, for indistinguishability obfuscation
no such limitations are known, and recently, several candidate
constructions of indistinguishability obfuscation were suggested based
on different hardness assumptions on multilinear maps.Our result
provides further evidence of the intractability of finding a Nash
equilibrium, one that is extrinsic to the evidence presented so far.
We continue the study of welfare
maximization in unit-demand (matching) markets, in a distributed
information model where agent's valuations are unknown to the central
planner, and therefore communication is required to determine an
efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if
the market size is n, then r rounds of interaction (with logarithmic
bandwidth) suffice to obtain an n^(1/(r+1))-approximation to the optimal
social welfare. In particular, this implies that such
markets converge to a stable state (constant approximation) in time
logarithmic in the market size.We obtain the first multi-round lower
bound for this setup. We show that even if the allowable per-round
bandwidth of each agent is n^epsilon(r), the approximation ratio of any
r-round (randomized) protocol is no better than
Omega(n^(exp(-r)),implying an Omega(log log n) lower bound on the rate
of convergence of the market to equilibrium.Our construction and
technique may be of interest to round-communication tradeoffs in the
more general setting of combinatorial auctions, for which the only known
lower bound is for simultaneous (r=1) protocols [DNO14].