Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to \emph{negative correlation} properties. However, what if an application naturally calls for dependent rounding on the one hand, and desires \emph{positive} correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding, but also have nearly best-possible behavior -- near-independence, which generalizes positive correlation -- on ``small" subsets of the variables. The recent breakthrough of Li \& Svensson for the classical $k$-median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly. We improve upon Li-Svensson's approximation ratio for $k$-median from $2.732 + \epsilon$ to $2.611 + \epsilon$ by developing an algorithm that improves upon various aspects of their work. Our dependent-rounding approach helps us improve the dependence of the runtime on the parameter $\epsilon$ from Li-Svensson's $N^{O(1/\epsilon^2)}$ to $N^{O((1/\epsilon) \log(1/\epsilon))}$.

We present an algorithm for surface reconstruction from a point cloud. It runs in O(n log n) time, where n is the number of sample points, and this is optimal in the pointer machine model. The only existing O(n log n)-time algorithm is due to Funke and Ramos, and it uses some sophisticated data structures. The key task in their algorithm is to ex- tract a locally uniform subsample from the input points. Our extraction of locally uniform subsample is based on a variant of the standard octree and it is much simpler. We built a prototype that runs an implementation of our algorithm to extract a locally uniform sub- sample, invokes Cocone to reconstruct a surface from the subsample, and adds back the samples points absent from the subsample via edge flips. In our experiments with some non-uniform samples, the subsample extraction step is fast and effective, and the prototype gives a 51% to 68% speedup from using Cocone alone. The prototype also runs faster on locally uniform samples.

We consider the problem of, given an array $A[1,n]$ of elements with a total order, building a data structure that solves two queries: $(a)$ selection queries receive a range $[i,j]$ and an integer $k$ and return the position of the $k$th largest element in $A[i,j]$; $(b)$ top-$k$ queries receive $[i,j]$ and $k$ and return the positions of the $k$ largest elements in $A[i,j]$. These problems can be solved in optimal time, $O(1+\log k/\log\log n)$ and $O(k)$ respectively, using linear-space data structures. We present the first study of {\em encoding} data structures for this problem, which do not access $A$ at query time. These save storage space in applications where the values of $A$ themselves are not of interest. We first show that any encoding answering such queries requires $n\lg k - O(n+k \lg k)$ bits of space. Then we design encodings using $O(n\log k)$ bits, that is, asymptotically optimal up to constant factors, that answer selection and top-$k$ queries in optimal time.

Even though local search heuristics are the method of choice in practice for many well-studied optimization problems, most of them behave poorly in the worst case. This is in particular the case for the Maximum-Cut Problem, for which local search can take an exponential number of steps to terminate and the problem of computing a local optimum is PLS-complete. To narrow the gap between theory and practice, we study local search for the Maximum-Cut Problem in the framework of smoothed analysis in which inputs are subject to a small amount of random noise. We show that the smoothed number of iterations is quasi-polynomial, i.e., it is bounded from above by a polynomial in n^log(n) and ¦ where n denotes the number of nodes and ¦ denotes the perturbation parameter. This shows that worst-case instances are fragile and it is a first step in explaining why they are rarely observed in practice.

