Linear Recognition of Almost Interval Graphs

On the maximum quartet distance between phylogenetic trees

between any two phylogenetic trees on $n$ leaves is at most

$(\frac 23 +o(1))\binom{n}{4}$.

Using the machinery of flag algebras we improve the currently known bounds

regarding this conjecture, in particular we show that the maximum is at most

$(0.69 +o(1))\binom{n}{4}$.

We also give further evidence that the conjecture is true by proving that

the maximum distance between caterpillar trees is at most

$(\frac 23 +o(1))\binom{n}{4}$.

Permutation patterns are hard to count

Our tools also allow us to disprove the Noonan--Zeilberger conjecture which states that the sequence {C(n,F)} is P-recursive.

Effective Diameter for Forest Fire and Social Random Walk Model

In this paper, we analyze one of these properties, shrinking diameter. We define a restricted version of their model that incorporates the main features that seem to contribute towards this property, and prove that the graphs generated by this model exhibit shrinking diameter. We prove that an even simpler model, the random walk model, already exhibits this phenomenon.

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

Partial Resampling to Approximate Covering Integer Programs

We develop a new rounding scheme based on the Partial Resampling variant of the Lov\'{a}sz Local Lemma developed by Harris \& Srinivasan (2013). This achieves an approximation ratio of $1 + \frac{\ln (\Delta_1+1)}{\amin} + O(\sqrt{ \frac{\log (\Delta_1+1)}{\amin}} )$, where $\amin$ is the minimum covering constraint and $\Delta_1$ is the maximum $\ell_1$-norm of any column of the covering matrix (whose entries are scaled to lie in $[0,1]$); we also show nearly-matching inapproximability and integrality-gap lower bounds.

Our approach improves asymptotically, in several different ways, over known results. First, it replaces $\Delta_0$, the maximum number of nonzeroes in any column (from the result of Srinivasan) by $\Delta_1$ which is always -- and can be much -- smaller than $\Delta_0$; this is the first such result in this context. Second,

our algorithm automatically handles multi-criteria programs; we achieve improved approximation ratios compared to the algorithm of Srinivasan, and give, for the first time when the number of objective functions is large, polynomial-time algorithms with good multi-criteria approximations.

We also significantly improve upon the upper-bounds of Kolliopoulos \& Young when the integer variables are required to be within $(1 + \epsilon)$ of some given upper-bounds, and show nearly-matching inapproximability.

Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution

We show that in certain conditions when the LLL condition is violated, a variant of the MT algorithm can still produce a distribution which avoids most of the bad events. We show in some cases this MT variant can run faster than the original MT algorithm itself, and develop the first-known criterion for the case of the asymmetric LLL. This can be used to find partial Latin transversals -- improving upon earlier bounds of Stein (1975) -- among other applications. We furthermore give applications in enumeration, showing that most applications (where we aim for all or most of the bad events to be avoided) have many more solutions than known before by proving that the MT-distribution has ``large" min-entropy and hence that its support-size is large.

Multiscale Mapper: An Algorithm for Topological Summarization via Codomain Covers

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

An important technical tool that we use is a construction of nearly optimal and linear lossless condensers which is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan, JACM 2009). Moreover, we design a deterministic and non-adaptive $\ell_1/\ell_1$ compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time $k^{1+\alpha} (\log N)^{O(1)}$ (for the GUV-based condenser) and is of independent interest. Our scheme significantly simplifies and improves an earlier expander-based construction due to Berinde, Gilbert, Indyk, Karloff, Strauss (Allerton 2008).

Our methods use linear lossless condensers in a black box fashion; therefore, any future improvement on explicit constructions of such condensers would immediately translate to improved parameters in our framework (potentially leading to $k (\log N)^{O(1)}$ reconstruction time with a reduced exponent in the poly-logarithmic factor, and eliminating the extra parameter $\alpha$).

Finally, by allowing the algorithm to use randomness, while still using non-adaptive queries, the running time of the algorithm can be improved to $\tilde{O}(k \log^3 N)$.

Directed multicut is W[1]-hard, even for four terminal pairs

Our gadget methodology allows us also to prove W[1]-hardness of the Steiner Orientation problem parameterized by the number of terminal pairs, resolving an open problem of Cygan, Kortsarz, and Nutov [SIAM J. Discrete Math. 27(3):1503-1513 (2013)].

Subexponential parameterized algorithm for Interval Completion

Online Contention Resolutions Schemes

We, thus, get a broadly applicable framework for several online selection problems, which improves on previous approaches in terms of the types of constraints that can be handled, the objective functions that can be dealt with, and the assumptions on the strength of the adversary. Furthermore, we resolve two open problems from the literature; namely, we present the first constant-factor constrained oblivious posted price mechanism for matroid constraints, and the first constant-factor algorithm for weighted stochastic probing with deadlines.

Faster Fully Dynamic Matchings with Small Approximation Ratios

also been the subject of much attention. Existing algorithms for dynamic matching (in general n-vertex m-edge graphs) fall into two groups: there are fast (mostly randomized) algorithms that do not achieve a better than 2-approximation, and there are slow algorithms with Omega(m^{1/2})

update time that achieve a better-than-2 approximation. Thus the obvious question is whether we can design an algorithm that achieves a tradeoff between these two: a o(m^{1/2}) update time and a better-than-2 approximation simultaneously. We answer this question in the affirmative. Previously, such bounds were only known for the special case of bipartite graphs.

Our main result is a fully dynamic deterministic algorithm that maintains a (3/2 + epsilon)-approximation in amortized update time O(m^{1/4}epsilon^{-2.5}). In addition to achieving the trade-off described above, our algorithm manages to be polynomially faster than all existing deterministic algorithms (excluding a log(n)-approximation of Onak et. al.) while still maintaining a better-than-2 approximation.

We also give stronger results for graphs whose arboricity is at most a. We show how to maintain a (1+ epsilon)-approximate fractional matching or a (3/2 + epsilon)-approximate integral matching in worst-case time O(a(a + log n)) for constant epsilon. When the arboricity is constant, this bound is O(log n) and when the arboricity is polylogarithmic the update time is also polylogarithmic. Previous results for small arboricity non-bipartite graphs could only maintain a maximal matching (2-approximation).

We maintain the approximate matching without explicitly using augmenting paths. We define an intermediate graph, called an edge degree constrained subgraph (EDCS) and show that the EDCS contains a large matching, and show how to maintain an EDCS H in G. The EDCS was used in previous works on bipartite graphs, however the details and proofs are completely different in general graphs. The algorithm for bipartite graphs relies on ideas from flows and cuts to non-constructively prove the existence of a good matching in H, but these ideas do not seem to extend to non-bipartite graphs. In this paper we instead explicitly construct a large fractional matching in H. In some cases we can guarantee that this fractional matching is gamma-resticted, which means that it only uses values either in the range [0,gamma] or 1. We then combine this matching with a new structural property of maximum matchings in non-bipartite graphs, which is analogous to the cut induced by maximum matchings in bipartite graphs.

Deterministic APSP, Partial Matches, and More: Quickly Derandomizing the Polynomial Method

A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, applying the tools of epsilon-biased sets and modulus-amplifying polynomials.

Kernelization via Sampling with Applications to Dynamic Graph Streams

Matching: First, there exists an $\tilde{O}(k^2)$ space algorithm that returns an exact maximum matching on the assumption the cardinality is at most $k$. The best previous algorithm used $\tilde{O}(kn)$ space where $n$ is the number of vertices in the graph and we prove our result is optimal up to logarithmic factors. Our algorithm has $\tilde{O}(1)$ update time. Second, there exists an $\tilde{O}(n^2/\alpha^3)$ space algorithm that returns an $\alpha$-approximation for matchings of arbitrary size. We generalize both results for weighted matching. Third, there exists an $\tilde{O}(n^{4/5})$ space algorithm that returns a constant approximation in graphs with bounded arboricity. While there has been a substantial amount of work on approximate matching in insert-only graph streams, these are the first non-trivial results in the dynamic setting.

Vertex Cover and Hitting Set: There exists an $\tilde{O}(k^d)$ space algorithm that solves the minimum hitting set problem where $d$ is the cardinality of the input sets and $k$ is an upper bound on the size of the minimum hitting set. We prove this is optimal up to logarithmic factors. Our algorithm has $\tilde{O}(1)$ update time. The case $d=2$ corresponds to minimum vertex cover.

Finally, we consider a larger family of parameterized problems (including $b$-matching, disjoint paths, vertex coloring among others) for which our subgraph sampling primitive yields fast, small-space dynamic graph stream algorithms. We then show lower bounds for natural problems outside this family.

On approximating strip packing with a better ratio than 3/2

that we want to place in a strip of given width such that we minimize

the height of the obtained packing. It is a very classical two-dimensional

packing problem that has received a lot of attention and it has applications

in many settings such as stock-cutting and scheduling. A straight-forward

reduction from Partition shows that the problem cannot be

approximated with a better absolute factor than 3/2. However, this reduction

requires the numeric values to be exponentially large. In this paper,

we present a (1.4+epsilon)-approximation algorithm with pseudo-polynomial

running time. This implies that for polynomially bounded input data

the problem can be approximated with a strictly better ratio than

for exponential input which is a very rare phenomenon in combinatorial

optimization.

Our algorithm is based on a structural lemma proving that there is

a packing of height (1.4+epsilon)OPT that allows a partition

of the packing area into few rectangular boxes. These boxes have the

property that they decouple the packing decisions for the items that

are thin and high, wide and narrow, or large in both dimensions.

The interaction of these item types is typically a major problem

when designing algorithms and our partition completely solves this.

Particularly

difficult are items that are thin and high since a single one of them

can increase the optimal packing height significantly if placed wrongly

and there can be up to Omega(n) of them. For

those items the box partition is even fine grained enough so that

all items in a box have essentially the same height. This reduces

the usually difficult packing decisions for these items to a problem

that can be solved easily via a pseudo-polynomial time dynamic program.

The mentioned reduction from Partition also breaks down if we allow

to drop a constant number of input items (while the compared optimal

solution cannot do that). We show that then we can approximate the

problem much better and present a polynomial time algorithm computing

a packing of height at most (1+epsilon)OPT that needs to drop at most

a constant number of items.

Simpler, faster and shorter labels for distances in graphs

More specifically, we present a distance labeling scheme with labels of length $\frac{\log 3}{2}n+o(n)$ bits\footnote{Throughout the paper, all logarithms are in base 2.} and constant decoding time. This outperforms all existing results with respect to both size and decoding time, including Winkler's (Combinatorica 1983) decade-old result, which uses labels of size $(\log 3)n$ and $\Oh(n / \log n)$ decoding time, and Gavoille et al.\ (SODA'01), which uses labels of size $11n+o(n)$ and $O(\log\log n)$ decoding time. In addition, our algorithm is simpler than the previous ones.

In the case of integral edge weights of size at most $W$, we present almost matching upper and lower bounds for the label size $\ell$:

$\frac{1}{2}(n-1) \log \ceil{\frac{W}{2} + 1} \le \ell \le \frac{1}{2}n \log{(2W+1)} + O(\log n\cdot\log(nW))$.

Furthermore, for $r$-additive approximation labeling schemes, where distances can be off by up to an additive constant $r$, we present both upper and lower bounds. In particular, we present an upper bound for $1$-additive approximation schemes which, in the unweighted case, has the same size (ignoring second order terms) as an adjacency labeling scheme, namely $n/2$.

We also give results for bipartite graphs as well as for exact and $1$-additive distance oracles.

Gowers Norm, Function Limits, and Parameter Estimation

Phase Transitions in Group Testing

\begin{equation}

Y = \openone\bigg\{ \bigcup_{i \in S} \{X_i = 1\} \bigg\} \oplus Z, \nonumber

\end{equation}

where $X=(X_1,\dotsc,X_p)\in\{0,1\}^p$ is a measurement vector indicating the items involved in each test, and $Z\in\{0,1\}$ represents possible noise under modulo-$2$ addition. We consider Bernoulli designs, in which each entry of each measurement vector is independently drawn at random from a Bernoulli distribution.

In the noiseless case with $k = \Theta(p^{\theta})$ ($\theta \le \frac{1}{3}$), we show the following for an optimal recovery algorithm:

\begin{align}

n \ge \Big( k\log_2\frac{p}{k} \Big) (1+\eta) \implies \PP[\mathrm{error}] \to 0 \nonumber \\

n \le \Big( k\log_2\frac{p}{k} \Big) (1-\eta) \implies \PP[\mathrm{error}] \to 1 \nonumber

\end{align}

for any $\eta > 0$, where an error means that $\hat{S} \ne S$, with $\hat{S}$ denoting the estimate of $S$. That is, we provide an exact threshold at which the error probability under goes a phase transition from $0$ to $1$, for a measurement-optimal recovery rule minimizing the required number of measurements regardless of the computational complexity. The same threshold was previously shown to be the best possible when the measurement vectors are designed adaptively, with each vector chosen based on the outcomes of previous tests. Thus, despite being non-adaptive, Bernoulli designs are \emph{asymptotically optimal} when $\theta \le \frac{1}{3}$.

In the case of partial recovery, we show that

\begin{align}

n \le \Big( (1-\alpha^{*}) k\log_2\frac{p}{k} \Big) (1-\eta) \implies \PP[\mathrm{error}] \to 1, \nonumber

\end{align}

for any $\eta > 0$, where an error means that $|S \backslash \hat{S}| \ge \alpha^{*}|S|$ or $|\hat{S} \backslash S| \ge \alpha^{*}|S|$, so that $\alpha^{*}$ indicates the allowed ``distance'' from $\hat{S}$ to $S$. Thus, there is little gain to be obtained in the required number of measurements even under this relaxed criterion. Finally, analogous necessary and sufficient conditions are derived for the noisy setting with $Z \sim \Bernoulli(\rho)$, and we again provide exact thresholds for sufficiently small $\theta$.

Our analysis takes a novel approach revealing that the error probability is characterized by tail probabilities containing quantities of the form $\imath(x;y) := \log\frac{P_{Y|X}(y|x)}{P_Y(y)}$, permitting precise characterizations due to the fact that independent summations concentrate around their mean. This approach is a significant departure from widely-used tools such as maximum-likelihood decoding and Fano's inequality, and leads to sharper bounds for the case that $k$ scales with $p$, as well as the stronger statement $\PP[\mathrm{error}] \to 1$ (as opposed to merely $\PP[\mathrm{error}] \not\to 0$) in the converse bounds.

Discrete Gaussian Sampling Reduces to CVP and SVP

Motivated by its increasing importance, we investigate the complexity of DGS itself and its relationship to CVP and SVP. Our first result is a polynomial-time dimension-preserving reduction from DGS to CVP. There is a simple reduction from CVP to DGS, so this shows that DGS is equivalent to CVP. Our second result, which we find to be more surprising, is a polynomial-time dimension-preserving reduction from centered DGS (the important special case when $t = 0$) to SVP. In the other direction, there is a simple reduction from $\gamma$-approximate SVP for any $\gamma = \Omega(\sqrt{n/\log n})$, and we present some (relatively weak) evidence to suggest that this might be the best achievable approximation factor.

Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions

Our main result is a $(1-1/e)^2$-approximation for the adaptive seeding problem for any monotone submodular function. While adaptive policies are often approximated via non-adaptive policies, our algorithm is based on a novel method we call \emph{locally-adaptive} policies. These policies combine a non-adaptive global structure, with local adaptive optimizations. This method enables the $(1-1/e)^2$-approximation for general monotone submodular functions and circumvents some of the impossibilities associated with non-adaptive policies.

We also introduce a fundamental problem in submodular optimization that may be of independent interest: given a ground set of elements where every element appears with some small probability, find a set of expected size at most $k$ that has the highest expected value over the realization of the elements. We show a surprising result: there are classes of monotone submodular functions (including coverage) that can be approximated almost optimally as the probability vanishes. For general monotone submodular functions we show via a reduction from \textsc{Planted-Clique} that approximations for this problem are not likely to be obtainable. This optimization problem is an important tool for adaptive seeding via non-adaptive policies, and its hardness motivates the introduction of \emph{locally-adaptive} policies we use in the main result.

Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

data-streaming problem, where the $m$ sets that comprise the instance

are to be read one by one. A semi-streaming algorithm is allowed only

$O(n poly(\log n, \log m))$ space to process this stream. For each

$p \ge 1$, we give a very simple deterministic algorithm that makes

$p$ passes over the input stream and returns an

appropriately certified $(p+1)n^{1/(p+1)}$-approximation to the

optimum set cover. More importantly, we proceed to show that this

approximation factor is essentially tight, by showing that a factor

better than $0.99 n^{1/(p+1)}/(p+1)^2$ is unachievable for a $p$-pass

semi-streaming algorithm, even allowing randomisation. In particular,

this implies that achieving a $\Theta(\log n)$-approximation requires

$\Omega(\log n/\log\log n)$ passes, which is tight up to the

$\log\log n$ factor.

These results extend to a relaxation of the set cover problem where we

are allowed to leave an~$\epsilon$ fraction of the universe uncovered: the

tight bounds on the best approximation factor achievable in~$p$ passes

turn out to be $\Theta_p(\min\{n^{1/(p+1)}, \epsilon^{-1/p}\})$.

Our lower bounds are based on a construction of a family of high-rank

incidence geometries, which may be thought of as vast generalisations

of affine planes. This construction, based on algebraic techniques,

appears flexible enough to find other applications and is therefore

interesting in its own right.

Time vs. Information Tradeoffs for Leader Election in Anonymous Trees

Our aim is to establish tradeoffs between the allocated time $\tau$ and the amount of information that has to be given {\em a priori} to the nodes to enable leader election in time $\tau$ in all trees for which leader election in this time is at all possible. Following the framework of {\em algorithms with advice}, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the {\em size of advice}. For a given time $\tau$ allocated to leader election, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time $\tau$.

For most values of $\tau$, our upper and lower bounds are either tight up to multiplicative constants, or they differ only by a logarithmic factor. Let $T$ be an $n$-node tree of diameter $diam \leq D$. While leader election in time $diam$ can be performed without any advice, for time $diam-1$ we give tight upper and lower bounds of $\Theta (\log D)$. For time $diam-2$ we give tight upper and lower bounds of $\Theta (\log D)$ for even values of $diam$, and tight upper and lower bounds of $\Theta (\log n)$ for odd values of $diam$. Moving to shorter time, in the interval $[\beta \cdot diam, diam -3]$ for constant $\beta >1/2$, we prove an upper bound of $O(\frac{n\log n}{D})$ and a lower bound of $\Omega(\frac{n}{D})$, the latter being valid whenever $diam$ is odd or when the time is at most $diam-4$. Hence, with the exception of the special case when $diam$ is even and time is exactly $diam-3$, our bounds leave only a logarithmic gap in this time interval. Finally, for time $\alpha \cdot diam$ for any constant $\alpha <1/2$ (except for the case of very small diameters), we again give tight upper and lower bounds, this time $\Theta (n)$.

Recovery and rigidity in a regular stochastic block model

eciently. Moreover we also prove that, in this setting, any suitably good partial recovery can be bootstrapped to obtain a full recovery of the communities.

How to Round Subspaces: A New Spectral Clustering Algorithm

We present two applications for our algorithm. First one finds a disjoint union of bounded degree expanders which approximate a given graph in spectral norm. The second one is for approximating the sparsest $k$-partition in a graph where each cluster have expansion at most $\phi_k$ provided $\phi_k \le O(\lambda_{k+1})$ where $\lambda_{k+1}$ is the $(k+1)^{st}$ eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required $\phi_k \le O(\lambda_{k+1}/k)$.

Focused Stochastic Local Search and the Lovasz Local Lemma

Obstructions for three-coloring graphs with one forbidden induced subgraph

We prove that there are only finitely many 4-critical $P_6$-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-coloring $P_6$-free graphs, which solves an open problem posed by Golovach et al. Here, $P_6$ denotes the induced path on six vertices.

Our result leads to the following dichotomy theorem: if $H$ is a connected graph, then there are finitely many 4-critical $H$-free graphs if and only if $H$ is a subgraph of $P_6$. This answers a question of Seymour.

The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand.

Tight bounds for graph homomorphism and subgraph isomorphism

Approximating the k-Level in Three-Dimensional Plane Arrangements

Approximate Undirected Maximum Flows in O(m polylog(n)) Time

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

The Adversarial Noise Threshold for Distributed Protocols

In our first result we show that any n-party T-round protocol on an undirected communication network G can be compiled into a robust simulation protocol on a sparse (O(n) edges) subnetwork so that the simulation tolerates an adversarial error rate of Omega(1/n); the simulation has a round complexity of O((m log n / n) T), where m is the number of edges in G. (So the simulation is work-preserving up to a log factor.) The adversary's error rate is within a constant factor of optimal. Given the error rate, the round complexity blowup is within a factor of O(k log n) of optimal, where k is the edge connectivity of G.

We also determine that the maximum tolerable error rate on directed communication networks is Theta(1/s) where s is the number of edges in a minimum equivalent digraph.

Next we investigate adversarial per-edge error rates, where the adversary is given an error budget on each edge of the network. We determine the limit for tolerable per-edge error rates on an arbitrary directed graph to within a factor of 2. However, the construction that approaches this limit has exponential round complexity, so we give another compiler, which transforms T-round protocols into O(mT)-round simulations, and prove that for polynomial-query black box compilers, the per-edge error rate tolerated by this last compiler is within a constant factor of optimal.

Beyond the Richter-Thomassen Conjecture

As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any $n$ pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least $(1-o(1))n^2$.

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions

On the switch Markov chain for perfect matchings

Constructive algorithm for path-width of matroids

such a linear layout is said to have width at most $k$.

When restricted to $1$-dimensional subspaces, this problem is equivalent to computing the path-width of an $\mathbb F$-represented matroid in matroid theory and computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory.

We present a fixed-parameter tractable algorithm to construct a linear layout of width at most $k$, if it exists, for input subspaces of a finite-dimensional vector space over $\mathbb F$. As corollaries, we obtain a fixed-parameter tractable algorithm to produce a path-decomposition of width at most $k$ for an input $\mathbb F$-represented matroid of path-width at most $k$, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most $k$ for an input graph of linear rank-width at most $k$. In both corollaries, no such algorithms were known previously.

Our approach is based on dynamic programming combined with the idea developed by Bodlaender and Kloks (1996) for their work on path-width and tree-width of graphs.