Moser & Tardos have developed a powerful algorithmic approach (henceforth ``MT") to the Lovasz Local Lemma (LLL); the basic operation in that algorithm is a search for ``bad" events in a current configuration. We examine the variable distribution during intermediate stages of MT. We show that these configurations have a more or less ``random'' form, building further on the ``MT-distribution" concept of Haeupler et al. One important consequence of this that bad events can be found relatively quickly, improving upon MT across the complexity spectrum: it makes some polynomial-time algorithms sub-linear (e.g., for Latin transversals, which are of basic combinatorial interest), gives lower-degree polynomial run-times in some settings, transforms certain super-polynomial-time algorithms into polynomial-time ones, and leads to Las Vegas algorithms for some coloring problems for which only Monte Carlo algorithms were known. 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 that this MT variant can run faster than the original MT algorithm, 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 enumerative applications, showing that many problems have many more solutions than known before by proving that the MT-distribution has ``large" Renyi entropy and hence that its support-size is large.

Leader election is a fundamental problem in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader. When the nodes are anonymous, leader election is formulated as follows: every node must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this paper, we study deterministic leader election in *n*-node anonymous trees of diameter *diam* d *D*.
We establish tradeoffs between the allocated time Ä and the amount of information that must be given *a priori* to the nodes to enable leader election in time Ä in all trees for which leader election in this time is at all possible. While leader election in time *diam* can be performed without any information, for time *diam*-1 we give a tight bound of ¸(log *D*). For time *diam*-2 we give a tight bound of ¸(log *D*) for even values of *diam*, and a tight bound of ¸(log *n*) for odd values of *diam*. Moving to shorter time, in the interval [²·*diam*, *diam*-3] for constant ² >1/2, we prove an upper bound of O((*n*log *n*)/*D*) and a lower bound of &(*n/D*), the latter being valid whenever *diam* is odd or when the time is at most *diam*-4. Finally, for time ±·*diam* for any constant ± < 1/2 (except for the case of very small diameters), we again give a tight bound, this time ¸(*n*).

This paper addresses the general limit of the standard tractability
results for Constraint Satisfaction Problems (CSP) and counting-CSP, that they only apply to instances
where all constraints belong to a single tractable language. 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. Our main
result is an algorithm that, given a CSP instance with n
variables, finds in time f(k)n^{O(1)} a strong backdoor into
a scattered class (associated with a list of finite conservative
constraint languages) of size k or correctly decides that there
is no such 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.

Several simple, classical, little-known algorithms in the statistical literature for generating random permutations by coin-tossing are examined, analyzed and implemented. These algorithms are either asymptotically optimal or close to being so in terms of the expected number of times the random bits are generated. In addition to asymptotic approximations to the expected complexity, we also clarify the corresponding variances, as well as the asymptotic distributions. A brief comparative discussion with numerical computations in a multicore system is also given.

We present fast algorithms for sketching valuation functions. Let $N$ ($|N|=n$) be some ground set and $v:2^N\rightarrow \mathbb R$ be a function. We say that $\tilde v:2^N\rightarrow \mathbb R$ is an \emph{$\alpha$-sketch} of $v$ if for every set $S$ we have that $\frac {v(S)} {\alpha} \leq \tilde v(S) \leq v(S)$ and $\tilde v$ can be described in $poly(n)$ bits. If $v$ is submodular then a $\tilde O(\sqrt n)$-sketch can be constructed using polynomially many value queries [Goemans et al., SODA'09] (this is essentially the best possible, as Balcan and Harvey [STOC'11] show that no submodular function admit an $n^{\frac 1 3 - \epsilon}$-sketch). Based on their work, Balcan et al. [COLT'12] and Badanidiyuru et al [SODA'12] construct a $\tilde O(\sqrt n)$-sketch for subadditive functions with polynomially many demand queries. All previous sketches use complicated geometric arguments: the first step proves the existence of a good sketch by finding an ellipsoid that ``approximates'' $v$ well (by applying John's theorem to ensure the existence of an ellipsoid that is ``close'' to $v$). The second step shows how to efficiently find this ellipsoid, by repeatedly solving a certain convex program to obtain better approximations of John's ellipsoid. This paper gives a significantly simpler, non-geometric proof for the existence of good sketches, and obtains much faster algorithms that match the previous bounds. Specifically, we construct a $\tilde O(\sqrt n)$-sketch of a submodular function with $\tilde O(n^\frac{3}{2})$ value queries, and an $\tilde O(\sqrt n)$-sketch of a subadditive function with $O(n)$ demand and value queries.

We study algorithms that, given query-access to an input function, approximately determine whether the function satisfies a desired property. More specifically, our algorithms accept if the function has the property and reject with high probability if the function is far from having the property. The distance to having the property is measured with respect to a known or an unknown distribution over the domain of function. In this work, we focus on functions over domains of the form {1,2,..,n}^d (that is, d-dimensional hypergrids). We look at a general class of properties of such functions, called bounded derivative properties (BDP), which includes monotonicity and the Lipschitz property. We give an optimal tester for BDPs for the case when the distance to the property is measured with respect to a product distribution, that is, a distribution where each coordinate is chosen independently. Our main tool here is a novel dimension reduction which reduces testing properties of functions over {1,2,..,n}^d to testing functions over {1,2,..,n}. This dimension reduction is optimal up to a constant factor. For BDPs of functions over {1,2,...,n}, we design an optimal tester for the case when the distribution is known. Our tester is based on Knuth's construction of binary search trees over {1,2,..,n} with minimum expected depth. As a special case, we obtain an optimal monotonicity tester for {1,2,..,n}, thus improving the tester given by Ailon and Chazelle (Information and Computation, 2006). Our work resolves two open problems given in their work.

For every fixed constant $\alpha > 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \R^N$ in time $k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tx \in \R^N$ satisfying $\|\tx - \hat{x}\|_1 = O( \|\hat{x} - H_k(\hat{x})\|_1$ ), where $\hat{x}$ is the transform of $x$ and $H_k(\hat{x})$ is its best $k$-sparse approximation. Our algorithm is fully deterministic and only uses non-adaptive queries to $x$. 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 et al, 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 et al (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$). 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)$.

The F-Minor-Free Deletion problem asks, for a fixed set F and an input consisting of a graph G and integer k, whether k vertices can be removed from G such that the resulting graph does not contain any member of F as a minor. Fomin et al. (FOCS 2012) showed that the special case when F contains at least one planar graph has a kernel of size f(F)·k^{g(F)} for some functions f and g. They left open whether this Planar F-Minor-Free Deletion problem has kernels whose size is uniformly polynomial, of the form f(F)·k^{c} for some universal constant c. We prove that some Planar F-Minor-Free Deletion problems do not have uniformly polynomial kernels (unless
NP coNP/poly), not even when parameterized by the vertex cover number. On the positive side, we consider the problem of determining whether k vertices can be removed to obtain a graph of treedepth at most ·. We prove that this problem admits uniformly polynomial kernels with O(k^{6}) vertices for every fixed ·.