It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width; a theorem by Geelen, Gerards, and Whittle~(2002) implies that for each fixed finite field $\mathbb F$, there are finitely many forbidden $\mathbb F$-representable minors for the class of matroids of path-width at most $k$. An algorithm by Hlin{\v e}n{\'y} (2006) can detect a minor in an input $\mathbb F$-represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition even if the complete list of forbidden minors were known.

Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.

Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics

We give a randomized polynomial time approximation scheme (PTAS) when the regions are fat weakly disjoint. This notion of regions was first defined when a QPTAS was given for the problem in [SODA 2010: Chan and Elbassioni]. We combine the techniques in the previous work, together with the recent PTAS for TSP [STOC 2012: Bartal, Gottlieb and Krauthgamer] to achieve a PTAS for TSPN. However, several non-trivial technical hurdles need to be overcome for applying the PTAS framework to TSPN.

(1) Heuristic to detect sparse instances. In the STOC 2012 paper, a minimum spanning tree heuristic is used to estimate the portion of an optimal tour within some ball. However, for TSPN, it is not known if an optimal tour would use points inside the ball to visit regions that intersect the ball.

(2) Partially cut regions in the recursion. After a sparse ball is identified by the heuristic, the PTAS framework for TSP uses dynamic program to solve the instance restricted to the sparse ball, and recursively solve the remaining instance. However, for TSPN, it is an important issue to decide whether each region partially intersecting the sparse ball should be solved in the sparse instance or considered in the remaining instance.

Surprisingly we show that both issues can be resolved by conservatively making the ball in question responsible for all intersecting regions. In particular, a sophisticated charging argument is needed to bound the cost of combining tours in the recursion.

Moreover, more refined procedures are used to improve the dependence of the running time on the doubling dimension $k$

from the previous $\exp[O(1)^{k^2}]$ (even for just TSP) to $\exp[O(1)^{O(k \log k)}]$.

Finding perfect matchings in bipartite hypergraphs

We prove the existence of an efficient algorithm to find perfect matchings in bipartite hypergraphs whenever a stronger version of Haxell’s condition holds. Our algorithm can be seen as a generalization of the classical Hungarian algorithm for finding perfect matchings in bipartite graphs. The techniques we use to achieve this result could be of use more generally in other combinatorial problems on hypergraphs where disjointness structure is crucial, e.g. Set Packing.

How to Play Multichannel Rendezvous Games with Public Randomness

settings: Two players are equipped with radios that may be tuned to

channels in potentially different subsets, $S_1$ and $S_2$, of a

universe of $n$ channels. In order to discover each other, the

players must tune to the same channel at the same time. The behavior

of each player is determined by a potentially randomized channel

schedule, which determines which channel the player tunes for each

positive time $t$; the challenge is to guarantee that the players

discover each other as quickly as possible. This is precisely the

``blind rendezvous problem'' studied in the popular cognitive radio

setting.

The problem is complicated by the fact that there is no notion of

identity: the channel schedule of a player may depend only on the

player's channel subset; furthermore, the players may have commenced

their schedules at different times and may be brought together at

arbitrary points in their schedules. In prior

work~\cite{CRSS:Deterministic} it was shown that

\emph{deterministic} schedules can guarantee rendezvous in time

$O(|S_1|\cdot|S_2|\log\log n)$.

These schedules require quadratic time to rendezvous, which is

impractical for typical applications with large channel universes.

In this paper, we beat this quadratic barrier by utilizing a public

source of randomness---a \emph{random beacon} that outputs a random

bit during each time step---to achieve rendezvous in expected time

\[

O\left(\log n + \frac{|S_1 \cup S_2|}{|S_1 \cap S_2|}\right)\,.

\]

As it happens, existing practical environments can indeed yield such

a public source of randomness. Observe that this is always at most

linear in $n$ and offers an exponential speedup when channel subsets

and their intersection are constant fractions of the universe. We

achieve these results by combining minwise independence with a novel

pseudo-random tool, the \emph{synchronizing disperser}. Typical

dispersers permit efficient use of randomness for hitting witness

sets; our synchronizing disperser does more, permitting two nodes

with differing views of the shared randomness (on account of their

different starting times) to extract common pseudorandom samples

efficiently. Our construction draws heavily on the expansion

properties of Cayley graphs and may be of independent

interest. Finally, we counterbalance this result by establishing an

$\Omega(|S_1|\cdot|S_2|)$ lower bound on the time to rendezvous with

any amount of private randomness but no public randomness.

Deterministic Algorithms for Submodular Maximization Problems

In this work we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic 1/2-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

Persistent Homology and Nested Dissection

Scheduling Parallel DAG Jobs Online to Minimize Average Flow Time

Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff

Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver

Although positive LPs can be solved in polylogarithmic depth while using only $log^2 n/eps^3$ parallelizable iterations [3], the best known positive SDP solvers due to Jain and Yao [18] require $log^{14}(n) /eps^{13}$ parallelizable iterations. Several alternative solvers have been proposed to reduce the exponents in the number of iterations [19, 29]. However, the correctness of the convergence analyses in these works has been called into question [29], as they both rely on algebraic monotonicity properties that do not generalize to matrix algebra.

In this paper, we propose a very simple algorithm based on the optimization framework proposed in [3] for LP solvers. Our algorithm only needs $log^2 n / eps^3$ iterations, matching that of the best LP solver. To surmount the obstacles encountered by previous approaches, our analysis requires a new matrix inequality that extends Lieb-Thirring's inequality, and a sign-consistent, randomized variant of the gradient truncation technique proposed in [2, 3].

Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture

The foundational and most studied problem in this second approach is a conjecture of these authors on bridge-addable classes that we prove in this paper. A class of graphs is \emph{bridge-addable} if any graph obtained by adding an edge between two connected components of a graph in the class is also in the class. Examples of bridge-addable classes include forests, planar graphs, graphs with bounded treewidth, or graphs excluding any 2-connected minor. We prove that a random graph from a bridge-addable class is connected with probability at least $e^{-\frac{1}{2}} + o(1)$, when its number of vertices tends to infinity.

This lower bound is tight since it is reached for forests. The best previously known constants where $e^{-1}$, $e^{-0.7983}$ and $e^{-2/3}$ proved respectively by McDiarmid, Steger and Welsh, by Balister, Bollob\'as and Gerke, and by Norin.

Expanders via Local Edge Flips

Our main result is to prove that a natural instantiation of the random flip produces an expander in at most $O(n^2 d^2 \sqrt{\log n})$ steps, with high probability. Our argument uses a potential-function analysis based on the matrix exponential, together with the recent beautiful results on the higher-order Cheeger inequality of graphs. We also show that our technique can be used to analyze another well-studied random process known as the `random switch', and show that it produces an expander in $O(n d)$ steps for $d=\Omega(\log n)$, with high probability.

An improved bound on fraction of correctable deletions

deletions. For any fixed $k \ge 2$, we construct a

family of codes over alphabet of size $k$ with positive rate,

which allow efficient recovery from a worst-case deletion

fraction approaching $1-\frac{2}{k+1}$. In particular, for binary

codes, we are able to recover a fraction of deletions approaching

$1/3$. Previously, even non-constructively the largest deletion

fraction known to be correctable with positive rate was

$1-\Theta(1/\sqrt{k})$, and around $0.17$ for the binary case.

Our result pins down the largest fraction of correctable deletions for

$k$-ary codes as $1-\Theta(1/k)$, since $1-1/k$ is an upper bound even

for the simpler model of erasures where the locations of the missing

symbols are known.

Closing the gap between $1/3$ and $1/2$ for the limit of worst-case

deletions correctable by binary codes remains a tantalizing open

question.

An Efficient Algorithm for Computing High Quality Paths amid Polygonal Obstacles

Locality-sensitive Hashing without False Negatives

The construction is efficient in the sense that the expected number of hash collisions between vectors at distance cr, for a given c>1, comes close to that of the best possible data independent LSH without the covering guarantee, namely, the seminal LSH construction of Indyk and Motwani (FOCS '98).

The efficiency of the new construction essentially *matches* their bound if cr = log(n)/k, where n is the number of points in the data set and k>0 is integer, and differs from it by at most a factor ln(4)<1.4 in the exponent for general values of cr. As a consequence, LSH-based similarity search in Hamming space can avoid the problem of false negatives at little or no cost in efficiency.

Approximation of non-boolean 2CSP

Games Conjecture, this is the best possible approximation up to constant factors.

Previously, a $1/R$-approximate algorithm was known, based on linear programming. Our algorithm is based on semidefinite programming. The Semidefinite Program that we use has an almost-matching integrality gap.

For the more general Max $k$CSP-$R$, in which each constraint involves $k$ variables, each ranging over a set of size $R$, it was known that the best possible approximation is of the order of $k/R^{k-1}$, provided that $k$ is sufficiently large compared to $R$; our algorithm shows that the bound $k/R^{k-1}$ is not tight for $k=2$.

On the Complexity of Dynamic Mechanism Design

Treetopes and their Graphs

Improved Approximation Algorithms for k-Submodular Function Maximization

lon>0$ a $((k+1)/2k+\varepsilon)$-approximation algorithm for maximizing monotone $k$-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight.

We also extend the approach to provide constant factor approximation algorithms for maximizing skew-bisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.

Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile

Our approach is based on a method to analyze solutions of Laplacian systems, and this allows us to extend the results to local graph partitioning algorithms. In particular, we show that our approach can be used to analyze personal pagerank vectors, and to give a local graph partitioning algorithm for the small-set expansion problem with performance guarantees similar to the generalizations of Cheeger's inequality. We also present a spectral approach to prove similar results for the truncated random walk algorithm. These show that local graph partitioning algorithms almost match the performance of the spectral partitioning algorithm, with the additional advantages that they apply to the small-set expansion problem and their running time could be sublinear. Our techniques provide common approaches to analyze the spectral partitioning algorithm and local graph partitioning algorithms.

Bounds for Random Constraint Satisfaction Problems via Spatial Coupling

Online Degree-Bounded Steiner Network Design

The degree-bounded Steiner tree problem -- which

asks for a subgraph with minimum degree that connects a

given set of vertices -- is perhaps one of the

most representative problems in this class. This paper

deals with its well-studied generalization called the

degree-bounded Steiner forest problem where the connectivity

demands are represented by vertex pairs that need to be individually connected.

In the classical online model, the input graph is

given offline but the demand pairs arrive sequentially

in online steps. The selected subgraph starts off as the

empty subgraph, but has to be augmented to satisfy

the new connectivity constraint in each online step.

The goal is to be competitive against an adversary that knows the input in advance.

The standard techniques for solving degree-bounded problems often fall in the category of \textit{iterative} and \textit{dependent} rounding techniques. Unfortunately, these rounding methods are inherently difficult to adapt to an online settings since the underlying fractional solution may change dramatically in between the rounding steps. Indeed, this might be the very reason that despite many advances in the online network design paradigm in the past two decades, the natural family of degree-bounded problems has remained widely open.

In this paper, we design an intuitive greedy-like algorithm that achieves a competitive

ratio of $O(\log n)$ where $n$ is the number of vertices.

We show that no (randomized) algorithm can achieve a (multiplicative)

competitive ratio $o(\log n)$; thus our result is asymptotically tight.

We further show strong hardness results for the group Steiner tree and

the edge-weighted variants of degree-bounded connectivity problems.

F{\"u}rer and Raghavachari resolved the offline variant of degree-bounded

Steiner forest in their paper in SODA'92. Since then, the family of

degree-bounded network design problems has been extensively studied in the

literature resulting in the development of many interesting tools and

numerous papers on the topic.

We hope that our approach and its dual analysis, paves the way for solving the

\textit{online} variants of the classical problems in this family of problems.

Weighted dynamic finger in binary search trees

Approximating Low-Stretch Spanners

For basic $(2k-1)$-spanner, we first show an integrality gap for the natural flow-based LP (the main tool in almost all nontrivial spanner approximations) which nearly matches the trivial $O(n^{1/k})$-approximation. For small stretch there is still room for improvement, though, so we also design an $\tO(n^{1/3})$-approximation for $4$-spanner (both basic and directed). This was the last value of $k$ for which only an $O(\sqrt{n})$-approximation was known for basic $k$-spanner, and thus implies that for any $k$ the approximation ratio is at most $\tO(n^{1/3})$.

For $f$-fault tolerant spanners, we show that in the small-stretch setting ($k \in \{3,4\}$) it is possible to entirely remove the dependence on $f$ from the approximation ratio, at the cost of moving to bicriteria guarantees. The previous best dependence on $f$ was either linear (in the stretch $3$ case) or exponential (for stretch $4$).

Independence and Efficient Domination on $P_6$-free Graphs

Using the combinatorial tools that we develop for the above algorithm, we also give a polynomial-time algorithm for Efficient Dominating Set on $P_6$-free graphs. In this problem, the input is a graph $G$, every vertex has an integer weight, and the objective is to find a set $S$ of maximum weight such that every vertex in $G$ has exactly one vertex in $S$ in its closed neighborhood, or to determine that no such set exists. Prior to our work, the class of $P_6$-free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of Efficient Dominating Set was unknown.

Non-convex Compressed Sensing with the Sum-of-Squares Method

Although a small value of q is favorable for measuring the distance to sparse vectors, previous methods for q < 1 involve q quasi-norm minimization which is computationally intractable. In this paper, we overcome this issue by using the sum-of-squares method, and give the first polynomial-time stable recovery scheme for a large class of matrices A in q quasi-norm for any fixed constant 0 < q ≤ 1.

Make-to-Order Integrated Scheduling and Distribution

The main challenge is to design algorithms that optimize operational performance by jointly scheduling production and delivery of customer orders. In this paper we study a model of scheduling customer orders on multiple identical machines and their distribution

to customers afterwards.

The goal is to minimize the total time from release to distribution plus total distribution cost to the customers.

We design the first poly-logarithmic competitive algorithm for the problem (previously only linear competitive algorithms were known).

Our model generalizes two fundamental problems: scheduling of jobs on multiple identical machines

(where the goal function is to minimize the total flow time) as well as the TCP Acknowledgment problem.

The Complexity of All-switches Strategy Improvement

Communication with Contextual Uncertainty

A naive solution would be for Alice and Bob to first agree on some common function h that is close to both f and g and then use a protocol for h to compute h(x,y). We show that any such agreement leads to a large overhead in communication ruling out such a universal solution.

In contrast, we show that if g has a one-way communication protocol with complexity k in the standard setting, then it has a communication protocol with complexity O(k(1+I)) in the uncertain setting, where I denotes the mutual information between x and y. In the particular case where the input distribution is a product distribution, the protocol in the uncertain setting only incurs a constant factor blow-up in communication and error.

Furthermore, we show that the dependence on the mutual information I is required. Namely, we construct a class of functions along with a non-product distribution over (x,y) for which the communication complexity is a single bit in the standard setting but at least Omega(\sqrt{n}) bits in the uncertain setting.

Dynamic (1 + \eps)-Approximate Matchings: A Density-Sensitive Approach

Gupta and Peng [FOCS'13] presented a deterministic algorithm for maintaining fully dynamic $(1+\eps)$-approximate maximum cardinality matching (MCM) in general graphs with worst-case update time $O(\sqrt{m} \cdot \eps^{-2})$, for any $\eps > 0$, where $m$ denotes the current number of edges in the graph.

Despite significant research efforts, this $\sqrt{m}$ update time barrier remains the state-of-the-art even if amortized time bounds and randomization are allowed or the approximation factor is allowed to increase from $1+\eps$ to $2-\eps$, and even in basic graph families such as planar graphs.

This paper presents a simple deterministic algorithm whose performance depends on the \emph{density} of the graph.

Specifically, we maintain fully dynamic $(1+\eps)$-approximate MCM with worst-case update time $O(\alpha \cdot \eps^{-2})$ for graphs with \emph{arboricity} bounded by $\alpha$.

(The arboricity of a graph is the minimum number of edge-disjoint forests into which it can be partitioned, and it is close to the density of its densest subgraph.)

The update time bound holds even if the arboricity bound $\alpha$ changes dynamically.

Since the arboricity ranges between $1$ and $\sqrt{m}$, our density-sensitive bound $O(\alpha \cdot \eps^{-2})$ naturally generalizes the $O(\sqrt{m} \cdot \eps^{-2})$ bound of Gupta and Peng.

For the family of constant arboricity graphs (which includes forests, planar graphs, and graphs excluding a fixed minor),

in the regime $\eps = O(1)$ our update time reduces to a constant.

This should be contrasted with the previous best 2-approximation results for constant arboricity graphs,

which achieve either an $O(\log n)$ worst-case bound (Kopelowitz et al., ICALP'14) or an $O(\sqrt{\log n})$ amortized bound (He et al., ISAAC'14), where $n$ stands for the number of vertices in the graph.

En route to this result, we provide \emph{local} algorithms of independent interest for maintaining fully dynamic approximate matching and vertex cover.

Clustering time series under the Frechet distance

An O(log m)-Competitive Algorithm for Online Machine Minimization

The following two key components lead to our new result. Firstly, we derive a new lower bound on the optimum value that relates the laxity and the number of jobs with intersecting time windows. Then, we design a new algorithm that is tailored to this lower bound and balances the delay of jobs by taking the number of currently running jobs into account.

Jointly Private Convex Programming

by private information from agents, when the solution can be naturally

partitioned among the agents. This class of problems includes multi-commodity

flow problems, general allocation problems, and multi-dimensional knapsack

problems, among other examples. The accuracy of our algorithm depends on the

number of coupling constraints, which bind multiple agents. On the

other hand, our accuracy is nearly independent of the number of variables, and

in many cases, actually improves as the number of agents increases. A special

case of our result (solving general allocation problems beyond ``Gross

Substitute'' preferences) resolves the main open problem from [Hsu et al. STOC

2014].

We also consider strategic agents who have preferences over their part of the

solution. For any convex program in our class that maximizes social

welfare, we show how to create an approximately dominant strategy

truthful mechanism, approximately maximizing welfare. The central idea is to

charge agents prices based on the approximately optimal dual variables, which

are themselves computed under differential privacy. Our results substantially

broaden the class of problems that are known to be solvable under privacy

and/or incentive constraints.

Local-on-Average Distributed Tasks

constant, otherwise it is {\em global}. Unfortunately, local tasks

are relatively scarce, and most distributed tasks require time at least

logarithmic in the network size (and often higher than that).

In a dynamic setting, i.e., when the network undergoes repeated and frequent

topological changes, such as vertex and edge insertions and deletions,

it is desirable to be able to perform a {\em local} update procedure around

the modified part of the network, rather than running a static {\em global}

algorithm from scratch following each change.

This paper makes a step towards establishing the hypothesis that

many (statically) {\em non-local} distributed tasks are

{\em local-on-average} in the dynamic setting, namely,

their \emph{amortized} time complexity is $O(\log^* n)$.

Towards establishing the plausibility of this hypothesis, we

develop a technique for transforming static $O(\polylog(n))$ time algorithms

into dynamic $O(\log^* n)$ amortized time update procedures. We then apply this

method to several fundamental problems whose static time complexity

is logarithmic, including forest-decomposition, edge-orientation

and coloring sparse graphs, and show that their amortized time complexity in the dynamic setting is indeed $O(\log^* n)$.

Stabilizing Consensus with Many Opinions

complete communication network of size $n$ initially holds an \emph{opinion},

which is chosen arbitrarily from a finite set $\Sigma$. The

system must converge toward a consensus state in which all, or almost all

nodes, hold the same opinion. Moreover, this opinion should be \emph{valid},

i.e., it should be one among those initially present in the system. This

condition should be met even in the presence of an adaptive, malicious

adversary who can modify the opinions of a bounded number of nodes in every

round.

We consider the \emph{3-majority dynamics} in the \emph{Uniform-Gossip} model:

An efficient protocol in which, in every round, each node revises its opinion

on the basis of the opinions held in the previous round by 3 randomly chosen

neighbors (with ties broken arbitrarily). Let $k$ be the number of (initial)

valid opinions. We show that, for any $\alpha < 1/3$ and for $k =

\mathcal{O}(n^{\alpha})$, the 3-majority dynamics converges in time polynomial in $k$ and

$\log n$ even in the presence of an adversary who can affect up to

$o(\sqrt{n})$ nodes at each round.

Previously, the convergence of the 3-majority protocol was known for $|\Sigma|

= 2$ only, with an argument that is robust to adversarial errors. On the other

hand, no anonymous uniform-gossip protocol that is robust to

adversarial errors was known for $|\Sigma| > 2$.

Near-Optimal Light Spanners

is a ``sparse" subgraph that approximately preserves distances between every pair of nodes.

The stretch of spanner is said to be $k$ (also referred to as $k$-spanner for short) if $\dist(s,t,H) \leq k \cdot \dist(s,t,G)$, where $\dist(s,t,H')$ for a subgraph $H'$ is the distance from $s$ to $t$ in $H'$.

Two main measures of the sparseness of the spanner are the size (number of edges) and the total weight (the sum of the weights of the edges in the spanner).

It is well-known that one can efficiently construct a $(2k-1)$-spanner with $O(n^{1+1/k})$ number of edges \cite{ADDJS93}.

This size-stretch tradeoff is conjectured to be optimal based on the girth conjecture of Erd\H{o}s \cite{Er64}.

However, the current state of the art for the second measure is not yet optimal.

Recently Elkin, Neiman and Solomon [ICALP 14] improved the state of the art by presenting an improved analysis of the greedy algorithm,

proving that the greedy algorithm admits $(2k-1) \cdot (1+\eps)$-stretch and total edge weight of $O_{\eps}(k/\log{k} \cdot \omega(MST(G))\cdot n^{1/k})$, where

$\omega(MST(G))$ is the weight of the minimum spanning tree of $G$.

The previous analysis by Chandra \etal [SOCG 92] admitted

$(2k-1)\cdot (1+\eps)$-stretch and total edge weight of $O_{\eps}(k \omega(MST(G)) n^{1/k})$.

Hence, Elkin \etal improved the weight of the spanner by a $\log{k}$ factor.

In the work, we complectly remove the $k$ factor from the weight, presenting a spanner with $(2k-1)\cdot (1+\eps)$-stretch,

$O_{\eps}(\omega(MST(G)) n^{1/k})$ total weight and $O(n^{1+1/k})$ number of edges.

Up to $(1+\eps)$ factor in the stretch this matches the girth conjecture of Erd\H{o}s \cite{Er64}.

Algorithms and Adaptivity Gaps for Stochastic Probing

values are independent random variables. The algorithm knows the

distributions of these variables, but not the actual outcomes. The

only way to learn the actual outcomes is to probe these elements.

However, there are constraints on which set of elements may be

probed. (E.g., we may have to travel in some metric to probe elements

and have limited time.) These constraints are called outer

constraints. We want to develop an algorithm that picks some set of

elements to maximize the (expected) value, subject to the picked

subset of elements satisfying some other set of constraints, called

the inner constraints. Such problems were studied for both inner and

outer constraints being matroid intersections; these modeled problems

like kidney matching and Bayesian auctions. One limitation of past

work was their reliance on linear-programming-like techniques,

which meant going beyond matroid-like structures was difficult.

In this work, we give a very general adaptivity gap result that holds for all

prefix-closed outer constraints, as long as the inner constraints are

matroid intersections. The adapativity gap is O(log n) for any

constant number of inner matroid constraints. We feel prefix-closedness

captures all "reasonable" outer constraints, like orienteering, connectivity, and

precedence. Based on this we give the first approximation algorithms

for such stochastic probing problems. These have applications, e.g., to

path-planning and precedence-constrained scheduling problems.

Balanced Allocation: Patience is not a Virtue

Here, we present a fully decentralized and easy-to-implement algorithm called $\mathsf{FirstDiff}[d]$ that combines the simplicity of $\mathsf{Greedy}[d]$ and the improved balance of $\mathsf{Left}[d]$. The key idea in $\mathsf{FirstDiff}[d]$ is to probe until a different bin size from the first observation is located, then place the ball. Although in the abstract the number of probes could be quite large, we show that $\mathsf{FirstDiff}[d]$ requires $d$ probes on average per ball (in both the standard and heavily-loaded settings). Thus the number of probes is no greater than either that of $\mathsf{Greedy}[d]$ or $\mathsf{Left}[d]$. More importantly, we show that $\mathsf{FirstDiff}[d]$ closely matches the improved maximum load ensured by $\mathsf{Left}[d]$ in both the standard and heavily-loaded settings. We additionally give experimental data that $\mathsf{FirstDiff}[d]$ is indeed as good as $\mathsf{Left}[d]$, if not better, in practice.

Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting

This paper addresses the general limit of the mentioned tractability results for CSP and #CSP, that they only apply to instances where all constraints belong to a single tractable language (in general, the union of two tractable languages isn’t tractable). We show that we can overcome this limitation as long as we keep some control of how constraints over the various considered tractable languages interact with each other. For this purpose we utilize the notion of a strong backdoor of a CSP instance, as introduced by Williams et al. (IJCAI 2003), which is a set of variables that when instantiated moves the instance to an island of tractability, i.e., to a tractable class of instances. We consider strong backdoors into scattered classes, consisting of CSP instances where each connected component belongs entirely to some class from a list of tractable classes. Figuratively speaking, a scattered class constitutes an archipelago of tractability. The main difficulty lies in finding a strong backdoor of given size k; once it is found, we can try all possible instantiations of the backdoor variables and apply the polynomial time algorithms associated with the islands of tractability on the list component wise. Our main result is an algorithm that, given a CSP instance with n variables, finds in time f(k)*poly(n) a strong backdoor into a scattered class (associated with a list of finite conservative constraint languages) of size k or correctly decides that there isn’t such a backdoor. This also gives the running time for solving (#)CSP, provided that (#)CSP is polynomial-time tractable for the considered constraint languages. Our result makes significant progress towards the main goal of the backdoor-based approach to CSPs – the identification of maximal base classes for which small backdoors can be detected efficiently.

Windrose Planarity: Embedding Graphs with Direction-Constrained Edges

Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a combinatorial embedding that is given as part of the input. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph admitting a windrose-planar drawing we show how to construct one with at most one bend per edge on an $O(n) \times O(n)$ grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

Random-cluster Dynamics in Z^2

The Restricted Isometry Property of Subsampled Fourier Matrices

Communication Complexity of Permutation-Invariant Functions

Efficient Low-Redundancy Codes for Correcting Multiple Deletions

For any fixed k, we construct a binary code with c_k log n redundancy that can be decoded from k deletions in O_k(n log^4 n) time. The coefficient c_k can be taken to be O(k^2 log k), which is only quadratically worse than the optimal, non-constructive bound of O(k). We also indicate how to modify this code to allow for a combination of up to k insertions and deletions.

We also note that amongst linear codes capable of correcting k deletions, the (k+1)-fold repetition code is essentially the best possible.

Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders

\begin{enumerate}

\item For any $\alpha>0$, $\delta>0$, and a random bipartite graph $G$ with left degree $D=O(\log N)$, we prove that the Lasserre hierarchy cannot distinguish whether $G$ is an $(N^{\alpha},(1-\delta)M)$-disperser or not an $(N^{1-\alpha},\delta M)$-disperser.

\item For any $\rho>0$, we prove that there exists infinitely many constants $d$ such that the Lasserre hierarchy cannot distinguish whether a random bipartite graph $G$ with right degree $d$ is a $(\rho N, (1-(1-\rho)^d)M)$-disperser or not a $(\rho N, (1-\Omega(\frac{1-\rho}{\rho d + 1-\rho}))M)$-disperser. We also provide an efficient algorithm to find a subset of size exact $\rho N$ that has an approximation ratio matching the integrality gap within an extra loss of $\frac{\min\{\frac{\rho}{1-\rho},\frac{1-\rho}{\rho}\}}{\log d}$.

\end{enumerate}

Our method gives an integrality gap in the Lasserre hierarchy for bipartite expanders with left degree~$D$. $G$ on $([N],[M])$ is a $(\rho N,a)$-expander if for any subset $S\subseteq [N]$ of size $\rho N$, the neighbor set $\Gamma(S)$ contains at least $a \cdot \rho N$ distinct vertices. We prove that for any constant $\epsilon>0$, there exists constants $\epsilon'<\epsilon,\rho,$ and $D$ such that the Lasserre hierarchy cannot distinguish whether a bipartite graph on $([N],[M])$ with left degree $D$ is a $(\rho N, (1-\epsilon')D)$-expander or not a $(\rho N, (1-\epsilon)D)$-expander.

On the Economic Efficiency of the Combinatorial Clock Auction

This has provided for a practical examination of an assortment of auction mechanisms and, amongst these,

two simultaneous ascending price auctions have proved to be extremely successful.

These are the simultaneous multiround ascending auction (SMRA) and the combinatorial

clock auction (CCA). It has long been known that, for certain classes of valuation functions,

the SMRA provides good theoretical guarantees on social welfare.

However, no such guarantees were known for the CCA.

In this paper, we show that CCA does provide strong guarantees on social welfare {\em provided}

the price increment and stopping rule are well-chosen.

This is very surprising in that the choice of price increment has been used primarily

to adjust auction duration and the stopping rule has attracted little attention.

The main result is a polylogarithmic approximation guarantee for

social welfare when the maximum number of items demanded $\C$ by a bidder is fixed.

Specifically, we show that either the revenue of the CCA is at least

an $\Omega\Big(\frac{1}{\C^{2}\log n\log^2m}\Big)$-fraction of the optimal welfare or

the welfare of the CCA is at least an $\Omega\Big(\frac{1}{\log n}\Big)$-fraction of the optimal

welfare, where $n$ is the number of bidders and $m$ is the number of items. As a corollary,

the welfare ratio -- the worst case ratio between the social welfare of the

optimum allocation and the social welfare of the CCA allocation -- is at most $O(\C^2 \cdot \log n \cdot \log^2 m)$.

We emphasize that this latter result requires no assumption on bidders valuation functions.

Finally, we prove that such a dependence on $\C$ is necessary. In particular, we show that the

welfare ratio of the CCA is at least $\Omega \Big(\C \cdot \frac{\log m}{\log \log m}\Big)$.

The Matching Problem Has No Small Symmetric SDP

symmetric linear program. Rothvoss (2014)

recently proved that any, not necessarily symmetric, linear program

also has exponential size. It is natural to ask whether the matching

problem can be expressed compactly in a framework such as

semidefinite programming (SDP) that is more powerful than linear

programming but still allows efficient optimization.

We answer this question negatively for symmetric SDPs: any symmetric

SDP for the matching problem has exponential size.

We also show that an O(k)-round Lasserre SDP relaxation for the

asymmetric metric traveling salesperson problem yields at least as good an approximation

as any symmetric SDP relaxation of size n^{k}.

The key technical ingredient underlying both these results is an upper

bound on the degree needed to derive polynomial identities that hold

over the space of matchings or traveling salesperson tours.

Packing Small Vectors

We give improved results for the two dimensional case. For arbitrarily small vectors, the first fit algorithm for two dimensional vector packing is no better than 2-competitive. We present a natural family of first fit variants, and for optimized parameters get a competitive ratio $\approx 1.48$ for sufficiently small vectors.

We improve upon the $1.48$-competitive ratio -- not via a first fit variant -- and give a competitive ratio arbitrarily close to $4/3$ for packing small, two dimensional vectors. We show that no algorithm can achieve better than a $4/3$ competitive ratio for two dimensional vectors, even if one allows the algorithm to split vectors amongst arbitrarily many bins.

Sparse Approximation via Generating Point Sets

Our result can be viewed as a method for sparse, convex autoencoding: approximately representing the data in a compact way using sparse combinations of a small subset $\algset$ of the original data. The new algorithm can be kernelized, and it preserves sparsity in the original input.

Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching

New Bounds for Approximating Extremal Distances in Undirected Graphs

All the known exact algorithms achieve α=1, β=0 and γ=2. A single graph search yields α=2 for the diameter and the radius and α=3 for the eccentricities, all with β=0 and γ=1. Roditty and Vassilevska W. [STOC13] obtain α=3/2, β<1 and γ=3/2 for D and r. Chechik, Larkin, Roditty, Schoenebeck, Tarjan and Vassilevska W. [SODA14] give α=3/2 for D, r and α=5/3 for ε(v), all with β=0 and γ=3/2. Under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi and Zane [JCSS01], it is impossible for the diameter to get α<3/2, β=0, γ<2 [STOC13] and α<4/3, β=O(mᵟ), γ < 2 - 2δ for any δ≥0 [SODA14].

This paper contains the contributions summarized below.

First, we show under SETH that it is impossible to get α<3/2 for the diameter and α<5/3 for the eccentricities with β=O(mᵟ) and γ < 2 - 2δ for any δ ≥ 0. Thus, we tighten the above results for the diameter and the eccentricities. In particular, the recently achieved approximation factors α=3/2 for D and α=5/3 for ε(v) cannot be improved in truly sub-quadratic time (γ<2) even with a constant additive term β=O(1) under SETH: the eccentricities are more difficult to approximate than the diameter.

Second, we present an algorithmic scheme that gives nontrivial approximations with exponent γ = 1+∊ arbitrarily close to the optimum 1. Specifically, for any integer k ≥ 0, we present a randomized algorithm giving α = 2 - 1/2ᵏ for diameter and radius and α = 3 - 4/(2ᵏ+1) for eccentricities with β<1 in Õ(m n^{1/(k+1)}) expected time (thus γ = 1 + 1/(k+1)). For k ≥ 2, this gives a family of previously unknown bounds, and approaches near-linear running time as k grows.

Third, we observe a new connection between approximating the diameter and finding h-dominating sets, which are subsets of nodes at distance ≤ h from every other node. These sets could be of independent interest for other graph problems. Our algorithms discover an h-dominating set X for h ~ (α-1) D that is employed to give an α-approximation D̃ in Õ(|X| m) time. Since finding a smaller X would yield a faster algorithm, we give some lower bounds on the size of X in the worst case through explicit constructions. As an intriguing example, given any graph of diameter 4 our algorithms find a 3-dominating set of size Θ̃(n^{1/3}), which is proven to be tight up to poly-logs.

An Improved Distributed Algorithm for Maximal Independent Set

presents an extremely simple randomized algorithm providing a near-optimal local complexity for this problem, which incidentally, when combined with some known techniques, also leads to a near-optimal global complexity.

Classical MIS algorithms of Luby [STOC'85] and Alon, Babai and Itai [JALG'86] provide the global complexity guarantee that, with high probability, all nodes terminate after $O(\log n)$ rounds. In contrast, our initial focus is on the local complexity, and our main contribution is to provide a very simple algorithm guaranteeing that each particular node $v$ terminates after $O(\log deg(v)+\log 1/\epsilon)$ rounds, with probability at least $1-\epsilon$. The guarantee holds even if the randomness outside 2-hops neighborhood of $v$ is determined adversarially. This degree-dependency is optimal, due to a lower bound of Kuhn, Moscibroda, and Wattenhofer [PODC'04].

Interestingly, this local complexity smoothly transitions to a global complexity: by adding techniques of Barenboim, Elkin, Pettie, and Schneider [FOCS'12; arXiv: 1202.1983v3], we get a randomized MIS algorithm with a high probability global complexity of $O(\log \Delta) + 2^{O(\sqrt{\log \log n})}$, where $\Delta$ denotes the maximum degree. This improves over the $O(\log^2 \Delta) + 2^{O(\sqrt{\log \log n})}$ result of Barenboim et al., and gets close to the $\Omega(\min\{\log \Delta, \sqrt{\log n}\})$ lower bound of Kuhn et al.

Corollaries include improved algorithms for MIS in graphs of upper-bounded arboricity, or lower-bounded girth, for Ruling Sets, for MIS in the Local Computation Algorithms (LCA) model, and a faster distributed algorithm for the Lov\'{a}sz Local Lemma.

Fast Approximations for Matroid Intersection

We observe that a $(1-\epsilon)$-approximation for the maximum cardinality case can be obtained in $O(nk/\epsilon)$ independence queries by adapting Cunningham's algorithm. Our main contribution is a $(1-\epsilon)$ approximation algorithm for the weighted matroid intersection problem that requires $O(n k \log^2 (1/\epsilon) / \epsilon^2)$ independence queries and time.

How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness

The goal of this paper is to fix exponential backoff, particularly focusing on the case where processes arrive in an on-line, worst-case fashion. We present a relatively simple backoff protocol Re-Backoff that has, at its heart, a version of exponential backoff. It guarantees expected constant throughput with dynamic process arrivals and requires only an expected polylogarithmic number of access attempts per process.

Re-Backoff is also robust to periods where the shared resource is unavailable for a period of time. If it is unavailable for D time slots, Re-Backoff provides the following guarantees. When the number of packets is a finite n, the average expected number of access attempts for successfully sending a packet is O(log^2( n + D)). In the infinite case, the average expected number of access attempts for successfully sending a packet is O(log^2(\nc) + \log^2(D) )$ where \nc is the maximum number of processes that

are ever in the system concurrently.

Simple pricing schemes for consumers with evolving values

Our results assume that the buyer's value per usage evolves according to a Markov process that satisfies a martingale property. For our main result, we consider pricing mechanisms in which the seller offers the product for free for a certain number of uses, and then charges an appropriate fixed price per usage. We assume that the buyer responds by buying the product for as long as his value exceeds the fixed price. Importantly, the buyer does not need to know anything about how his future value will evolve, only how much he wants to use the product {\em right now}. This mitigation of risk yields a larger pool of buyers.

Evolutionary dynamics in finite populations mix rapidly

Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut

Consider a graph $G=(V, E)$ and a partitioning of $V$ into subsets of nodes $S_1$, ..., $S_{N}$, each inducing a connected subgraph $G[S_i]$. We define an $\alpha$-congestion shortcut with dilation $\beta$ to be a set of subgraphs $H_1$, ..., $H_{N} \subseteq G$, one for each subset $S_i$, such that:

(1) For each $i \in [1, N]$, the diameter of the subgraph $G[S_i]+H_i$ is at most $\beta$.

(2) For each edge $e\in E$, the number of subgraphs $G[S_i]+H_i$ containing $e$ is at most $\alpha$.

We prove that any partition of a $D$-diameter planar graph into individually-connected parts admits an $O(D\log D)$-congestion shortcut with dilation $O(D\log D)$, and we also present a distributed construction of it in $\tilde{O}(D)$ rounds. We moreover prove these parameters to be near-optimal; i.e., there are instances in which, unavoidably, $\max\{\alpha, \beta\} = \Omega(D\frac{\log D}{\log\log D})$.

Finally, we use low-congestion shortcuts, and their efficient distributed construction, to derive $\tilde{O}(D)$-round distributed algorithms for MST and Min-Cut, in planar networks. This complexity nearly matches the trivial lower bound of $\Omega(D)$. We remark that this is the first result bypassing the well-known $\tilde{\Omega}(D+\sqrt{n})$ existential lower bound of general graphs (see Peleg and Rubinovich [FOCS'99]; Elkin [STOC'04]; and Das Sarma et al. [STOC'11]) in a family of graphs of interest.

Improved Deterministic Algorithms for Linear Programming in Low Dimensions

Towards optimal deterministic coding for interactive communication

that simulate any interactive protocol both under adversarial and random errors,

and can approach rate 1.

For channels that flip bits with probability~$\epsilon<1/2$,

our coding scheme achieves a communication rate of $1 -\Theta\left(\sqrt{H({\eps})}\right)$ and

a failure probability of~$\exp(-n/ \log n)$ in length $n$ protocols. Prior to our work, all deterministic schemes (either efficient or not) had a rate bounded away from~$1$. Furthermore, the best failure probability achievable by an efficient deterministic protocol was only quasi-polynomial, i.e., of the form $\exp(- \log^{O(1)} n)$ (Braverman, ITCS 2012).

For channels in which an adversary controls the noise pattern our coding scheme can tolerate $O(1/\log n)$ fraction of errors with rate approaching 1. No similar deterministic and efficient

schemes were known with any constant rate.

Essential to both results is an explicit, efficiently encodable and decodable linear {\em tree-code} of length~$n$ that has a relative distance $\Theta(\eps/\log n)$ and a

rate~$1-\Theta(\epsilon)$, defined over a polynomial size alphabet. No nontrivial distance bound was known for any efficient constant rate tree-code.

The linearity of our code, and in particular the fact that it can be {\em systematic}, turns out to play an important role in approaching rate 1 for random and adversarial errors.

A central contribution of the paper in deriving our protocols for random and adversarial errors,

is a novel code-concatenation scheme, a notion standard in coding theory which we adapt for the interactive setting. We use the above tree-code as the ``outer code'' in this concatenation. The necessary deterministic ``inner code'' is achieved by a nontrivial derandomization of the probabilistic protocol of (Haeupler, STOC 2014). This deterministic coding scheme (with {\em exponential-time} preprocessing,

but applied here to $\log n$ bit blocks) can handle an $\epsilon$ fraction of adversarial errors with a communication rate of $1 - \Theta\left(\sqrt{H({\eps})}\right)$.

Towards Optimal Algorithms for Prediction with Expert Advice

Our analysis develops upper and lower bounds simultaneously, analogous to the primal-dual method. Our analysis of the optimal adversary goes through delicate asymptotics of the random walk of a particle between multiple walls. We use the connection we develop to random walks to derive an improved algorithm and regret bound for the case of 4 experts, and, provide a general framework for designing the optimal algorithm and adversary for an arbitrary number of experts.

Approximating capacitated $k$-median with $(1+\eps)k$ open facilities

In this paper, we give the first constant approximation for \CKM, that only violates the cardinality constraint by a factor of $1+\eps$. This generalizes the result of [Li15], which only works for the uniform capacitated case. Moreover, the approximation ratio we obtain is $O\big(\frac{1}{\eps^2}\log\frac1\eps\big)$, which is an exponential improvement over the ratio of $\exp(O(1/\epsilon^2))$ in [Li15]. The natural LP relaxation for the problem, which almost all previous algorithms for \CKM are based on, has unbounded integrality gap even if $(2-\eps)k$ facilities can be opened. We introduce a novel configuration LP for the problem, that overcomes this integrality gap.

Learning and Efficiency in Games with Dynamic Population

In this paper we analyze efficiency of repeated games in dynamically changing environments. An important trait of learning behavior is its versatility to changing environments, assuming that the learning method used is adaptive, i.e., doesn't rely too heavily on experience from the distant past. We show that, in large classes of games, if players choose their strategies in a way that guarantees low adaptive regret, high social welfare is ensured, even under very frequent changes.

A main technical tool for our analysis is the existence of a solution to the welfare maximization problem that is both close to optimal and relatively stable over time. Such a solution serves as a benchmark in the efficiency analysis of learning outcomes. We show that such a stable and close to optimal solution exists for many problems, even in cases when the exact optimal solution can be very unstable. We further show that a sufficient condition on the existence of stable outcomes is the existence of a differentially private algorithm for the welfare maximization problem. Hence, we draw a strong connection between differential privacy and high efficiency of learning outcomes in frequently changing repeated games.

We demonstrate our techniques by focusing on two classes of games as examples: independent item auctions and congestion games. In both applications we show that adaptive learning guarantees high social welfare even with surprisingly high churn in the player population.

Exact and Approximation Algorithms for Weighted Matroid Intersection

The core of our algorithms is a decomposition technique: we decompose the weighted version of the problem into a set of unweighted matroid intersection problems. The computational advantage of this approach is that we can then make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. To be precise, we show that we can find an exact solution via solving W unweighted matroid intersections problems, where W is the largest given weight. Furthermore, we can find a (1-\epsilon)-approximate solution via solving O(\epsilon^{-1} \log r) unweighted matroid intersection problems, where r is the smallest rank of the given two matroids.

Our algorithms are simple and flexible: they can be adapted to specific matroid intersection problems, making use of specialized unweighted matroid intersection algorithms. In this paper, we show the following results.

- Given two general matroids, using Cunningham's algorithm, we solve the problem exactly in O(\tau Wnr^{1.5}) time and (1-\epsilon)-approximately in O(\tau \epsilon^{-1}nr^{1.5}\log r) time, where \tau is the time complexity of an independence oracle call.

- Given two graphic matroids, using the algorithm of Gabow and Xu, we solve the problem exactly in O(W \sqrt{r}n \log r) time and (1-\epsilon)-approximately in

O( \epsilon^{-1} \sqrt{r}n \log^2r) time.

- Given two linear matroids (in the form of two r-by-n matrices), using the algorithm of Cheung, Kwok and Lau, we solve the problem exactly in O(nr \log r_*+ W n r_*^{\omega-1}) time and (1-\epsilon)-approximately in O(nr \log r_*+ \epsilon^{-1} n r_*^{\omega-1} \log r_* ) time, where r_* is the maximum size of a common independent set.

Finally, we give a further application of our decomposition technique. We use it to solve efficiently the rank-maximal matroid intersection problem, a problem motivated by matching problems under preferences.

Higher Lower Bounds from the 3SUM Conjecture

dynamic data structures and graph problems.

This line of work was initiated by Patrascu (STOC 2010)

who reduced 3SUM to an offline SetDisjointness problem.

However, the reduction introduced by Patrascu{} suffers from several inefficiencies,

making it difficult to obtain {\em tight} conditional lower bounds from the 3SUM conjecture.

In this paper we address many of the deficiencies of Patrascu's framework. We give new and efficient

reductions from 3SUM to offline SetDisjointness and offline SetIntersection (the reporting version of SetDisjointness)

which leads to polynomially higher lower bounds on several problems.

Using our reductions, we are able to show the essential optimality of several algorithms, assuming the 3SUM conjecture.

- Chiba and Nishizeki's $O(m\alpha)$-time algorithm (SICOMP 1985) for enumerating all

triangles in a graph with arboricity/degeneracy $\alpha$ is essentially optimal, for any $\alpha$.

- Bj{\o}rklund, Pagh, Williams, and Zwick's algorithm (ICALP 2014)a for listing $t$ triangles is essentially optimal

(assuming the matrix multiplication exponent is $\omega=2$).

- Any static data structure for SetDisjointness that answers queries in constant time must spend $\Omega(N^{2-o(1)})$

time in preprocessing, where $N$ is the size of the set system.

These statements were unattainable via Patrascu's reductions.

We also introduce several new reductions from 3SUM to pattern matching problems and dynamic graph problems.

Of particular interest are new conditional lower bounds for dynamic versions of Maximum Cardinality Matching,

which introduce a new technique for obtaining amortized lower bounds.

A polynomial time quantum algorithm for computing class groups and solving the principal ideal problem in arbitrary degree number fields

ideal class group and solving the principal ideal problem (PIP) in

arbitrary classes of number fields under the Generalized Riemann

Hypothesis. Previously, these problems were known to have polynomial time

solutions in classes of fixed degree number fields by a result of Hallgren

[Hallgren STOC05]. More recently, Biasse and Song [BiasseSong 15] showed

that the PIP could be solved in classes of totally real fields of

arbitrary degree (a special case relevant to cryptography) in polynomial

time by adapting the unit group algorithm of Eistentrager et al. [EHKS

STOC14].

Computing the class group and solving the PIP are fundamental problems in

number theory. In particular, they are connected to many unproven

conjectures in both analytic and algebraic number theory. Our algorithms

also directly apply to the computation of relative class groups and unit

groups, to the computation of ray class groups and to the the resolution

of norm equations. Moreover, the resolution of the PIP is a key component

in the cryptanalysis of cryptosystems based on the hardness of finding a

short generator in a principal ideal.

Unlike the previous methods, our strategy for computing the ideal class

group and solving the PIP consists of reducing these tasks to the

computation of S-unit groups. This is another fundamental problem in

number theory, and it is the first time that an algorithm for this task is

described without relying on oracles for the PIP and the ideal class

group. We show that S-units can be found in polynomial time on a quantum

computer by generalizing the recent work of Eisentrager et al. [EHKS

STOC14] on the computation of the unit group. Our main technical

contribution is an efficient quantum reduction from computing the S-units

to solving an instance of a generalized HSP problem on R^O(n), which

involves new results on the metrical properties of lattices. In addition,

we show how to convert the output into an exact compact representations,

which is convenient for further algebraic manipulations.

Improved Approximation for Vector Bin Packing

For the 2-dimensional case we give an asymptotic approximation guarantee of $1+\ln(1.5)+\epsilon \approx (1.405+\epsilon)$, improving upon the previous bound of $1+\ln 2+\epsilon \approx (1.693+\epsilon)$. We also give an almost tight $(1.5+\epsilon)$ absolute approximation guarantee, improving upon the previous bound of 2 by Kellerer and Kotov. For the $d$-dimensional case, we get a $1.5+\ln (\frac{d}2)+ o_d(1)+\epsilon$ guarantee, improving upon the previous $(1+\ln d+\epsilon)$ guarantee due to Bansal, Caprara and Sviridenko based on the Round & Approx (R & A) framework. Here $(1+ \ln d)$ was a natural barrier as rounding-based algorithms can not achieve better than $d$ approximation. We get around this by exploiting various structural properties of (near)-optimal packings, and using multi-objective multi-budget matching based techniques and expanding the R & A framework to go beyond rounding-based algorithms. Along the way we also prove several results that could be of independent interest.

Nearly Optimal NP-Hardness of Unique Coverage

For constant $k$, we prove that $1$-in-$k$ Hitting Set is NP-hard to approximate within a factor $O(\frac{1}{\log k})$. This improves the result of Guruswami and Zhou [SODA'11, ToC'12], who proved the same result assuming the Unique Games Conjecture. For Unique Coverage, we prove that it is hard to approximate within a factor $O(\frac{1}{\log^{1 - \epsilon} n})$ for any $\epsilon > 0$, unless NP admits quasipolynomial time algorithms. This improves the results of Demaine et al. [SODA'06, SICOMP'08], including their $\approx 1/\log^{1/3} n$ inapproximability factor which was proven under the Random 3SAT Hypothesis. Our simple proof combines ideas from two classical inapproximability results for Set Cover and Constraint Satisfaction Problem, made efficient by various derandomization methods based on bounded independence.

Weighted SGD for $\ell_p$ Regression with Randomized Preconditioning

\begin{compactitem}

\item

We propose a hybrid algorithm named \pcsgd that uses RLA techniques for preconditioning and constructing an importance sampling distribution, and then performs an SGD-like iterative process with weighted sampling on the preconditioned system.

\item

By rewriting the $\ell_p$ regression problem into a stochastic optimization problem, we connect \pcsgd to several existing $\ell_p$ solvers including RLA methods with algorithmic leveraging (RLA for short).

\item

We prove that \pcsgd inherits faster convergence rates that only depend on the lower dimension of the linear system, while maintaining low computation complexity.

Such SGD convergence rate is superior over other related SGD algorithm such as the weighted randomized Kaczmarz algorithm.

\item

Particularly, when solving $\ell_1$ regression, \pcsgd returns an approximate solution with $\epsilon$ relative error on the objective value in $\bigO(\log n \cdot \nnz(A) + \poly(d)/\epsilon^2)$ time.

This complexity is {\it uniformly} better than that of RLA methods in terms of both $\epsilon$ and $d$ when the problem is unconstrained.

In the presence of constraints, \pcsgd only has to solve a sequence of much simpler and smaller optimization problem over the same constraints which in general can be more efficient than solving the constrained subproblem required in RLA.

\item

For $\ell_2$ regression, \pcsgd returns an approximate solution with $\epsilon$ relative error on the objective value and solution vector in prediction norm in $\bigO(\log n \cdot \nnz(A) + \poly(d) \log(1/\epsilon) /\epsilon)$ time.

We show that when solving unconstrained $\ell_2$ regression, this complexity is comparable to that of RLA and is asymptotically better over several state-of-the-art solvers in the regime where the desired accuracy $\epsilon$, high dimension $n$ and low dimension $d$ satisfy $d\geq 1/\epsilon$ and $n \geq d^2/\epsilon$.

\end{compactitem}

Finally, the effectiveness of such algorithms is illustrated numerically on both synthetic and real datasets, and the results are consistent with our theoretical findings and demonstrate that \pcsgd converges to a medium-precision solution, e.g., $\epsilon=10^{-3}$, more quickly.

Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut

of its special cases, the {\em node-weighted} multiway cut problem

in {\em undirected} graphs. In {\sc Directed Multiway Cut} (\DirMC)

the input is an edge-weighted directed graph $G=(V,E)$ and a set of

$k$ terminal nodes $\{s_1,s_2,\ldots,s_k\} \subseteq V$; the goal is

to find a min-weight subset of edges whose removal ensures that there

is no path from $s_i$ to $s_j$ for any $i \neq j$. In {\sc

Node-weighted Multiway Cut} (\NodeMC) the input is a node-weighted

undirected graph $G$ and a set of $k$ terminal nodes

$\{s_1,s_2,\ldots,s_k\} \subseteq V$; the goal is to remove a

min-weight subset of nodes to disconnect each pair of

terminals. \DirMC admits a $2$-approximation \cite{NaorZ01}

and \NodeMC admits a $2(1-\frac{1}{k})$-approximation

\cite{GargVY04}, both via rounding of LP relaxations.

Previous rounding algorithms for these problems, from nearly twenty

years ago, are based on careful rounding of an {\em

optimum} solution to an LP relaxation. This is particularly true

for \DirMC for which the rounding relies on a custom LP formulation

instead of the natural distance based LP relaxation \cite{NaorZ01}.

In this paper we describe extremely simple and near linear-time

rounding algorithms for \DirMC and \NodeMC via a natural distance

based LP relaxation. The dual of this relaxation is a special case

of the maximum multicommodity flow problem. Our

algorithms achieve the same bounds as before but have the

significant advantage in that they can work with {\em any feasible}

solution to the relaxation. Consequently, in addition to obtaining

``book'' proofs of LP rounding for these two basic problems, we also

obtain significantly faster approximation algorithms by taking

advantage of known algorithms for computing near-optimal solutions

for maximum multicommodity flow problems. We also investigate

lower bounds for \DirMC when $k=2$ and in particular prove that

the integrality gap of the LP relaxation is $2$ even in directed

planar graphs.

Constant Factor Approximation for Subset Feedback Problems via a new LP relaxation

undirected graphs. The input to these problems is an undirected

graph $G=(V,E)$ and a set of $k$ terminals nodes $S =

\{s_1,s_2,\dots,s_k \} \subset V$. A cycle in $G$ is interesting if

it contains a terminal. In the Subset Feedback Edge Set problem

(\SFES) the edges are weighted and the goal is to remove a minimum

weight set of edges such that no interesting cycle remains. In the

Subset Feedback Vertex Set (\SFVS) the nodes are weighted and the

goal is to remove a minimum weight set of nodes such that no

interesting cycle remains.

A $2$-approximation is known for \SFES \cite{EvenNSZ00} and a

$8$-approximation is known for \SFVS \cite{EvenNZ00}. The algorithm

and analysis for \SFVS is very complicated. One reason for the difficulty

in addressing feedback problems in undirected graphs has been the lack of

LP relaxations with constant integrality gaps. The natural LP has

an $\Omega(\log n)$ integrality gap.

In this paper, we introduce new LP relaxations for \SFES and \SFVS

and show that the integrality gap of this LP relaxatoin is at most

$13$ for both \SFES and \SFVS. Our LP formulation and analysis are

intuitive and simple to understand. We believe that related

formulations and ideas would lead to an approximation ratio better

than $8$ for for \SFVS.

Clustering Problems on Sliding Windows

Babcock, Datar, Motwani and O'Callaghan~\cite{BDMO03}, which has remained unanswered for over a decade. Our algorithm uses $O(k^3 \log^6 n)$ space

and $\poly(k, \log n)$ update time. This is an exponential improvement on the space required by the technique due to Babcock, et al. We introduce a data structure that extends smooth histograms as introduced by Braverman and Ostrovsky~\cite{BO06} to operate on a broader class of functions. In particular, we show that using only polylogarithmic space we can maintain a summary of the current window from which we can construct an $O(1)$-approximate clustering solution.

Merge-and-reduce is a generic method in computational geometry for adapting offline algorithms to the insertion-only streaming model. Several well-known coreset constructions are maintainable in the insertion-only streaming model using this method, including well-known coreset techniques for the $k$-median and $k$-means problems in both low-and high-dimensional Euclidean spaces~\cite{HPM04,Ch09}. Previous work \cite{FS05} has adapted coreset techniques to the insertion-deletion model, but translating them to the sliding window model has remaineda challenge. We give the first algorithm that, given an insertion-only streaming coreset of space $s$ (maintained using merge-and-reduce method), maintains this coreset in the sliding window model using $O(s^2\epsilon^{-2}\log n)$ space.

For clustering problems, our results constitute the first significant step towards resolving problem number 20 from the List of Open Problems in Sublinear Algorithms~\cite{sublinear_open_20}.

Natural Algorithms for Flow Problems

New directions in nearest neighbor searching with applications to lattice sieving

For small A, these filters are very similar to the spherical locality-sensitive hash family (LSH) previously studied by Andoni et al. For A > 0 however we show we achieve a superior performance, provided we have access to an efficient oracle for finding relevant filters. Whereas LSH is limited by a performance parameter \rho > 1/(2c^2 - 1) for approximate NNS with approximation factor c, with spherical LSF we achieve values \rho < 1/(2c^2 - 1) with the exact exponent \rho depending on the density of the data set. For sparse data, we obtain \rho = 1/(2c^2 - 1).

To instantiate the above oracle, we replace the independent filters by filters from certain structured codes. We show that the additional structure in these codes does not significantly change the collision probabilities, while allowing efficient decoding for identifying relevant filters.

We finally apply this method to lattice sieving algorithms for solving the shortest vector problem (SVP) on lattices, and show that it leads to a heuristic time complexity of (3/2)^(n/2) ~ 2^0.292n for solving SVP in dimension n. This improves upon the current best algorithm for solving SVP which uses spherical LSH and runs in time 2^0.298n. Experiments with the GaussSieve validate the claimed speedup and show that this method may be practical as well, as the polynomial overhead is small.

Species Trees from Gene Trees Despite a High Rate of Lateral Genetic Transfer: A Tight Bound

In previous works, a natural stochastic model of LGT was introduced and it was shown that the species phylogeny can be reconstructed from gene trees despite surprisingly high rates of LGT. Both lower and upper bounds on this rate were obtained, but a large gap remained. Here we close this gap, up to a constant. Specifically, we show that the species phylogeny can be reconstructed perfectly even when each edge of the tree has a constant probability of being the location of an LGT event. Our new reconstruction algorithm builds the tree recursively from the leaves. We also provide a matching lower bound.

Undirected Graph Exploration with Θ(log log n) Pebbles

Algorithmic Complexity of Power Law Networks

The aim of this paper is to study the algorithmic complexity of such ``typical'' networks. The contribution of this work is twofold.

First, we define a deterministic condition for checking whether a graph has a power law degree distribution and experimentally validate it on real-world networks.

This definition allows us to derive interesting properties of power law networks. We observe that for exponents of the degree distribution in the range $[1,2]$ such networks exhibit double power law phenomenon that was observed for several real-world networks. Our observation indicates that this phenomenon could be explained by just pure graph theoretical properties.

The second aim of our work is to give a novel theoretical explanation why many algorithms run faster on real-world data than what is predicted by algorithmic worst-case analysis.

We show how to exploit the power law degree distribution to design faster algorithms for a number of classical P-time problems including transitive closure, maximum matching, determinant, PageRank and matrix inverse.

Moreover, we deal with the problems of counting triangles and finding maximum clique.

Previously, it has been only shown that these problems can be solved very efficiently on power law graphs when these graphs are random, e.g., drawn at random from some distribution. However, it is unclear how to relate such a theoretical analysis to real-world graphs, which are fixed.

Instead of that, we show that the randomness assumption can be replaced with a simple condition on the degrees of adjacent vertices, which can be used to obtain similar results.

Again, we experimentally validate that many real-world graphs satisfy our property.

As a result, in some range of power law exponents, we are able to solve the maximum clique problem in polynomial time, although in general power law networks the problem is NP-complete.

In contrast to previously done average-case analyses, we believe that this is the first ``waterproof'' argument that explains why many real-world networks are easier. Moreover, an interesting aspect of this study is the existence of structure oblivious algorithms, i.e., algorithms that run faster on power law networks without explicit knowledge of this fact or explicit knowledge of the parameters of the degree distribution, e.g., algorithms for maximum clique or triangle counting.

The Power of Two Choices with Simple Tabulation

In this paper, we investigate the power of two choices when the hash functions h0 and h1 are implemented with simple tabulation, which is a very efficient hash function evaluated in constant time. Following their analysis of Cuckoo hashing [J.ACM’12], Pătraşcu and Thorup claimed that the expected maximum load with simple tabulation is O(lg lg n). This did not include any high probability guarantee, so the load balancing was not yet to be trusted.

Here we show that with simple tabulation, the maximum load is O(lg lg n) with high probability, giving the first constant time hash function with this guarantee. We also give a concrete example where, unlike with fully random hashing, the maximum load is not bounded by lg lg n + O(1), or even (1 + o(1)) lg lg n with high probability. Finally we show that the expected maximum load is lg lg n + O(1), just like with fully random hashing.

Characterisation of Strongly Stable Matchings

equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching $M$ is a set of vertex-disjoint edges. An edge $(x,y) \in E \setminus M$ is a {\em blocking edge} for $M$ if $x$ is either unmatched or strictly prefers $y$ to its current partner in $M$, and $y$ is either unmatched or strictly prefers $x$ to its current partner in $M$ or is indifferent between them. A matching is {\em strongly stable} if there is no blocking edge with respect to it. We present a characterisation of the set of all strongly stable matchings, thus solving an open problem already stated in the book by Gusfield and Irving \cite{GI}. It has previously been shown that strongly stable matchings form a distributive lattice \cite{Manlove} and although the number of strongly stable matchings can be exponential in the number of vertices, we show that there exists a partial order with $O(m)$ elements representing all strongly stable matchings, where $m$ denotes the number of edges in the graph. We give two algorithms that construct two such representations: one in $O(nm^2)$ time and the other in $O(nm)$ time, where $n$ denotes the number of vertices in the graph. Note that the construction of the second representation has the same time complexity as that of computing a single strongly stable matching.

Sparsity and dimension

Finding Stable Allocations in Polymatroid Intersection

Our framework includes both integer- and real-variable versions. The integer-variable version corresponds to a special case of the discrete-concave function model due to Eguchi, Fujishige, and Tamura (2003), who established the existence of a stable allocation by showing that a simple extension of the deferred acceptance algorithm of Gale and Shapley finds a stable allocation in pseudo-polynomial time. It has been open to develop a polynomial time algorithm even for our special case.

In this paper, we present the first strongly polynomial algorithm for finding a stable allocation in polymatroid intersection. To achieve this, we utilize the augmenting path technique for polymatroid intersection. In each iteration, the algorithm searches for an augmenting path by simulating a chain of proposes and rejects in the deferred acceptance algorithm. The running time of our algorithm is $O(n^3\gamma)$, where $n$ and $\gamma$ respectively denote the cardinality of the ground set and the time for computing the saturation and exchange capacities. This is as fast as the best known algorithm for the polymatroid intersection problem.

An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market

Online Pricing with Impatient Bidders

The impatient bidders problem was introduced by Bansal et al. [TALG’10], where the authors considered the online setting in which additionally the algorithm is given the end of the time interval of each bidder when he arrives. Bansal et al. showed that the competitive ratio for deterministic algorithms is lower bounded by \Omega(\sqrt{log h}) and upper bounded by O(log h), whereas in the randomized setting the gap was between \Omega(\sqrt{log log h / log log log h}) and O(log log h).

We study two versions of the impatient bidders problem, that is in the online setting of Bansal et al., but also in a more restrictive (from the algorithmic perspective) setting where the end of the time interval of each bidder remains unknown until it is hit. We prove that tight bounds for both settings and surprisingly, in both cases the optimum competitive ratios are the same. In particular we prove that the competitive ratio of an optimum deterministic algorithm is \Theta(log h/ log log h), whereas in for randomized algorithms it is \Theta(log log h).

Additionally, we also consider the Veblen bidders problem, where each bidder is only interested in buying the good at a given price level. If its price drops below that level at any point within their time interval, but before they buy it, they lose interest in buying the good. The Veblen bidders problem plays a twofold role in our paper. Not only is it interesting by itself, but it is also the core idea in our proofs for the impatient bidders problem.

Error Amplification for Pairwise Spanner Lower Bounds

A large and growing body of work has considered upper bounds for these objects, but lower bounds have been elusive. The only known lower bound results are (1) Coppersmith \& Elkin (SODA'05) against preservers (zero error), and (2) considerably weaker bounds by Woodruff (FOCS'06) against spanners ($+k$ error).

Our main result is an amplification theorem: we prove that lower bounds against pairwise {\em distance preservers} imply lower bounds against pairwise \emph{spanners}. In other words, to prove lower bounds against {\em any} constant stretch spanners, it is enough to consider only subgraphs that are not allowed to stretch pairwise distances at all!

We apply this theorem to obtain drastically improved bounds. Some of these include:

\begin{itemize}

\item Linear size pairwise spanners with up to $+(2k-1)$ error cannot span $|P|=\omega(n^{(1+k)/(3+k)})$ pairs - this is a large improvement over Woodruff's $|P|=\omega(n^{2-2/k})$.

\item $|H| = \Omega(n^{1 + 1/k})$ edges are required for a $+(2k-1)$ spanner of $|P| = \Omega(n^{1 + 1/k})$ pairs - this is another large improvement over Woodruff's $|P| = \Omega(n^2)$.

\item The first tight bounds for pairwise spanners: for $+2$ error and $P=\Theta(n^{3/2})$ we show that $\Theta(n^{3/2})$ edges are necessary and sufficient.

\end{itemize}

We also show analogous lower bounds against subset spanners (where $P = S \times S$ for some node subset $S$) and $D$-spanners (where $P$ is the set of pairs whose distance exceeds some threshold $D$).

Better Distance Preservers and Additive Spanners

The first part of our paper concerns {\em pairwise distance preservers}, which make the restriction $\beta=0$ (i.e. distances must be preserved {\em exactly}). Our main result here is an upper bound of $|H| = O(n^{2/3}|P|^{2/3} + n|P|^{1/3})$ when $G$ is undirected and unweighted. This improves on existing bounds whenever $|P| = \omega(n^{3/4})$, and it is the first such improvement in the last ten years.

We then devise a new application of distance preservers to graph clustering algorithms, and we apply this algorithm to {\em subset spanners}, which require $P = S \times S$ for some node subset $S$, and {\em (standard) spanners}, which require $P = V \times V$. For both of these objects, our construction generalizes the best known bounds when the error allowance is constant, and we obtain the strongest polynomial error/sparsity tradeoff that has yet been reported (in fact, for subset spanners, ours is the {\em first} nontrivial construction that enjoys improved sparsity from a polynomial error allowance).

We leave open a conjecture that $O(n^{2/3}|P|^{2/3} + n)$ pairwise distance preservers are possible for undirected unweighted graphs. Resolving this conjecture in the affirmative would improve and simplify our upper bounds for all the graph sketches mentioned above.

Hardness of Satisfiable CSPs and Hypergraph Coloring via efficient PCPs with Super-position Complexity

gap to prove the following hardness results:

* It is quasi-NP-hard to satisfy 31/32 + 2^{-(log n)^{1/4 - o(1)}} fraction of the

clauses of a satisfiable Max-5SAT instance on n variables.

* It is quasi-NP-hard to color an n-vertex 2-colorable 6-uniform hypergraph using

2^{(log n)^{1/4 - o(1)}} colors.

The hardness result for Max-5SAT gives the best bound on the ``error'' in the

inapproximability threshold for satisfiable CSPs, improving the previous

2^{-{2^{Omega(sqrt{loglog n})}}} error in the threshold for Max-4SAT proved by

Dinur and Guruswami. Our second result is an improvement over the hardness of

hypergraph coloring for 2-colorable 8-uniform hypergaphs (with the same hardness

factor) obtained by Huang using a new construction of an Outer Verifier with

super-position complexity.

Huang's Outer Verifier substantially simplified and improved upon the first such

construction by Khot and Saket who introduced the notion of super-position

complexity and gave a hardness factor of 2^{(log n)^{1/20 - o(1)}} for

hypergraph coloring. The Outer Verifier of Huang is obtained by (i) a direct

reduction from standard Label Cover to a system of constant width quadratic

equations over F[2] with an approximation as well as a super-position complexity

gap, and (ii) amplifying the approximation gap by Parallel Repetition while

preserving the super-position complexity bound.

We enhance this construction of the Outer Verifier by using a modified version

of Parallel Repetition which yields an additional projection bound, analogous to

the one proved by Håstad for the standard Label Cover. This guarantee allows us

to use more efficient Inner Verifiers to prove our hardness results.

Constructing Almost Minimum Spanning Trees with Constant Average Distortion

While known lower bounds exclude the possibility of the worst case distortion of a tree being small, it was shown in \cite{ABN07} that there exists a spanning tree with constant average distortion. Yet, the weight of such a tree may be significantly larger than that of the MST.

In this paper we show that any weighted undirected graph admits a {\em spanning tree} whose weight is at most $(1+\delta)$ times that of the MST, providing {\em constant average distortion} $O(1/\delta^2)$.

The constant average distortion bound is implied by a stronger property of {\em scaling distortion}, i.e., improved distortion for smaller fractions of the pairs.

The result is achieved by first showing the existence of a low weight {\em spanner} with small {\em prioritized distortion}, an even stronger property allowing to prioritize the nodes whose associated distortions will be improved. We show that prioritized distortion implies scaling distortion via a general transformation, which may be of independent interest.

Canonical Paths for MCMC: from Art to Science

Making use of this general approach, we obtain fully polynomial-time randomized approximation scheme (FPRAS) for counting the number of $b$-matching with $b\leq 7$ and $b$-edge-cover with $b\leq 2$. They are natural generations of matching and edge covers for graphs. No polynomial time approximation was known for these problems.

An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem

which is the problem of assigning indivisible items

to players with budget constraints. In its most general

form, an instance of the MBA problem might include many

different prices for the same item among different

players, and different budget constraints for every

player. So far, the best approximation algorithms we know

for the MBA problem achieve a $3/4$-approximation ratio,

and employ a natural LP relaxation, called the Assignment-LP.

In this paper, we give an algorithm for MBA, and prove that

it achieves a $3/4+c$-approximation ratio, for some constant

$c>0$. This algorithm works by rounding solutions to an

LP called the Configuration-LP, therefore also showing that

the Configuration-LP is strictly stronger than the

Assignment-LP (for which we know that the integrality gap

is $3/4$) for the MBA problem.

An FPTAS for Minimizing Indefinite Quadratic Forms over Integers in Polyhedra

Approximation schemes for machine scheduling with resource (in-)dependent processing times

In both problems, jobs require a certain amount of an additional resource and have to be scheduled on machines minimizing the makespan, while at every point in time a given resource capacity is not exceeded.

In the first variant of the problem the processing times and resource amounts are fixed, while in the second the former depends on the latter.

We present asymptotic fully polynomial approximation schemes (AFPTAS) for the problems:

For any $\eps>0$ a schedule of length at most $(1+\eps)$ times the optimum plus an additive term of $\mathcal{O}(1/\eps^2)$ is provided, and the running time is polynomially bounded in $1/\eps$ and the input length.

Up to now only approximation algorithms with constant approximation ratios were known.

Approximately Efficient Double Auctions with Strong Budget Balance

Two-sided markets, on the other hand, have not received the same attention despite the numerous applications to web advertisement, stock exchange, and frequency spectrum allocation. This work studies double auctions, in which unit-demand buyers and unit-supply sellers act strategically.

An ideal goal in double auction design is to maximize the social welfare of buyers and sellers with individually rational (IR),

incentive compatible (IC)} and strongly budget-balanced (SBB) mechanisms. The first two properties are standard.

SBB requires that the payments charged to the buyers are entirely handed to the sellers. This property is crucial in all the contexts

that do not allow the auctioneer retaining a share of buyers' payments or subsidizing the market.

Unfortunately this goal is known to be unachievable even for the special case of bilateral trade, where there is only one

buyer and one seller. Therefore, in subsequent papers, meaningful trade-offs between these requirements have been investigated.

Our main contribution is the first IR, IC and SBB mechanism that provides an O(1)-approximation to the optimal social welfare. This result holds for any number of buyers and sellers with arbitrary, independent distributions. Moreover, our result continues to hold when there is an additional matroid constraint on the sets of buyers who may get allocated an item. To prove our main result, we devise an extension of sequential posted price mechanisms to two-sided markets. In addition to this, we improve the best-known approximation bounds for the bilateral trade problem.

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model

Dynamic graph streams - We resolve the space complexity of single-pass turnstile streaming

algorithms for approximating matchings by showing that for any $\eps > 0$, $\Theta(n^{2 - 3\eps})$ space is both sufficient and necessary (up to polylogarithmic factors) to compute an $n^{\eps}$-approximate matching; here $n$ denotes the number of vertices in the input graph.

The simultaneous communication model - Our results for dynamic graph streams also resolve the (per-player) simultaneous communication complexity for approximating matchings in the edge partition model. For the vertex partition model, we design new randomized and deterministic protocols for $k$ players to achieve an $\alpha$-approximation. Specifically, for $\alpha \geq \sqrt{k}$, we provide a randomized protocol with total communication of $O(nk/\alpha^2)$ and a deterministic protocol with total communication of $O(nk/\alpha)$. Both these bounds are tight. Moreover, our work generalizes the results established by Dobzinski et.al (STOC 2014) for the special case of $k = n$. Finally, for the case of $\alpha = o(\sqrt{k})$, we establish a new lower bound on the simultaneous communication complexity which is super-linear in $n$.

Blocking optimal k-arborescences

Packing edge-disjoint odd (u,v) trails

The $k$-mismatch problem revisited

We study this problem in both the standard offline setting and also as a streaming problem. In the streaming $k$-mismatch problem the text arrives one symbol at a time and we must give an output before processing any future symbols. Our main results are as follows:

\begin{itemize}

\item Our first result is a deterministic $O(nk^2\log{k}/m+n\polylog{m})$ time \emph{offline} algorithm for $k$-mismatch on a text of length $n$. This is a factor of $k$ improvement over the fastest previous result of this form from SODA 2000~\cite{ALP:2000,ALP:2004}.

\item We then give a randomised and online algorithm which runs in the same time complexity but requires only $O(k^2\polylog{m})$ space in total.

\item Next we give a randomised $(1+\epsilon)$-approximation algorithm for the streaming $k$-mismatch problem which uses $O(k^2\polylog{m}/\epsilon^2)$ space and runs in $O(\polylog{m}/\epsilon^2)$ worst-case time per arriving symbol.

\item Finally we combine our new results to derive a randomised $O(k^2\polylog{m})$ space algorithm for the streaming $k$-mismatch problem which runs in $O(\sqrt{k}\log{k} + \polylog{m})$ worst-case time per arriving symbol. This improves the best previous space complexity for streaming $k$-mismatch from FOCS 2009~\cite{Porat:09} by a factor of $k$. We also improve the time complexity of this previous result by an even greater factor to match the fastest known offline algorithm (up to logarithmic factors).

\end{itemize}

An Algorithmic Hypergraph Regularity Lemma

Szemeredi’s Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rodl gave one such extension to 3-uniform hypergraphs, and Rodl and Skokan extended this result to k-uniform hypergraphs. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rodl and Skokan. Similarly to the graph case, all of these proofs are non-constructive. In this paper, we report on a constructive proof of Gowers’ Hypergraph Regularity Lemma, and discuss an application.

Simpler and tighter analysis of sparse oblivious subspace embeddings

This new method is based on elementary tail bounds combined with matrix trace inequalities (Golden-Thompson or Lieb's theorem), and does not require combinatorics, unlike the Nelson-Nguyen approach. There are also variants of this method that are even simpler, at the cost of worse parameters. Furthermore, the bounds obtained are much tighter than previous ones, matching known lower bounds up to a single log(d) factor in embedding dimension (previous results had more log factors and also had suboptimal tradeoffs with sparsity).

Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth and cliquewidth

understanding of how NP-hard optimization problems become easier on graphs of

bounded treewidth and bounded cliquewidth: for various problems,

matching upper bounds and conditional lower bounds describe exactly how the

running time has to depend on treewidth or cliquewidth. Fomin~et~al.~[SODA 2009, SODA 2010] have shown a significant difference between the two parameters:

assuming the Exponential-Time Hypothesis (ETH), the best possible

algorithms for problems such as MAX CUT and EDGE DOMINATING SET have running time $2^{O(t)}\cdot n^{O(1)}$ when

parameterized by treewidth, but $n^{O(t)}$ when parameterized by

cliquewidth. In this paper, we show that a similar phenomenon occurs

also in the domain of counting problems. Specifically, we prove

that, assuming the Counting Strong Exponential-Time Hypothesis (#SETH), the

problem of counting perfect matchings

- has no $(2-\epsilon)^k\cdot n^{O(1)}$ time algorithm for any $\epsilon>0$ on graphs of treewidth $k$ (but it is known be solvable in time $2^{k}\cdot n^{O(1)}$ if a tree decomposition of width $k$ is given), and

- has no $O(n^{(1-\epsilon)k})$ time algorithm for any $\epsilon>0$ on graphs of cliquewidth $k$ (but it can be solved in time $O(n^{k+1})$ if a $k$-expression is given).

A celebrated result of Fisher, Kasteleyn, and Temperley from the 60s

show that counting perfect matchings in planar graphs is

polynomial-time solvable and Gallucio and Loebl [Electr. J. Comb., 6,

1999] gave a $4^{k}\cdot n^{O(1)}$ time algorithm for graphs of genus

$k$. We show that the dependence on genus $k$ has the be exponential:

assuming $\sharpETH$, there is no $2^{o(k)}\cdot n^{O(1)}$ time

algorithm for the problem on graphs of genus $k$.

Typically, hardness proofs for counting perfect matchings involve a

``mysterious'' step where we reduce an NP-hard decision problem to

(the counting version of) a polynomial-time solvable problem. We

demonstrate that, by using the framework of Holant problems and

observing that every constant-size signature can be realized by a

matchgate, such hardness proofs can be obtained in a clean and

methodological manner, even in the parameterized setting. This opens

the possibility of further hardness results of similar flavor for

other counting problems.

Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems

* Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2^O(n^{1/2} / log^c n) or 2^O(k^{1/4} / log^c k) n^O(1) for some integer c.

* Assuming the non-existence of a subexponential-time approximation scheme for Min

Bisectionon d-regular graphs, for some constant d, none of these problems can be solved in time 2^o(n) or 2^o(sqrt(k)) n^O(1).

For all the aforementioned completion problems, apart from Proper Interval Completion, FPT algorithms with running time of the form 2^O(sqrt(k) log k) n^O(1) are known. Thus, the second result proves that a significant improvement of any of these algorithms would lead to a surprising breakthrough in the design of approximation algorithms for Min Bisection.

To prove our results, we propose a new reduction methodology based on combining the classic approach of starting with a sparse instance of 3-Sat, prepared using the Sparsification Lemma, with the existence of almost linear-size Probabilistically Checkable Proofs (PCPs). Apart from our main results, we also obtain lower bounds excluding the existence of subexponential algorithms for the Optimum Linear Arrangementproblem, as well as improved, yet still not tight, lower bounds for Feedback Arc Set in Tournaments.

Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee

We prove that Vertex Cover is fixed-parameter tractable for this stronger parameter k: We derive an algorithm which solves Vertex Cover in time O*(3^k), and thus push the envelope further on the parameterized tractability of Vertex Cover.

Range Predecessor and Lempel-Ziv Parsing

where the goal is to associate with each phrase of the parsing its {\em most recent} occurrence in the input

string. We solve this problem in $\O(n(1 + (\log\sigma/\sqrt{\log n}))$ time, using the same working space as above. The previous best solution for rightmost parsing uses $\O(n(1+\log\sigma/\log\log n)$ time and $\O(n\log n)$ space. As a bonus, in our solution for rightmost parsing we provide a faster construction method for efficient {\em 2D orthogonal range reporting}, which is of independent interest.

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

Each definition is well-motivated in a variety of applications. All versions of diameter and radius can be solved via solving all-pairs shortest paths (APSP), followed by a fast postprocessing step. However, solving APSP on $n$-node graphs requires $\Omega(n^2)$ time even in sparse graphs.

We study the question: when can diameter and radius in \emph{sparse} graphs be solved in truly subquadratic time, and when is such an algorithm unlikely?

Motivated by lower bounds on computing these measures exactly in truly subquadratic time under plausible assumptions, we search for \emph{approximation} and \emph{fixed parameter subquadratic} algorithms, and alternatively, for reasons why they do not exist.

We find that:

- Most versions of Diameter and Radius can be solved in truly subquadratic time with

\emph{optimal} approximation guarantees, under plausible assumptions.

For example, there is a $2$-approximation algorithm for directed Radius with one-way distances that runs in $\tilde{O}(m\sqrt{n})$ time, while a $(2-\delta)$-approximation algorithm in $O(n^{2-\eps})$ time is considered unlikely.

- On graphs with treewidth $k$, we can solve all versions in $2^{O(k\log{k})}n^{1+o(1)}$ time. We show that these algorithms are near \emph{optimal} since even a $(3/2-\delta)$-approximation algorithm that runs in time $2^{o(k)}n^{2-\eps}$ would refute the plausible assumptions.

A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees

Computing in continuous space with self-assembling polygonal tiles (extended abstract)

A faster subquadratic algorithm for finding outlier correlations

of strongly correlated variables among a collection of $n$ variables

with otherwise weak pairwise correlations.

After normalization, this task amounts to the geometric task where

we are given as input a set of $n$ vectors with unit Euclidean norm

and dimension $d$, and we are asked to find all the outlier pairs of

vectors whose inner product is at least $\rho$ in absolute value, subject

to the promise that all but at most $r$ pairs of vectors have inner product

at most $\tau$ in absolute value for some constants $0\leq \tau <\rho\leq 1$.

In particular this promise implies that there are at most $r$ outlier pairs.

A natural objective for algorithm design in this setting is to

seek designs whose running time scales {\em subquadratically} in

the number of variables $n$ and avoids substantial dependence

on the outlier parameter $\rho$ and the background parameter $\tau$.

In a recent breakthrough result, Gregory Valiant [FOCS 2012; J.\,ACM 2015]

showed that for

{\em binary inputs} (that is, $\{-1,1\}$-valued data normalized to

unit Euclidean length) there is a randomized algorithm that finds the

at-least-$\rho$-correlated pairs among an at-most-$\tau$-correlated

background in time

\[

\tilde O(n^{(5-\omega)/(4-\omega)+\omega(\log\rho)/(\log\tau)}+rdn^{1/(4-\omega)})\,,

\]

where $2\leq\omega<2.38$ is the exponent of square matrix

multiplication. In particular, for small values of $r$

the running time is subquadratic

in the number of variables $n$ assuming $\tau$ is sufficiently small

compared with $\rho$, and furthermore, unlike earlier approaches such as

{\em locality-sensitive hashing} [Indyk and Motwani, STOC 1998],

when $\tau\rightarrow 0$ the exponent of the running time converges

to a subquadratic value $(5-\omega)/(4-\omega)$ that is

{\em independent of the outlier strength $\rho$} for any constant $\rho$.

The key insight in Valiant's algorithm is to first

(i) {\em compress} the input by randomly expanding and aggregating the input

vectors and then (ii) {\em detect} the correlations in the compressed data

with fast matrix multiplication.

We improve on Valiant's algorithm with a faster compression subroutine

that enables a better tradeoff between parts (i) and (ii) of the

framework, as controlled by a parameter $0<\gamma<1$.

We present a randomized algorithm that for binary inputs

runs in time

\[

\tilde O(n^{\max\,\{1-\gamma+M(\Delta\gamma,\gamma),\,M(1-\gamma,2\Delta\gamma)\}}+rdn^{2\gamma})\,,

\]

where $M(\mu,\nu)$ is the

exponent to multiply an $n^\mu\times n^\nu$ matrix with an $n^\nu\times n^\mu$

matrix and $\Delta=1/(1-(\log\rho)/(\log\tau))$.

With $\gamma=1/(2\Delta+1)$ our algorithm runs in time

$\tilde O(n^{2\omega/(3-(\log\rho)/(\log\tau))}+rdn^{1/(\Delta+1/2)})$

and with $\gamma=\alpha/(2\Delta+\alpha)$ in time

$\tilde O(n^{4/(2+\alpha(1-(\log\rho)/(\log\tau)))}+rdn^{\alpha/(\Delta+\alpha/2)})$,

where $0.3<\alpha\leq 1$ is the threshold exponent for

rectangular matrix multiplication. For example, the last bound

implies that asymptotically it is possible to detect extremely weak

outliers with, say, $\rho=2^{-100}$ and $\tau=2^{-101}$,

in time $\tilde O(n^{1.998}+rdn^{0.003})$.

Conversely, in the strong outlier setting with $\tau\rightarrow 0$ and

any constant $\rho$, we obtain the exponent

$2\omega/3$ for the running time, improving Valiant's exponent

$(5-\omega)/(4-\omega)$ across the range $2\leq\omega<2.38$.

(The notation $\tilde O(\cdot)$ hides polylogarithmic factors in $n$

and $d$ whose degree may depend on $\rho$ and $\tau$.)

Robust Positioning Patterns

In this context, we give the first explicit constructions of sequences and matrices with high rate and constant relative distance. Accompanying these efficient constructions, we also give efficient decoding algorithms, which can determine the position of the window given its contents, even if a constant fraction of the contents have been corrupted.

Sampling on lattices with free boundary conditions using randomized extensions

We show that randomly extending the boundary of a configuration with free boundaries by a few layers, choosing among only a constant number of allowable extensions, we can generalize the arguments used in the fixed boundary setting to infer bounds on the mixing time for free boundaries. We demonstrate this technique of using randomized extensions for 3-colorings on rectangular regions of $Z^2$ and lozenge tilings of triangular regions on the triangular lattice with free boundaries, building on arguments for the fixed boundary cases due to Luby, Randall and Sinclair.

Dynamic DFS Tree in Undirected Graphs: breaking the O(m) barrier

We present the following results for this problem.

1- Fault tolerant DFS tree:

There exists a data structure of size O~(m) (where O~() hides the poly-logarithmic factors.) such that given any k updates, a DFS tree for the resulting graph can be reported in O~(nk) worst case time. When the k updates are deletions only, this directly implies an O~(nk) time fault tolerant algorithm for a DFS tree.

2- Fully dynamic DFS tree:

There exists a fully dynamic algorithm for maintaining a DFS tree that takes worst case O~(\sqrt{mn}) time per update for any arbitrary online sequence of updates.

3- Incremental DFS tree:

Given any arbitrary online sequence of edge insertions, we can maintain a DFS tree in O~(n) worst case time per edge insertion.

These results are the first o(m) worst case time results for maintaining a DFS tree in a dynamic environment. Moreover, our fully dynamic algorithm provides, in a seamless manner, the first non-trivial deterministic algorithm with O(1) query time and o(m) worst case update time for the dynamic subgraph connectivity, bi-connectivity, and 2-edge connectivity.

Interpolating Between Truthful and Non-Truthful Mechanisms for Combinatorial Auctions

The goal of this paper is to understand the benefits of interpolation mechanisms versus truthful mechanisms or traditional protocols, and develop the necessary tools to formally study them. Interestingly, we exhibit settings where interpolation mechanisms greatly outperform the optimal traditional and truthful protocols. Yet, we also exhibit settings where interpolation mechanisms are (provably) no better than truthful ones. Finally, we apply our new machinery to prove that the recent single-bid mechanism of Devanur et. al.~\cite{DevanurMSW15} (the only pre-existing interpolation mechanism in the literature) achieves the optimal price of anarchy among a wide class of protocols, a claim that simply can't be addressed by appealing just to machinery from communication complexity or the study of truthful mechanisms.

Designing Networks with Good Equilibria under Uncertainty

with good equilibria under uncertainty. The underlying game is a

multicast game in a rooted undirected graph with nonnegative edge costs.

A set of k terminal vertices or players need to establish connectivity

with the root. The social optimum is the Minimum Steiner Tree.

We are interested in situations where the designer has incomplete

information about the input. We propose two different models, the

adversarial and the stochastic. In both models, the designer has

prior knowledge of the underlying metric but the requested subset

of the players is not known and is activated either in an adversarial

manner (adversarial model) or is drawn from a known probability

distribution (stochastic model).

In the adversarial model, the goal of the designer is to choose

a single, universal cost-sharing protocol that has low Price

of Anarchy (PoA) for all possible requested subsets of players.

The main question we address is: to what extent can prior knowledge

of the underlying metric help in the design?

We first demonstrate that there exist classes of graphs where

knowledge of the underlying metric can dramatically improve the

performance of good network cost-sharing design. For outerplanar

graph metrics, we provide a universal cost-sharing protocol with

constant PoA, in contrast to protocols that, by ignoring the graph

metric, cannot achieve PoA better than Omega(log k). Then, in our

main technical result, we show that there exist graph metrics, for

which knowing the underlying metric does not help and any universal

protocol has PoA of Omega(log k), which is tight. We attack this

problem by developing new techniques that employ powerful tools

from extremal combinatorics, and more specifically Ramsey Theory

in high dimensional hypercubes.

Then we switch to the stochastic model, where each player is

independently activated according to some probability distribution

that is known to the designer. We show that there exists a randomized

ordered protocol that achieves constant PoA. By using standard

derandomization techniques, we produce a deterministic ordered

protocol that achieves constant PoA. We remark, that the first result

holds also for the black-box model, where the probabilities are not

known to the designer, but is allowed to draw independent

(polynomially many) samples.

On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs

For example, on a planer road network, we can support fast queries and dynamic traffic updates as long as the shortest path from any source to any target (including using arbitrary detours) is between, say, 80 and 3 miles-per-hour.

As a warm-up we also prove that graphs of bounded treewidth have exact distance oracles in the dynamic edge model.

To the best of our knowledge, this is the first dynamic distance oracle for a non-trivial family of dynamic changes to planar graphs with worst case costs of $o(n^{1/2})$ both for query and for update operations.

Subtree Isomorphism Revisited

The problem is of fundamental importance and has been studied since the 1960s.

For some variants, e.g., \emph{ordered trees}, near-linear time algorithms are known, but for the general case truly subquadratic algorithms remain elusive.

Our first result is a reduction from the Orthogonal Vectors problem to Subtree Isomorphism, showing that a truly subquadratic algorithm for the latter refutes the Strong Exponential Time Hypothesis (SETH).

In light of this conditional lower bound, we focus on natural special cases for which no truly subquadratic algorithms are known. We classify these cases against the quadratic barrier, showing in particular that:

\begin{itemize}

\item Even for binary, rooted trees, a truly subquadratic algorithm refutes SETH.

\item Even for rooted trees of depth $O(\log\log{n})$, where $n$ is the total number of vertices, a truly subquadratic algorithm refutes SETH.

\item For every constant $d$, there is a constant $\eps_d>0$ and a randomized, truly subquadratic algorithm for degree-$d$ rooted trees of depth at most $(1+ \eps_d) \log_{d}{n}$.

In particular, there is an $O(\min\{ 2.85^h ,n^2 \})$ algorithm for binary trees of depth $h$.

\end{itemize}

Our reductions utilize new ``tree gadgets" that are likely useful for future SETH-based lower bounds for problems on trees. Our upper bounds apply a folklore result from randomized decision tree complexity.