Abstract: One of the most noted construction methods of $3$-vertex-connected graphs is due to Tutte and based on the following fact: Every $3$-vertex-connected graph $G$ on more than $4$ vertices contains a contractible edge, i.\,e., an edge whose contraction generates a $3$-connected graph. This implies the existence of a sequence of edge contractions from $G$ to $K_4$ such that every intermediate graph is $3$-vertex-connected. A theorem of Barnette and Gr\"unbaum yields a similar sequence using removals on edges instead of contractions.

We show how to compute both sequences in optimal time, improving the previously best known running times of $O(|V|^2)$ to $O(|E|)$. Based on this result, we give a linear-time test of $3$-connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in the last years. The $3$-connectivity test is conceptually different from well-known linear-time tests on $3$-connectivity; it uses a certificate that is easy to verify in time $O(|E|)$. We show how to extend the results to an optimal certifying test of $3$-edge-connectivity.

Abstract: The quantum query complexity of Boolean matrix multiplication is typically studied as a function of the matrix dimension, $n$, as well as the number of 1s in the output, L. We prove an upper bound of ~O(n sqrt{L}) for all values of L. This is an improvement over previous algorithms for all values of L. On the other hand, we show that for any eps < 1 and any L <= eps n^2, there is an Omega(n sqrt{L}) lower bound for this problem, showing that our algorithm is essentially tight.

We first reduce Boolean matrix multiplication to several instances of graph collision. We then provide an algorithm that takes advantage of the fact that the underlying graph in all of our instances is very dense to find all graph collisions efficiently.

Abstract: We study the complexity of computing the sign of the Tutte polynomial of a graph. As there are only three possible outcomes (positive, negative, and zero), this seems at first sight more like a decision problem than a counting problem. Surprisingly, however, there are large regions of the parameter space for which computing the sign of the Tutte polynomial is actually #P-hard. As a trivial consequence, approximating the polynomial is also #P-hard in this case. Thus, approximately evaluating the Tutte polynomial in these regions is as hard as exactly counting the satisfying assignments to a CNF Boolean formula. For most other points in the parameter space, we show that computing the sign of the polynomial is in FP, whereas approximating the polynomial can be done in polynomial time with an NP oracle. As a special case, we completely resolve the complexity of computing the sign of the chromatic polynomial --- this is easily computable at q=2 and when q is at most 32/27, and is NP-hard to compute for all other values of the parameter q.

Abstract: We present a new data structure called the \emph{Compressed Random Access Memory}~(CRAM) that can store a dynamic string~$T$ of characters, e.g., representing the memory of a computer, in compressed form while achieving asymptotically almost-optimal bounds (in terms of empirical entropy) on the compression ratio. It allows short substrings of~$T$ to be decompressed and retrieved efficiently and, significantly, characters at arbitrary positions of~$T$ to be modified quickly during execution \emph{without decompressing the entire string}. This can be regarded as a new type of data compression that can update a compressed file directly. Moreover, at the cost of slightly increasing the time spent per operation, the CRAM can be extended to also support insertions and deletions. Our key observation that the empirical entropy of a string does not change much after a small change to the string, as well as our simple yet efficient method for maintaining an array of variable-length blocks under length modifications, may be useful for many other applications as well.

Abstract: In this paper, we generalize Spencer's hyperbolic cosine algorithm to the matrix-valued setting. We apply the proposed algorithm to several problems by analyzing its computational efficiency under two special cases of matrices; one in which the matrices have a group structure and the other in which they have rank-one. As an application of the former case, we present a deterministic algorithm that, given the multiplication table of a finite group of size n, it constructs an Alon-Roichman expanding Cayley graph of logarithmic degree in near-optimal O(n^2\log^3 n) time. For the latter case, we present a fast deterministic algorithm for spectral sparsification of positive semi-definite matrices, which implies an improved deterministic algorithm for spectral graph sparsification of dense graphs. In addition, we give an elementary connection between spectral sparsification of positive semi-definite matrices and element-wise matrix sparsification. As a consequence, we obtain improved element-wise sparsification algorithms for diagonally dominant-like matrices.

Abstract: Consider a \emph{sum-product} normed space, i.e.\ a space of the form $Y=\ell_1^n \otimes X$, where $X$ is another normed space. Each element in $Y$ consists of a length-$n$ vector of elements in $X$, and the norm of an element in $Y$ is the sum of the norms of its coordinates. In this paper we show a constant-distortion embedding from the normed space $\ell_1^n \otimes X$ into a lower-dimensional normed space $\ell_1^{n'} \otimes X$, where $n' \ll n$ is some value that depends on the properties of the normed space $X$ (namely, on its Rademacher dimension). In particular, composing this embedding with another well-known embedding of Indyk \cite{Indyk07}, we get an $O(1/\eps)$-distortion embedding from the earth-mover metric $\EMD_{\Delta}$ on the grid $[\Delta]^2$ to $\ell_1^{\Delta^{O(\eps)}} \otimes \EEMD_{\Delta^{\eps}}$ (where $\EEMD$ is a norm that generalizes earth-mover distance). This embedding is stronger (and simpler) than the sketching algorithm of Andoni et al~\cite{ABIW09}, which maps $\EMD_{\Delta}$ with $O(1/\eps)$ approximation into sketches of size $\Delta^{O(\eps)}$.

Abstract: We study the Submodular Ranking problem [Azar-Gamzu11] in the presence of metric costs. The input to Minimum Latency Submodular Cover (MLSC) problem consists of a metric $(V,d)$ with source $r \in V$ and $m$ monotone submodular functions $f_1, f_2, ..., f_m: 2^V \rightarrow [0,1]$. The goal is to find a path originating at $r$ that minimizes the total cover time of all functions; the cover time of function $f_i$ is the smallest value $t$ such that $f_i$ has value one on the vertices visited within distance $t$ along the path. This generalizes many previously studied problems, such as Submodular Ranking [Azar-Gamzu11] when the metric is uniform, and Group Steiner Tree [Garg-Konjevod-Ravi00] when $m=1$ and $f_1$ is a coverage function. We give a polynomial time $O(\log \frac{1}{\eps} \cdot \log^{2+\delta} |V|)$-approximation algorithm for MLSC, where $\epsilon>0$ is the smallest non-zero marginal increase of any $\{f_i\}_{i=1}^m$ and $\delta>0$ is any constant. This result is enabled by a simpler analysis of the submodular ranking algorithm from [Azar-Gamzu11].

We also consider the stochastic Submodular Ranking problem where elements $V$ have random instantiations, and obtain an adaptive algorithm with an $O(\log 1/ \eps)$ approximation ratio, which is best possible. This result also generalizes several previously studied stochastic problems, e.g. Adaptive Set Cover [Goemans-Vondrak06] and Shared Filter Evaluation [Munagala-Srivastava-Widom07],[Liu-Parthasarathy-Ranganathan-Yang08].

Abstract: We describe a method for upper bounding the quantum query complexity of certain boolean formula evaluation problems, using fundamental theorems about the general adversary bound. This nonconstructive method gives an upper bound on query complexity without producing an algorithm. For example, we describe an oracle problem which we prove (non-constructively) can be solved in $O(1)$ queries, where the previous best quantum algorithm uses a polynomial number of queries. We then give an explicit $O(1)$ query algorithm based on span programs, and show that for a special case of this problem, there exists a $O(1)$ query algorithm that uses the quantum Haar transform. This special case is a potentially interesting problem in its own right, which we call the \textsc{Haar Problem}.

Abstract: We consider the problem of testing isomorphism of groups of order $n$ given by Cayley tables. The trivial $n^{\log n}$ bound on the time complexity for the general case has not been improved upon over the past four decades. We demonstrate that the obstacle to efficient algorithms is the presence of abelian normal subgroups; we show this by giving a polynomial-time isomorphism test for \emph{semisimple groups}, defined as groups without nontrivial abelian normal subgroups. This concludes a project started by the authors and J. A. Grochow (SODA 2011). That paper gave an (easy) $n^{\log\log n}$ algorithm for this class, gave nontrivial polynomial-time algorithms assuming boundedness of certain parameters, and identified the problem of permutational isomorphism of permutation groups as a critical bottleneck. The key new ingredients in this paper are: (a) an algorithm to test permutational isomorphism of permutation groups in time polynomial in the order and simply exponential in the degree; (b) the introduction of the ``twisted code equivalence problem,'' a generalization of the classical code equivalence problem by admitting a group action on the alphabet; (c) an adaptation of the code equivalence algorithm from the authors' SODA'11 paper to twisted code equivalence with improved data management that (critically for this paper) improves the authors' SODA'11 bound even in the classical case; (d) a reduction of semisimple group isomorphism to permutational isomorphism of transitive permutation groups under the given time limits via ``twisted code equivalence.''
The twisted code equivalence problem and the problem of permutational isomorphism of permutation groups are of interest in their own right.

Abstract: We consider the following stochastic optimization problem first introduced by Chen et al. We are given a vertex set of a random graph where each possible edge is present with probability p_e. We do not know which edges are actually present unless we scan/probe an edge. However whenever we probe an edge and find it to be present, we are constrained to picking the edge and both its end points are deleted from the graph. We wish to find the maximum matching in this model. We compare our results against the optimal omniscient algorithm that knows the edges of the graph and present a 0.573 factor algorithm using a novel sampling technique. We also prove that no algorithm can attain a factor better than 0.896 in this model.

Abstract: We consider the classic clique (or, equivalently, the independent set) problem in two settings. In the streaming model, edges are given one by one in an adversarial order and the algorithm aims to output a good approximation under space restrictions. In the communication complexity setting, two players each hold a graph on $n$ vertices, and they wish to use limited amount of communication to distinguish between the cases when the union of the two graphs has a low or a high clique number. The settings are related in that the communication complexity gives a lower bound on the space complexity of streaming algorithms.
We give several results that illustrate different tradeoffs between clique separability and the required communication/space complexity under randomization. The main result is a lower bound of $\Omega(\frac{n^2}{r^2\log^2{n}})$-space for any $r$-approximate randomized streaming algorithm for maximum clique. A simple random sampling argument shows that this is tight up to a logarithmic factor. For the case when $r=o(\log{n})$, we present another lower bound of $\Omega(\frac{n^2}{r^4})$. In particular, it implies that any constant approximation randomized streaming algorithm requires $\Omega(n^2)$ space, even if the algorithm runs in exponential time. Finally, we give a third lower bound that holds for the extremal case of $s-1$ vs. $\ramsey(s)-1$, where $\ramsey(s)$ is the $s$-th Ramsey number. This is the extremal setting of clique numbers that can be separated. The proofs involve some novel combinatorial structures and sophisticated combinatorial constructions.

Abstract: The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. In this paper we show that, unless NP is contained in coNP/poly and the polynomial hierarchy collapses up to its third level, the following parameterized problems do not admit a polynomial time preprocessing algorithm that reduces the size of an instance to polynomial in the parameter:
– EDGE CLIQUE COVER, parameterized by the number of cliques,
– DIRECTED EDGE/VERTEX MULTIWAY CUT, parameterized by the size of the cutset, even in the case of two terminals,
– EDGE/VERTEX MULTICUT, parameterized by the size of the cutset, and
– k-WAY CUT, parameterized by the size of the cutset.
The existence of a polynomial kernelization for EDGE CLIQUE COVER was a seasoned veteran in open problem sessions. Furthermore, our results complement very recent developments in designing parameterized algorithms for cut problems by Marx and Razgon [STOC’11], Bousquet et al. [STOC’11], Kawarabayashi and Thorup [FOCS’11] and Chitnis et al. [SODA’12].

Abstract: We introduce the following notion of compressing an undirected graph $G$ with edge-lengths and terminal vertices $R\subseteq V(G)$. A \emph{distance-preserving minor} is a minor $G'$ (of $G$) with possibly different edge-lengths, such that $R\subseteq V(G')$ and the shortest-path distance between every pair of terminals is exactly the same in $G$ and in $G'$. What is the smallest $f^*(k)$ such that every graph $G$ with $k=|R|$ terminals admits a distance-preserving minor $G'$ with at most $f^*(k)$ vertices?
Simple analysis shows that $f^*(k)\le O(k^4)$. Our main result proves that $f^*(k)\ge \Omega(k^2)$, significantly improving over the trivial $f^*(k)\ge k$. Our lower bound holds even for planar graphs $G$, in contrast to graphs $G$ of constant treewidth, for which we prove that $O(k)$ vertices suffice.

Abstract: We consider packing LP's with m rows where all constraint coefficients are normalized to be in the unit interval. The n columns arrive in random order and the goal is to set the corresponding decision variables irrevocably when they arrive so as to obtain a feasible solution maximizing the expected reward. Previous (1-eps)-competitive algorithms require the right-hand side of the LP to be \Omega((m/eps^2) log (n/eps)), a bound that worsens with the number of columns and rows. However, the dependence on the number of columns is not required in the single-row case and known lower bounds for the general case are also independent of n.

Our goal is to understand whether the dependence on n is required in the multi-row case, making it fundamentally harder than the single-row version. We refute this by exhibiting an algorithm which is (1-eps)-competitive as long as the right-hand sides are \Omega((m^2/eps^2) log (m/eps)). Our techniques refine previous PAC-learning based approaches which interpret the online decisions as linear classifications of the columns based on sampled dual prices. The key ingredient of our improvement comes from a non-standard covering argument together with the realization that only when the columns of the LP belong to few 1-d subspaces we can obtain small such covers; bounding the size of the cover constructed also relies on the geometry of linear classifiers. General packing LP's are handled by perturbing the input columns, which can be seen as making the learning problem more robust.

Abstract: We prove that finding a k-edge induced subgraph is fixed-parameter tractable, thereby answering an open problem of Leizhen Cai. Our algorithm is based on several combinatorial observations, Gauss' famous Eureka theorem [Andrews, 86], and a generalization of the well-known fpt-algorithm for the model-checking problem for first-order logic on graphs with locally bounded tree-width due to Frick and Grohe [Frick and Grohe, 01]. On the other hand, we show that two natural counting versions of the problem are hard. Hence, the k-edge induced subgraph problem is one of the rare known examples in parameterized complexity that are easy for decision while hard for counting.

Abstract: We study streaming algorithms for the interval selection problem: finding a maximum cardinality subset of disjoint intervals on the line. A deterministic $2$-approximation streaming algorithm for this problem is developed, together with an algorithm for the special case of proper intervals, achieving improved approximation ratio of $3/2$. We complement these upper bounds by proving that they are essentially best possible in the streaming setting: it is shown that an approximation ratio of $2 - \epsilon$ (or $3 / 2 - \epsilon$ for proper intervals) cannot be achieved unless the space is linear in the input size. In passing, we also answer an open question of Adler and Azar \cite{AdlerAzar03} regarding the space complexity of constant-competitive randomized preemptive online algorithms for the same problem.

Abstract: We study \emph{fault-tolerant} spanners in doubling metrics. A subgraph $H$ for a metric space $X$ is called a $k$-vertex-fault-tolerant $t$-spanner ($(k,t)$-VFTS or simply $k$-VFTS), if for any subset $S \subseteq X$ with $|S| \leq k$, it holds that $d_{H \setminus S}(x, y) \leq t \cdot d(x, y)$, for any pair of $x, y \in X \setminus S$.

For any doubling metric, we give a basic construction of $k$-VFTS with stretch arbitrarily close to 1 that has optimal $O(kn)$ edges. In addition, we also consider bounded hop-diameter, which is studied in the context of fault-tolerance for the first time even for Euclidean spanners. We provide a construction of $k$-VFTS with bounded hop-diameter: for $m \geq 2n$, we can reduce the hop-diameter of the above $k$-VFTS to $O(\alpha(m, n))$ by adding $O(km)$ edges, where $\alpha$ is a functional inverse of the Ackermann's function.

Finally, we construct a fault-tolerant single-sink spanner with bounded maximum degree, and use it to reduce the maximum degree of our basic $k$-VFTS. As a result, we get a $k$-VFTS with $O(k^2 n)$ edges and maximum degree $O(k^2)$.

Abstract: The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al.~\cite{AFS08} proved that a certain configuration LP can be used to estimate the optimal value within a factor $1/(4+\epsilon)$, for any $\epsilon>0$, but at the same time it is not known how to efficiently find a solution with a comparable performance guarantee.
A natural question that arises from their work is if the difference between these guarantees is inherent or because of a lack of suitable techniques. We address this problem by giving a quasi-polynomial approximation algorithm with the mentioned performance guarantee. More specifically, we modify the local search of~\cite{AFS08} and provide a novel analysis that lets us significantly improve the bound on its running time: from $2^{O(n)}$ to $n^{O(\log n)}$. Our techniques also have the interesting property that although we use the rather complex configuration LP in the analysis, we never actually solve it and therefore the resulting algorithm is purely combinatorial.

Abstract: In this paper, we give efficient algorithms and lower bounds for solving the heavy hitters problem while preserving differential privacy in the fully distributed local model. In this model, there are $n$ parties, each of which possesses a single element from a universe of size $N$. The heavy hitters problem is to find the identity of the most common element shared amongst the $n$ parties. In the local model, there is no trusted database administrator, and so the algorithm must interact with each of the $n$ parties separately, using a differentially private protocol. We give tight information-theoretic upper and lower bounds on the accuracy to which this problem can be solved in the local model (giving a separation between the local model and the more common centralized model of privacy), as well as computationally efficient algorithms even in the case where the data universe $N$ may be exponentially large.

Abstract: We study the classic Vehicle Routing Problem in the setting of stochastic optimization with recourse. StochVRP is a two-stage problem, where demand is satisfied using two routes: fixed and recourse. The fixed route is computed using only a demand distribution. Then after observing the demand instantiations, a recourse route is computed – but costs here become more expensive by a factor lambda.
We present an O(log^2 n log(n lambda))-approximation algorithm for this stochastic routing problem, under arbitrary distributions. The main idea in this result is relating StochVRP to a special case of submodular orienteering, called knapsack rank-function orienteering. We also give a better approximation ratio for knapsack rank-function orienteering than what follows from prior work. Finally, we provide a Unique Games Conjecture based omega(1) hardness of approximation for StochVRP, even on star-like metrics on which our algorithm achieves a logarithmic approximation.

Abstract: We consider the online MST and TSP problems with recourse. The nodes of an unknown graph with metric edge cost appear one by one and must be connected in such a way that the resulting tree or tour has low cost. In the standard online setting, with irrevocable decisions, no algorithm can guarantee a constant competitive ratio. In our model we allow recourse actions by giving a limited budget of edge rearrangements per iteration. It has been an open question for more than 20 years if an online algorithm equipped with a constant (amortized) budget can guarantee constant-approximate solutions.

As our main result, we answer this question affirmatively in an amortized setting. We introduce an algorithm that maintains a nearly optimal tree when given constant amortized budget. In the non-amortized setting, we specify a promising proof technique and conjecture a structural property of optimal solutions that would prove a constant competitive ratio with a single recourse action. It might seem rather optimistic that such a small budget should be sufficient for a significant cost improvement. However, we can prove such power of recourse in the offline setting in which the sequence of node arrivals is known. Even this problem prohibits constant approximations if there is no recourse allowed. Surprisingly, already a smallest recourse budget significantly improves the performance guarantee from non-constant to constant.

Unlike in classical TSP variants, the standard double-tree and shortcutting approach does not give constant guarantees in the online setting. However, a non-trivial robust shortcutting technique allows to translate online MST results into TSP results at the loss of small factors.

Abstract: A covering integer program (CIP) is a mathematical program of the form:
min { c x : Ax >= 1, 0 <= x <= u, x integer }
where all entries are non-negative. In the online setting, the constraints (i.e., the rows of the constraint matrix A) arrive over time, and the algorithm can only increase the coordinates of x to maintain feasibility. As an intermediate step, we consider solving the covering linear program (CLP) online, where the integrality requirement on x is dropped.
Our main results are (a) an O(log k)-competitive online algorithm for solving the CLP, and (b) an O(log k log L)-competitive randomized online algorithm for solving the CIP. Here k <= n and L <= m respectively denote the maximum number of non-zero entries in any row and column of the constraint matrix A. By a result of Feige and Korman, this is the best possible for polynomial-time online algorithms, even in the special case of set cover.
The novel ingredient of our approach is to allow the dual variables to increase *and* *decrease* through the course of the algorithm. We show that the previous approaches, which either only raise dual variables, or lower duals only within a guess-and-double framework, cannot give a performance better than O(log n), even when each constraint only has a single variable (i.e., k = 1).

Abstract: In the k-arc connected subgraph problem, we are given a directed graph G and an integer k and the goal is the find a subgraph of minimum cost such that there are at least k-arc disjoint paths between any pair of vertices. We consider the minimum size k-arc connected subgraph problem where each arc of G has the same weight and give a 1+1/k approximation algorithm. Similar to the 2-approximation algorithm for this problem, our algorithm takes the union of k in-arborescences and k out-arborescences. The main difference is in the selection of arborescences. Here, inspired by recent work on traveling salesman problem, we select the arborescences randomly by sampling from a distribution on unions of k arborescenses that is defined by the linear programming relaxation of the problem. Unlike the work on TSP, we also crucially utilize sparsity properties of extreme point solutions of the linear programming relaxation. Our result improves on the 1 + 2/k approximation of Gabow et al. To complement the algorithm, we also show that the integrality gap of the minimum cost strongly connected subgraph problem (i.e., when k = 1) is at least 3/2 − c, for any c > 0. This result is inspired from the integrality gap result for the asymmetric traveling salesman problem giving further evidence of connections between the approximability of the two problems.

Abstract: Even, Selman, and Yacobi [ESY84,SY82] formulated a conjecture that in current terminology asserts that there do not exist disjoint NP-pairs all of whose separators are NP-hard viaTuring reductions. In this paper we consider a variant of this conjecture|there do not ex- ist disjoint NP-pairs all of whose separators are NP-hard via bounded truth-table reductions. We provide evidence for this conjecture. We also observe that if the original conjecture holds, then some of the known probabilistic public-key cryptosystems are not NP-hard to crack.

Abstract: Recently, \cite{BL} formalized an implicit assumption often made when choosing a clustering objective: that the optimum clustering to the objective should be preserved under small multiplicative perturbations to distances between points.
They showed that for max-cut clustering it is possible to circumvent NP-hardness and obtain polynomial-time algorithms for instances resilient to large (factor $O(\sqrt{n})$) perturbations, and subsequently \cite{ABS10} considered center-based objectives, giving algorithms for instances resilient to $O(1)$ factor perturbations.
In this paper, we greatly advance this line of work. For $k$-median, we present an algorithm that can optimally cluster instances resilient to $(1 + \sqrt{2})$-factor perturbations, solving an open problem of \cite{ABS10}. We additionally give algorithms for a more relaxed assumption in which we allow the optimal solution to change in a small $\epsilon$ fraction of the points after perturbation. We give the first bounds known for this more realistic and more general setting. We also provide positive results for min-sum clustering which is a generally much harder objective than $k$-median (and also non-center-based). Our algorithms are based on new linkage criteria that may be of independent interest.
Additionally, we give sublinear-time algorithms, showing algorithms that can return an implicit clustering from only access to a small random sample.

Abstract: Given a graph $G$ and an integer $k$, the \textsc{Feedback Vertex Set} (\textsc{FVS}) problem asks if there is a set $T$ of size at most $k$ that hits all cycles in the graph. Bodlaender (WG '91) gave the first fixed-parameter algorithm for \textsc{FVS} in undirected graphs. The fixed-parameter tractability status of \textsc{FVS} in directed graphs was a long-standing open problem until Chen et al. (STOC '08) showed that it is fixed-parameter tractable by giving an $4^{k}k!n^{O(1)}$ algorithm. In the subset versions of this problems, we are given an additional subset $S$ of vertices (resp. edges) and we want to hit all cycles passing through a vertex of $S$ (resp. an edge of $S$). Indeed both the edge and vertex versions are known to be equivalent in the parameterized sense. Recently the \textsc{Subset Feedback Vertex Set} in undirected graphs was shown to be FPT by Cygan et al. (ICALP '11) and Kakimura et al. (SODA '12). We generalize the result of Chen et al. (STOC '08) by showing that \textsc{Subset Feedback Vertex Set} in directed graphs can be solved in time $2^{2^{O(k)}}n^{O(1)}$, i.e., FPT parameterized by size $k$ of the solution. By our result, we complete the picture for feedback vertex set problems and their subset versions in undirected and directed graphs.
The technique of random sampling of important separators was used by Marx and Razgon (STOC '11) to show that \textsc{Undirected Multicut} is FPT and was generalized by Chitnis et al. (SODA '12) to directed graphs to show that \textsc{Directed Multiway Cut} is FPT. In this paper we give a general family of problems (which includes \textsc{Directed Multiway Cut} and \textsc{Directed Subset Feedback Vertex Set} among others) for which we can do random sampling of important separators and obtain a set which is disjoint from a minimum solution and covers its ``shadow". We believe this general approach will be useful for showing the fixed-parameter tractability of other problems in directed graphs.

Abstract: A graph $G = (V, E)$ is called $(k, \ell)$-sparse if $|F| \leq k|V(F)| - \ell$ for any $F \subseteq E$ with $F \neq \emptyset$. Here, $V(F)$ denotes the set of vertices incident to $F$. A graph $G=(V,E)$ is called $(k,\ell)$-full if $G$ contains a $(k,\ell)$-sparse subgraph with $|V|$ vertices and $k|V|-\ell$ edges. The family of edge sets of $(k,\ell)$-sparse subgraphs forms a family of independent sets of a matroid on $E$, known as the sparsity matroid of $G$. In this paper, we give a constant-time algorithm that approximates the rank of the sparsity matroid associated with a degree-bounded undirected graph. This algorithm leads to a constant-time tester for $(k,\ell)$-fullness in the bounded-degree model, (i.e., we can decide with high probability whether the input graph satisfies a property or far from it). Depending on the values of $k$ and $\ell$, our algorithm can test various properties of graphs such as connectivity, rigidity, and how many spanning trees can be packed in a unified manner.
Based on this result, we also propose a constant-time tester for $(k,\ell)$-edge-connected-orientability in the bounded-degree model, where an undirected graph $G$ is called $(k,\ell)$-edge-connected-orientable if there exists an orientation $\vec{G}$ of $G$ with a vertex $r \in V$ such that $\vec{G}$ contains $k$ arc-disjoint dipaths from $r$ to each vertex $v \in V$ and $\ell$ arc-disjoint dipaths from each vertex $v \in V$ to $r$.
A tester is called a one-sided error tester for $P$ if it always accepts a graph satisfying $P$. We show, for any $k \geq 2$ and (proper) $\ell \geq 0$, every one-sided error tester for $(k,\ell)$-fullness and $(k,\ell)$-edge-connected-orientability requires $\Omega(n)$ queries.

Abstract: Abstract. Peter Gacs showed [1] that for every n there exists a bit string x of length n whose plain complexity C (x) has almost maximal conditional complexity relative to x, i.e., C(C(x)|x) ≥ log n − log log n − O(1). Following Elena Kalinina [3], we provide a game-theoretic proof of this result; modifying her argument, we get a better (and tight) bound log n − O(1). We also show the same bound for prefix-free complexity.

Robert Solovay’s showed [10] that infinitely many strings x have maximal plain complexity but not maximal prefix-free complexity (among the strings of the same length); i.e. for some c: |x| − C(x) ≤ c and |x| + K(|x|) − K(x) ≥ log(2) |x| − clog(3) |x|. Using the result above, we provide a short proof of Solovay’s result. We also generalize it by showing that for some c and for all n there are strings x of length n with n − C (x) ≤ O(1), and n + K(n) − K(x) ≥ K(K(n)|n) − O(log K(K(n)|n)). This is very close to the upperbound K(K(n)|n) + O(1) proved by Solovay.

Abstract: An important question in cryptography concerns the possibility of achieving secure protocols even in the presence of physical attacks. Here we focus on an adversary that forces the honest player to re-use its randomness in different executions. This attack was first considered in the case of zero-knowledge proofs by Canetti et al~\cite{CGGM}, who focused on resetting verifiers (i.e., resettable zero knowledge). Next, Barak et al~\cite{BGGL}, focused on resetting provers (i.e., resettably sound zero knowledge) and proved that black-box simulation is impossible for any language in $\mc{NP}$. Finally, Deng et al~\cite{DGS09} constructed a \emph{simultaneously resettable} non black-box zero-knowledge argument (computationally sound only), that is therefore secure against resetting provers and verifiers.
We study the case of black-box simulation and construct nearly simultaneously resettable black-box zero-knowledge proof systems under standard assumptions. Our protocol is a {\em proof} (rather then just argument) system and requires that the resetting prover can reset the verifier up to a bounded number of times (which is unavoidable for black-box simulation), while the verifier can reset the prover an arbitrary polynomial number of times. The main achievement of our construction is that the round complexity is independent of the above bound of the number of the prover's resets.
To achieve our result, we construct a constant-round nearly simultaneously resettable coin-flipping protocol that we believe is of independent interest.

Abstract: The polynomial hierarchy plays a central role in classical complexity theory. Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study. We show that not only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Our work thus yields the first known hardness of approximation results for a quantum complexity class. Using these techniques, we also obtain hardness of approximation for the class QCMA. Our approach is based on the use of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy (Umans 1999). We close by showing that a variant of the local Hamiltonian problem with hybrid classical-quantum ground states is complete for the second level of our quantum hierarchy.

Abstract: We motivate and describe a new parameterized approximation paradigm which studies the interaction between performance ratio and running time for any parameterization of a given optimization problem. As a key tool, we introduce the concept of $\alpha$-{\em shrinking~transformation}, for $\alpha \geq 1$. Applying such transformation to a parameterized problem instance decreases the parameter value, while preserving approximation ratio of $\alpha$ (or $\alpha${\em-fidelity}). For example, it is well-known that {\it Vertex Cover} cannot be approximated within any constant factor better than 2 \cite{KR08} (under usual assumptions). Our parameterized $\alpha$-approximation algorithm for {\it k-Vertex Cover}, parameterized by the solution size, has a running time of $1.273^{(2 - \alpha)k}$, where the running time of the best FPT algorithm is $1.273^k$ [10]. Our algorithms define a continuous tradeoff between running times and approximation ratios, allowing practitioners to appropriately allocate computational resources.
Moving even beyond the performance ratio, we call for a new type of {\it approximative kernelization race}. Our $\alpha$-shrinking transformations can be used to obtain kernels which are smaller than the best known for a given problem. For the {\it Vertex Cover} problem we obtain a kernel size of $2(2 - \alpha)k$. The smaller ``$\alpha$-fidelity'' kernels allow us to solve exactly problem instances more efficiently, while obtaining an approximate solution for the original instance.
We show that such transformations exist for several fundamental problems, including {\em Vertex Cover}, {\em d-Hitting-Set}, {\em Connected Vertex Cover} and {\em Steiner Tree}. We note that most of our algorithms are easy to implement and are therefore practical in use.

Abstract: Consider the following online version of the submodular maximization problem under a matroid constraint: We are given a set of elements over which a matroid is defined. The goal is to incrementally choose a subset that remains independent in the matroid over time. At each time, a new weighted rank function of a different matroid (one per time) over the same elements is presented; the algorithm can add a few elements to the incrementally constructed set, and reaps a reward equal to the value of the new weighted rank function on the current set. The goal of the algorithm as it builds this independent set online is to maximize the sum of these (weighted rank) rewards. As in regular online analysis, we compare the rewards of our online algorithm to that of an offline optimum, namely a single independent set of the matroid that maximizes the sum of the weighted rank rewards that arrive over time. This problem is a natural extension of two well-studied streams of earlier work: the first is on online set cover algorithms (in particular for the max coverage version) while the second is on approximately maximizing submodular functions under a matroid constraint.

In this paper, we present the first randomized online algorithms for this problem with poly-logarithmic competitive ratio. To do this, we employ the LP formulation of a scaled reward version of the problem. Then we extend a weighted-majority type update rule along with uncrossing properties of tight sets in the matroid polytope to find an approximately optimal fractional LP solution. We use the fractional solution values as probabilities for a online randomized rounding algorithm. To show that our rounding produces a sufficiently large reward independent set, we prove and use new covering properties for randomly rounded fractional solutions in the matroid polytope that may be of independent interest.

Abstract: We study the problem of maximizing a monotone submodular set function subject to linear packing constraints. An instance of this problem consists of a matrix $A \in [0,1]^{m \times n}$, a vector $b \in [1,\infty)^m$, and a monotone submodular set function $f: 2^{[n]} \rightarrow \bbR_+$. The objective is to find a set $S$ that maximizes $f(S)$ subject to $A x_{S} \leq b$, where $x_S$ stands for the characteristic vector of the set $S$. A well-studied special case of this problem is when $f$ is linear. This special linear case captures the class of packing integer programs.
Our main contribution is an efficient combinatorial algorithm that achieves an approximation ratio of $\Omega(1 / m^{1/W})$, where $W = \min\{b_i / A_{ij} : A_{ij} > 0\}$ is the width of the packing constraints. This result matches the best known performance guarantee for the linear case. One immediate corollary of this result is that the algorithm under consideration achieves constant factor approximation when the number of constraints is constant or when the width of the constraints is sufficiently large. This motivates us to study the large width setting, trying to determine its exact approximability. We develop an algorithm that has an approximation ratio of $(1 - \epsilon)(1 - 1/e)$ when $W = \Omega(\ln m / \epsilon^2)$. This result essentially matches the theoretical lower bound of $1 - 1/e$. We also study the special setting in which the matrix $A$ is binary and $k$-column sparse. A $k$-column sparse matrix has at most $k$ non-zero entries in each of its column. We design a fast combinatorial algorithm that achieves an approximation ratio of $\Omega(1 / (Wk^{1/W}))$, that is, its performance guarantee only depends on the sparsity and width parameters.

Abstract: The factor graph of an instance of a symmetric constraint satisfaction problem on $n$ Boolean variables and $m$ constraints (CSPs such as k-SAT, k-AND, k-LIN) is a bipartite graph describing which variables appear in which constraints. The factor graph describes the instance up to the polarity of the variables, and hence there are up to $2^{km}$ instances of the CSP that share the same factor graph. It is well known that factor graphs with certain structural properties make the underlying CSP easier to either solve exactly (e.g., for tree structures) or approximately (e.g., for planar structures). We are interested in the following question: is there a factor graph for which if one can solve every instance of the CSP with this particular factor graph, then one can solve every instance of the CSP regardless of the factor graph (and similarly, for approximation)? We call such a factor graph {\em universal}. As one needs different factor graphs for different values of $n$ and $m$, this gives rise to the notion of a family of universal factor graphs.

We initiate a systematic study of universal factor graphs, and present some results for max-$k$SAT. Our work has connections with the notion of preprocessing as previously studied for closest codeword and closest lattice-vector problems, with proofs for the PCP theorem, and with tests for the long code. Many questions remain open.

Abstract: We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1-o(1) fraction of all 2-player XOR games.

Abstract: We consider the problem of testing a basic property of collections of distributions: having similar means. Namely, the algorithm should accept collections of distributions in which all distributions have means that do not differ by more than some given parameter, and should reject collections that are relatively far from having this property. By `far' we mean that it is necessary to modify the distributions in a relatively significant manner (measured according to the $\ell_1$ distance averaged over the distributions) so as to obtain the property.

We study this problem in two models. In the first model (the {\em query model\/}) the algorithm may ask for samples from any distribution of its choice, and in the second model (the {\em sampling model\/}) the distributions from which it gets samples are selected randomly. We provide upper and lower bounds in both models. In particular, in the query model, the complexity of the problem is polynomial in $1/\eps$ (where $\eps$ is the given distance parameter).
While in the sampling model, the complexity grows roughly as $m^{1-{\rm poly}(\eps)}$, where $m$ is the number of distributions.

Abstract: We give a general method for converting online algorithms to local computation algorithms, by selecting a random permutation of the input, and simulating running the online algorithm. We bound the number of steps of the algorithm using a query tree, which models the dependencies between queries. We improve previous analyses of query trees on graphs of bounded degree, and extend the analysis to the cases where the degrees are distributed binomially, and to a special case of bipartite graphs.

Using this method, we give a local computation algorithm for maximal matching in graphs of bounded degree, which runs in time and space O(log^3 n).
We also show how to convert a large family of load balancing algorithms (related to balls and bins problems) to local computation algorithms. This gives several local load balancing algorithms which achieve the same approximation ratios as the online algorithms, but run in O(log n) time and space.
Finally, we modify existing local computation algorithms for hypergraph 2-coloring and k-CNF and use our improved analysis to obtain better time and space bounds, of O(log^4 n), removing the dependency on the maximal degree of the graph from the exponent.

Abstract: A {\em coverage function} $f$ over a ground set $[m]$ is associated with a universe $U$ of weighted elements and $m$ sets $A_1,\ldots,A_m \subseteq U$, and for any $T\subseteq [m]$, $f(T)$ is defined as the total weight of the elements in the union $\cup_{j\in T} A_j$. Coverage functions are an important special case of submodular functions, and arise in many applications, for instance as a class of utility functions of agents in combinatorial auctions.
Set functions such as coverage functions often lack succinct representations, and in algorithmic applications, an access to a value oracle is assumed. In this paper, we ask whether one can test if a given oracle is that of a coverage function or not. We demonstrate an algorithm which makes $O(m|U|)$ queries to an oracle of a coverage function and completely reconstructs it. This gives a polytime tester for {\em succinct} coverage functions for which $|U|$ is polynomially bounded in $m$. In contrast, we demonstrate a set function which is ``far" from coverage, but requires $2^{\tilde{\Theta}(m)}$ queries to distinguish it from the class of coverage functions.

Abstract: In the standard setting of communication complexity, two players each have an input and they wish to compute some function of the joint inputs. This has been the object of much study and a wide variety of lower bound methods have been introduced to address the problem of showing lower bounds on communication. Recently, Jain and Klauck introduced the partition bound, which subsumes many of the known methods, in particular factorization norm (γ2), discrepancy, and the rectangle (corruption) bound. Physicists have considered a closely related scenario where two players share a predefined entangled state. Each is given a measurement as input, which they per- form on their share of the system. The outcomes of the measurements follow a dis- tribution which is predicted by quantum mechanics. Physicists want to rule out the possibility that there is a classical explanation for the distribution, through loop- holes such as communication or detector inefficiency. In an experimental setting, Bell inequalities are used to distinguish truly quantum from classical behavior. We present a new lower bound technique based on the notion of detector inef- ficiency (where some runs are discarded by either of the players) for the extended setting of simulating distributions, and show that it coincides with the partition bound in the special case of computing functions. As usual, the dual form is more feasible to use, and we show that it amounts to constructing an explicit Bell in- equality. We also give a lower bound on quantum communication complexity which can be viewed as a quantum analogue of the rectangle bound, effectively overcoming the necessity of a quantum minmax theorem. For one-way communication, we show that the quantum one-way partition bound is tight for classical communication with shared entanglement up to ar- bitrarily small error. Finally, an important goal in physics is to devise robust Bell experiments that are impervious to noise and detector inefficiency. We make further progress to- wards this by giving a general tradeoff between communication, Bell inequality violation, and detector efficiency.

Abstract: We study the well-known \emph{Label Cover} problem under the additional requirement that problem instances have large girth. We show that if the girth is some $k$, the problem is roughly $2^{\log^{1-\epsilon} n/k}$ hard to approximate for all constant $\epsilon > 0$. A similar theorem was claimed by Elkin and Peleg [ICALP 2000], but their proof was later found to have a fundamental error. Thus for the problem of Label Cover with large girth we give {\em the first} non-trivial lower bound. We use the new proof to show inapproximability for the basic $k$-spanner problem, which is both the simplest problem in graph spanners and one of the few for which super-logarithmic hardness was not known. Assuming $NP \not\subseteq BPTIME(2^{polylog(n)})$, we show (roughly) that for every $k \geq 3$ and every constant $\epsilon > 0$ it is hard to approximate the basic $k$-spanner problem within a factor better than $2^{(\log^{1-\epsilon} n) / k}$. A similar hardness for basic $k$-spanner was claimed by Elkin and Peleg [ICALP 2000], but the error in their analysis of Label Cover made this proof fail as well. For the basic $k$-spanner problem we improve the previous best lower bound of $\Omega(\log n)/k$ by Kortsarz [1998]. Our main technique is subsampling the edges of $2$-query PCPs, which allows us to reduce the degree of a PCP to be essentially equal to the soundness desired. This turns out to be enough to basically guarantee large girth.

Abstract: Given a set $\calP$ of $h$ pairwise-disjoint polygonal obstacles of totally $n$ vertices in the plane, we study the problem of computing the (weakly) visibility polygon from a polygonal obstacle $P^*$ (an island) in $\calP$, and present an $O(n^2h^2)$ time algorithm for it. Previously, the special case where $P^*$ is a line segment was solved in $O(n^4)$ time, which is worst-case optimal. In addition, when all obstacles in $\calP$ (including $P^*$) are convex, our algorithm runs in $O(n+h^4)$ time.

Abstract: We propose a generic and simple technique called "dyadic rounding" for rounding real vectors to zero-one vectors, and show its several applications in approximating singular vectors of matrices by zero-one vectors, cut decompositions of matrices, and norm optimization problems. Our rounding technique leads to the following consequences.

1. Given any $A \in \R^{m \times n}$, there exists $z \in \{0, 1\}^{n}$ such that
\[
\frac{\norm{Az}_{q}}{\norm{z}_{p}} \geq \Omega\left(p^{1 - \frac{1}{p}} (\log n)^{\frac{1}{p} - 1}\right) \norm{A}_{p \mapsto q},
\]
where $\norm{A}_{p \mapsto q} = \max_{x \neq 0} \norm{Ax}_{q} / \norm{x}_{p}$. Moreover, given any vector $v \in \R^{n}$ we can round it to a vector $z \in \{0, 1\}^{n}$ with the same approximation guarantee as above, but now the guarantee is with respect to $\norm{Av}_{q}/\norm{Av}_{p}$ instead of $\norm{A}_{p \mapsto q}$. Although stated for $p \mapsto q$ norm, this generalizes to the case when $\norm{Az}_{q}$ is replaced by \emph{any} norm of $z$.

2. Given any $A \in \R^{m \times n}$, we can efficiently find $z \in \{0, 1\}^{n}$ such that
\[
\frac{\norm{Az}}{\norm{z}} \geq \frac{\sigma_{1}(A)}{2 \sqrt{2 \log n}},
\]
where $\sigma_{1}(A)$ is the top singular value of $A$. Extending this, we can efficiently find \emph{orthogonal} $z_{1}, z_{2}, \dotsc, z_{k} \in \{0, 1\}^{n}$ such that
\[
\frac{\norm{Az_{i}}}{\norm{z_{i}}} \geq \Omega\left(\frac{\sigma_{k}(A)}{\sqrt{k \log n}}\right), \quad \text{for all $i \in [k]$}.
\]
We complement these results by showing that they are almost tight.

3. Given any $A \in \R^{m \times n}$ of rank $r$, we can approximate it (under the Frobenius norm) by a sum of $O(r \log^{2} m \log^{2} n)$ cut-matrices, within an error of at most $\fnorm{A}/\text{poly}(m, n)$. In comparison, the Singular Value Decomposition uses $r$ rank-$1$ terms in the sum (but not necessarily cut matrices) and has zero error, whereas the cut decomposition lemma by Frieze and Kannan in their algorithmic version of Szemer\'{e}di's regularity partition \cite{FK-conf,FK-journal} uses only $O(1/\eps^{2})$ cut matrices but has a large $\eps \sqrt{mn} \fnorm{A}$ error (under the cut norm). Our algorithm is {deterministic} and more efficient for the corresponding error range.

Abstract: Backdoor sets, a notion introduced by Williams et al. in 2003, are certain sets of key variables of a CNF formula F that make it easy to solve the formula; by assigning truth values to the variables in a backdoor set, the formula gets reduced to one or several polynomial-time solvable formulas. More specifically, a weak backdoor set of F is a set X of variables such that there exits a truth assignment t to X that reduces F to a satisfiable formula F[t] that belongs to a polynomial-time decidable base class C. A strong backdoor set is a set X of variables such that for all assignments t to X, the reduced formula F[t] belongs to C.
We study the problem of finding backdoor sets of size at most k with respect to the base class of CNF formulas with acyclic incidence graphs, taking k as the parameter. We show that
1. the detection of weak backdoor sets is W[2]-hard in general but fixed-parameter tractable for r-CNF formulas, for any fixed r>=3, and
2. the detection of strong backdoor sets is fixed-parameter approximable.

Result 1 is the the first positive one for a base class that does not have a characterization with obstructions of bounded size. Result 2 is the first positive one for a base class for which strong backdoor sets are more powerful than deletion backdoor sets.
Not only SAT, but also #SAT can be solved in polynomial time for CNF formulas with acyclic incidence graphs. Hence Result 2 establishes a new structural parameter that makes #SAT fixed-parameter tractable and that is incomparable with known parameters such as treewidth and cliquewidth.
We obtain the algorithms by a combination of an algorithmic version of the Erdős-Pósa Theorem, Courcelle's model checking for monadic second order logic, and new combinatorial results on how disjoint cycles can interact with the backdoor set. These new combinatorial arguments come into play when the incidence graph of F has many vertex-disjoint cycles. As only few of these cycles can vanish by assigning a value to a variable from the cycle, many cycles need to vanish by assigning values to variables that are in clauses of these cycles. These external variables are either so rare or structured that our combinatorial arguments can identify a small set of variables such that any backdoor set of size at most k contains at least one of these variables, or they are so abundant and unstructured that they themselves create cycles in the incidence graph in such a way that F cannot have a backdoor set of size at most k.

Abstract: We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. Despite its importance for modern real-time systems, this problem has not been studied before. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of 11 + 4√3 ≈ 17.9 and show that any polynomial-time algorithm needs a speedup factor of at least 2, unless P = NP. In the case of a constant number of machines we give a polynomial-time approximation scheme. Key to these results are two new relaxations of the demand bound function which yields a sufficient and necessary condition for a task system on a single machine to be feasible.

Abstract: In this paper, a fully compressed pattern matching problem is studied. The compression is represented by straight-line programs (SLPs), i.e. a context-free grammars generating exactly one string; the term fully means that both the pattern and the text are given in the compressed form. A novel algorithmic technique of dealing with SLPs is introduced and applied: the SLPs are recompressed, so that substrings of the pattern and text are encoded in both SLPs in the same way. To this end, the SLPs are locally decompressed and then recompressed in a uniform way.
This technique yields an O((n+m) log M log(n+m)) algorithm for compressed pattern matching, where n (m) is the size of the compressed representation of the text (pattern, respectively), while M is the size of the decompressed pattern. Since M <= 2^m, this greatly improves the previously best O(m^2n) algorithm.
Since LZ compression standard reduces to SLP with log(N/n) overhead and in O(n log(N/n)) time, the presented algorithm can be straightforwardly applied also to the fully LZ-compressed pattern matching problem, yielding an O(s log s log M) running time algorithm, where s = n log(N/n) + m log(M/m). To author's best knowledge there are no fully compressed pattern matching algorithms for LZ other than adaptations of FCPM for SLP.

Abstract: In this paper, we study a parity based generalization of the classical Multiway Cut problem. Formally, we study the Parity Multiway Cut problem, where the input is a graph G, vertex subsets T_e and T_o (T=T_e \cup T_o) called terminals, a positive integer k and the objective is to test whether there exists a k-sized vertex subset S such that S intersects all odd paths from v in T_o to T \ {v} and all even paths from v in T_e to $T \ {v}$. When $T_e=T_o$, this is precisely the classical Multiway Cut problem. If T_o = Ø then this is the Even Multiway Cut problem and if T_e=Ø then this is the Odd Multiway Cut problem. We remark that even the problem of deciding whether there is a set of at most k vertices that intersects all odd paths between a given pair of vertices s and t is NP-complete.
Our primary motivation for studying this problem is the recently initiated study of the parameterized complexity of parity versions of graphs minors (Kawarabayashi, Reed and Wollan, FOCS 2011) and separation problems similar to Multiway Cut.
The area of design of parameterized algorithms for graph separation problems has seen a lot of recent activity, which includes algorithms for Multi-Cut on undirected graphs (Marx and Razgon, STOC 2011, Bousquet, Daligault and Thomasse, STOC 2011), k-Way Cut (Kawarabayashi and Thorup, FOCS 2011), and Multiway Cut on directed graphs (Chitnis, Hajiaghayi and Marx, SODA 2012). A second motivation is that this problem serves as a good example to illustrate the application of a generalization of important separators which we introduce, and can be applied even when most of the recently develped tools fail to apply. We believe that this could be a useful tool for several other separation problems as well. We obtain this generalization by dividing the graph into slices with small boundaries and applying a divide and conquer paradigm over these slices. We show that Parity Multiway Cut is fixed parameter tractable (FPT) by giving an algorithm that runs in time f(k)n^{O(1)}. More precisely, we show that instances of this problem with solutions of size O(\log \log n) can be solved in polynomial time. Along with this new notion of generalized important separators, our algorithm also combines several ideas used in previous parameterized algorithms for graph separation problems including the notion of important separators and randomized selection of important sets to simplify the input instance.

Abstract: We study the fundamental problem of the exact and efficient generation of random values from a finite and discrete probability distribution. Suppose that we are given n distinct events with associated probabilities p_1, ..., p_n. We consider the problem of sampling a subset, which includes the i-th event independently with probability p_i, and the problem of sampling from the distribution, where the i-th event has a probability proportional to p_i. For both problems we present on two different classes of inputs - sorted and general probabilities - efficient
preprocessing algorithms that allow for asymptotically optimal querying, and prove almost matching lower bounds for their complexity.

Abstract: We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut above the Edwards-Erdős bound is fixed-parameter tractable: we give an algorithm that for any connected graph with n vertices and m edges finds a cut of size m/2 + (n-1)/4 + k in time 2^O(k)n^4, or decides that no such cut exists.
This answers a long-standing open question from parameterized complexity that has been posed several times over the past 15 years. It also improves an earlier result by Bollobás and Scott, who considered a weaker lower bound on the size of a maximum cut.
Our algorithm is asymptotically optimal, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size.

Abstract: The MULTICUT problem, given a graph G, a set of terminal pairs T={(s_i,t_i) | 1\leq i\leq r} and an integer p, asks whether one can find a cutset consisting of at most p non-terminal vertices that separates all the terminal pairs, i.e., after removing the cutset, t_i is not reachable from s_i for each 1\leq i\leq r. The fixed-parameter tractability of MULTICUT in undirected graphs, parameterized by the size of the cutset only, has been recently proven by Marx and Razgon (STOC 2011) and, independently, by Bousquet et al. (STOC 2011), after resisting attacks as a long-standing open problem. In this paper we prove that MULTICUT is fixed-parameter tractable on directed acyclic graphs, when parameterized both by the size of the cutset and the number of terminal pairs. We complement this result by showing that this is implausible for parameterization by the size of the cutset only, as this version of the problem remains $W[1]$-hard.

Abstract: In this paper, we revisit the classical $k$-median problem: Given $n$ points in a metric space, select $k$ centers so as to minimize the sum of distances of points to their closest center. Using the standard LP relaxation for $k$-median, we give an efficient algorithm to construct a probability distribution on sets of $k$ centers that matches the marginals specified by the optimal LP solution. Our algorithm draws inspiration from clustering and randomized rounding approaches that have been used previously for $k$-median and the closely related facility location problem, although ensuring that we choose at most $k$ centers requires a careful dependent rounding procedure.
Analyzing the approximation ratio of our algorithm presents significant technical difficulties: we are able to show an upper bound of $3.25$. While this is worse than the current best known $3+\epsilon$ guarantee of \cite{AGK01}, our approach is interesting because: (1) The random choice of the $k$ centers given by the algorithm keeps the marginal distributions and satisfies the negative correlation, leading to 3.25 approximation algorithms for some generalizations of the $k$-median problem, including the $k$-UFL problem introduced in \cite{JV01}, (2) our algorithm runs in $\tilde{O}(k^3 n^2)$ time compared to the $O(n^8)$ time required by the local search algorithm of \cite{AGK01} to guarantee a $3.25$ approximation, and (3) our approach has the potential to beat the decade old bound of $3+\epsilon$ for $k$-median by a suitable instantiation of various parameters in the algorithm.
We also give a $34$-approximation for the knapsack median problem, which greatly improves the approximation constant in \cite{Kum12}. Besides the improved approximation ratio, both our algorithm and analysis are simple, compared to \cite{Kum12}. Using the same technique, we also give a $9$-approximation for matroid median problem introduced in \cite{KKN11}, improving on their $16$-approximation.

Abstract: We consider problems related to the concepts of dominators and independent spanning trees and provide efficient algorithms for their solution. First, we revisit the problem of dominator verification and present simpler linear-time algorithms for acyclic, reducible, and general digraphs. Then we consider the problem of certifying dominators, which is to compute the dominators of a digraph together with some extra information (a certificate of correctness) that makes the verification of dominators and of the extra information very simple as well as linear-time. Such a certificate makes dominators self-verifying. Our certificates are based on the concepts of strongly independent spanning trees and directed bipolar orders. These concepts are of independent interest and were previously considered only for the special case of digraphs which, for every vertex v \not= r, contain two vertex disjoint paths from r to v, where r is a distinguished root vertex. Moreover, all previous algorithms required Omega(nm) time in the worst case for a digraph with n vertices and m arcs. Here we provide linear-time algorithms for these constructions. Based on these results, we develop simple linear-time algorithms for certifying dominators. Furthermore, we provide applications to other problems in digraphs.

Abstract: We consider {\em node-weighted} network design in planar and minor-closed families of graphs. In particular we focus on the edge-connectivity survivable network design problem (EC-SNDP). The input consists of a node-weighted undirected graph $G=(V,E)$ and integral connectivity requirements $r(uv)$ for each pair of nodes $uv$. The goal is to find a minimum node-weighted subgraph $H$ of $G$ such that, for each pair $uv$, $H$ contains $r(uv)$ edge-disjoint paths between $u$ and $v$. Our main result is an $O(k)$-approximation algorithm for EC-SNDP where $k=\max_{uv} r(uv)$ is the maximum requirement. This improves the $O(k \log n)$-approximation known for node-weighted EC-SNDP in general graphs \cite{Nutov10}. Our algorithm and analysis applies for the more general problem of covering a proper function with maximum requirement $k$. Our result is inspired by and generalizes the work of Demaine, Hajiaghayi and Klein \cite{DemaineHK09} who considered node-weighted Steiner tree and Steiner forest problems (and more generally covering $0$-$1$ proper functions) in planar graphs and gave constant factor approximations for these problems.

Abstract: For $f$ a weighted voting scheme used by $n$ voters to choose between two candidates, the $n$ \emph{Shapley-Shubik Indices} of $f$ provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley and Martin Shubik in 1954 \cite{SS54} and are widely studied in social choice theory as a measure of the ``influence'' of voters. The \emph{Inverse Shapley Value Problem} is the problem of designing a weighted voting scheme which (approximately) achieves a desired input vector of values for the Shapley indices. Despite much interest in this problem no provably correct and efficient algorithm was known prior to our work.
We give the first efficient algorithm with provable performance guarantees for the Inverse Shapley Value Problem. For any constant $\eps > 0$ our algorithm runs in fixed poly$(n)$ time (the degree of the polynomial is independent of $\eps$) and has the following performance guarantee: given as input a vector of desired Shapley indices, if any ``reasonable'' weighted voting scheme (roughly, one in which the threshold is not too skewed) approximately matches the desired vector of values to within some small error, then our algorithm explicitly outputs a weighted voting scheme that achieves this vector of Shapley indices to within error $\eps.$ If there is a ``reasonable'' voting scheme in which all voting weights are integers at most $\poly(n)$ that approximately achieves the desired Shapley indices, then our algorithm runs in time $\poly(n)$ and outputs a weighted voting scheme that achieves the target vector of Shapley indices to within error $\eps=n^{-1/8}.$

Abstract: We consider the problem of preprocessing $N$ points in 2D, each endowed with a priority, to answer the following queries: given a axis-parallel rectangle, determine the point with the largest priority in the rectangle. Using the ideas of the \emph{effective entropy} of range maxima queries and \emph{succinct indices} for range maxima queries, we obtain a structure that uses $O(N)$ words and answers the above query in $O(\log N \log \log N)$ time. This a direct improvement of Chazelle's result from 1985 \cite{Chazelle88} for this problem -- Chazelle required $O(N/\epsilon)$ words to answer queries in $O((\log N)^{1+\epsilon})$ time for any constant $\epsilon > 0$.

Abstract: Motivated by the need to provide an upon-demand ecient validation of various nancial transactions (e.g., the abounding Internet auctions), we present a novel secure, and ecient method which validates the output of a transaction. The method is based on inputs which are publicly committed to using generic commitment (even a value in tamper-proof hardware with only input/ output access can be considered (we call it: strictly black box [SBB] commitments). These commitments are typically faster than public-key ones, and they are the only cryptographic/ security tool we give the poly-time players throughout. Under such "structure-less" "non-algebraic" conditions we need to validate the correctness of a relation involving the publicly claimed output of a publicly known straight line computation (computed over the hidden committed inputs). We want the validation to remain secure (e.g., zero knowledge), and the question is: How can we show the validity securely given only the black-box commitments? Further: how can we use the given committed inputs for many proofs? (e.g., to reduce the cheating probability by repeated interactive proofs), or merely how can we securely copy the committed inputs? To this end (1) we first develop a novel technique of input representation which we call "split representation" over a finite field which give split commitments, embedding this representation in generic commitments; (2) secondly, a method called "translation," which eciently and secretly validates the straight line computation over the committed values is developed; and (3) finally, a validation boosting technique based on enhanced representation method we call "redundant split representation/ commitment" is presented which allows validated replication of committed values, which, in turn, implies overwhelming probability of validity and enables multi-proofs on a single input. Generic ecient protocol which is SBB ZK/ WI (witness indistinguishable) proof of knowledge for straight line programs over the committed inputs (and negligible soundness error) is, in turn, our main result, while an extremely ecient SBB ZK/ WI validation proof of Vickrey auctions is our demonstrative application.

Abstract: We consider online resource allocation problems where given a set of requests our goal is to select a subset that maximizes a value minus cost type of objective function. Requests are presented online in random order, and each request possesses an adversarial value and an adversarial size. The online algorithm must make an irrevocable accept/reject decision as soon as it sees each request. The "profit" of a set of accepted requests is its total value minus a convex cost function of its total size. This problem falls within the framework of secretary problems. Unlike previous work in that area, one of the main challenges we face is that the objective function can be positive or negative and we must guard against accepting requests that look good early on but cause the solution to have an arbitrarily large cost as more requests are accepted. This requires designing new techniques.
We study this problem under various feasibility constraints and present online algorithms with competitive ratios only a constant factor worse than those known in the absence of costs for the same feasibility constraints. We also consider a multi-dimensional version of the problem that generalizes multi-dimensional knapsack within a secretary framework. In the absence of any feasibility constraints, we present an O(l) competitive algorithm where l is the number of dimensions; this matches within constant factors the best known ratio for multi-dimensional knapsack secretary.

Abstract: We give new lower bounds for randomized NNS data structures in the cell probe model based on {\em robust} metric expansion for two metric spaces: $l_\infty$ and Earth Mover Distance (EMD) in high dimensions. In particular, our results imply stronger non-embedability for these metric spaces into $l_1$. The main components of our approach are a strengthening of the isoperimetric inequality for the distribution on $l_\infty$ introduced by Andoni et al [FOCS'08] and a robust isoperimetric inequality for EMD on quotients of the boolean hypercube.

Abstract: Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs: every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear number of clauses. This lemma has subsequently played a key role in the study of the exact complexity of the satisfiability problem. A natural question is whether an analogous structural result holds for CNFs or even for broader non-uniform classes such as constant-depth circuits or Boolean formulae. We prove a very strong negative result in this connection: For every superlinear function $f(n)$, there are CNFs of size $f(n)$ which cannot be written as a disjunction of $2^{n- \varepsilon n}$ CNFs each having a linear number of clauses for any $\varepsilon > 0$. We also give a hierarchy of such non-sparsifiable CNFs: For every $k$, there is a $k'$ for which there are CNFs of size $n^{k'}$ which cannot be written as a sub-exponential size disjunction of CNFs of size $n^{k}$. Furthermore, our lower bounds hold not just against CNFs but against an {\it arbitrary} family of functions as long as the cardinality of the family is appropriately bounded.
As by-products of our result, we make progress both on questions about circuit lower bounds for depth-3 circuits and satisfiability algorithms for constant-depth circuits. Improving on a result of Impagliazzo, Paturi and Zane, for any $f(n) = \omega(n \log(n))$, we define a pseudo-random function generator with seed length $f(n)$ such that with high probability, a function in the output of this generator does not have depth-3 circuits of size $2^{n-o(n)}$ with bounded bottom fan-in. We show that if we could decrease the seed length of our generator below $n$, we would get an explicit function which does not have linear-size logarithmic-depth series-parallel circuits, solving a long-standing open question.
Motivated by the question of whether CNFs sparsify into bounded-depth circuits, we show a {\it simplification} result for bounded-depth circuits: any bounded-depth circuit of linear size can be written as a sub-exponential size disjunction of linear-size constant-width CNFs. As a corollary, we show that if there is an algorithm for CNF satisfiability which runs in time $O(2^{\alpha n})$ for some fixed $\alpha < 1$ on CNFs of linear size, then there is an algorithm for satisfiability of linear-size constant-depth circuits which runs in time $O(2^{(\alpha + o(1))n})$.

Abstract: In this work we propose a generalization of Winfree's abstract Tile Assembly Model (aTAM) in which tile types are assigned rigid shapes, or geometries, along each tile face. We examine the number of distinct tile types needed to assemble shapes within this model, the temperature required for efficient assembly, and the problem of designing compact geometric faces to meet given compatibility specifications. We pose the following question: can complex geometric tile faces arbitrarily reduce the number of distinct tile types to assemble shapes? Within the most basic generalization of the aTAM, we show that the answer is no. For almost all $n$ at least $\Omega(\sqrt{\log n})$ tile types are required to uniquely assemble an $n\times n$ square, regardless of how much complexity is pumped into the face of each tile type. However, we show for all $n$ we can achieve a matching $O(\sqrt{\log n})$ tile types, beating the known lower bound of $\Theta(\log n / \log\log n)$ that holds for almost all $n$ within the aTAM. Further, our result holds at temperature $\tau=1$. Our next result considers a geometric tile model that is a generalization of the 2-handed abstract tile assembly model in which tile aggregates must move together through obstacle free paths within the plane. Within this model we present a novel construction that harnesses the collision free path requirement to allow for the unique assembly of any $n\times n$ square with a sleek $O(\log\log n)$ distinct tile types. This construction is of interest in that it is the first tile self-assembly result to harness collision free planar translation to increase efficiency, whereas previous work has simply used the planarity restriction as a desireable quality that could be achieved at reduced efficiency. This surprisingly low tile type result further emphasizes a fundamental open question: Is it possible to assemble $n\times n$ squares with $O(1)$ distinct tile types? Essentially, how far can the trade off between the number of distinct tile types required for an assembly and the complexity of each tile type itself be taken?

Abstract: In this paper, we consider generalizations of classical covering problems to handle hard capacities. In the hard capacitated set cover problem, additionally each set has a covering capacity which we are not allowed to exceed. In other words, even after picking a set, we may cover at most a specified number of elements. Based on the classical results by Wolsey, an $O(\log n)$ approximation follows for this problem.
Chuzhoy and Naor [FOCS 2002], first studied the special case of unweighted vertex cover with hard capacities and developed an elegant 3 approximation for it based on rounding a natural LP relaxation. This was subsequently improved to a 2 approximation by Gandhi et al. [ICALP 2003]. These results are surprising in light of the fact that for weighted vertex cover with hard capacities, the problem is at least as hard as set cover to approximate. Hence this separates the unweighted problem from the weighted version.
The set cover hardness precludes the possibility of a constant factor approximation for the hard-capacitated vertex cover problem on weighted graphs. However, it was not known whether a better than logarithmic approximation is possible on unweighted but {\em multigraphs}, i.e., graphs that may contain parallel edges. Neither the approach of Chuzhoy and Naor, nor the follow-up work of Gandhi et al. can handle the case of multigraphs. In fact, achieving a constant factor approximation for hard-capacitated vertex cover problem on unweighted multigraphs was posed as an open question in Chuzhoy and Naor's work. In this paper, we resolve this question by providing the first constant factor approximation algorithm for the vertex cover problem with hard capacities on unweighted multigraphs. Previous works also cannot handle hypergraphs which is analogous to consider set systems where elements belong to at most $f$ sets. In this paper, we give an $O(f)$ approximation algorithm for this problem. Further, we extend these works to consider partial covers.

Abstract: We give algorithms for the optimization problem: $\max_\rho \ip{Q}{\rho}$, where $Q$ is a Hermitian matrix, and the variable $\rho$ is a bipartite {\em separable} quantum state. This problem lies at the heart of several problems in quantum computation and information, such as the complexity of QMA(2). While the problem is NP-hard, our algorithms are better than brute force for several instances of interest. In particular, they give PSPACE upper bounds on promise problems admitting a QMA(2)protocol in which the verifier performs only logarithmic number of elementary gate on both proofs, as well as the promise problem of deciding if a bipartite local Hamiltonian has large or small ground energy. For $Q\ge0$, our algorithm runs in time exponential in $\|Q\|_F$. While the existence of such an algorithm was first proved recently by Brand{\~a}o, Christandl and Yard [{\em Proceedings of the 43rd annual ACM Symposium on Theory of Computation} , 343--352, 2011], our algorithm is conceptually simpler.

Abstract: Quadratic Programming (QP) is the well-studied problem of maximizing over {-1,1} values the quadratic form \sum_{i \ne j} a_{ij} x_i x_j. QP captures many known combinatorial optimization problems, and assuming the unique games conjecture, semidefinite programming techniques give optimal approximation algorithms. We extend this body of work by initiating the study of Quadratic Programming problems where the variables take values in the domain {-1,0,1}. The specific problems we study are QP-Ratio : \max_{\{-1,0,1\}^n} \frac{\sum_{i \not = j} a_{ij} x_i x_j}{\sum x_i^2}, and Normalized QP-Ratio : \max_{\{-1,0,1\}^n} \frac{\sum_{i \not = j} a_{ij} x_i x_j}{\sum d_i x_i^2}, where d_i = \sum_j |a_{ij}|
We consider an SDP relaxation obtained by adding constraints to the natural eigenvalue (or SDP) relaxation for this problem. Using this, we obtain an $\tilde{O}(n^{1/3})$ algorithm for QP-ratio. We also obtain an $\tilde{O}(n^{1/4})$ approximation for bipartite graphs, and better algorithms for special cases. As with other problems with ratio objectives (e.g. uniform sparsest cut), it seems difficult to obtain inapproximability results based on P!=NP. We give two results that indicate that QP-Ratio is hard to approximate to within any constant factor. We also give a natural distribution on instances of QP-Ratio for which an n^\epsilon approximation (for \epsilon roughly 1/10) seems out of reach of current techniques.

Abstract: Given a planar graph with $k$ terminal vertices, the \textsc{Planar Multiway Cut} problem asks for a minimum set of edges whose removal pairwise separates the terminals from each other. A classical algorithm of Dahlhaus et al. solves the problem in time $n^{O(k)}$, which was very recently improved to $2^{O(k)}\cdot n^{O(\sqrt{k})}$ time by Klein and Marx. Here we show the optimality of the latter algorithm: assuming the Exponential Time Hypothesis (ETH), there is no $f(k)\cdot n^{O(\sqrt{k})}$ time algorithm for \textsc{Planar Multiway Cut}. It also follows that the problem is W[1]-hard, answering an open question of Downey and Fellows.

Abstract: We study the k-level uncapacitated facility location problem, where clients need to be connected with paths crossing open facilities of $k$ types (levels). In this paper we give an approximation algorithm that for any constant $k$, in polynomial time, delivers solutions of cost at most $\alpha_k$ times $OPT$, where $\alpha_k$ is an increasing function of $k$, with $\lim_{k\to \infty} \alpha_k = 3$.
Our algorithm rounds a fractional solution to an extended LP formulation of the problem. The rounding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA'98) originally used for the group Steiner tree problem.
We improve the approximation ratio for $k$-UFL for all $k\geq3$, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for $k = 3,4$, and 5.

Abstract: Given a planar graph with $k$ terminal vertices, the Planar Multiway Cut problem asks for a minimum set of edges whose removal pairwise separates the terminals from each other. A classical result of Dahlhaus et al. shows that the problem can be solved in time $n^{O(k)}$. Here we present an algorithm with running time $2^{O(k)} n^{O(\sqrt{k})}$. This matches a recent lower bound of Marx showing that the $O(\sqrt{k})$ term in the exponent is best possible (assuming the Exponential Time Hypothesis).

Abstract: In the online minimum-cost metric matching problem, we are given a metric space with k servers, and have to match arriving requests to as-yet-unmatched servers to minimize the total distance from the requests to their assigned servers. We study this problem for the line metric, and for doubling metrics in general. We give O(log k)-competitive randomized algorithms, which significantly reduces the gap between the current O(log^2 k)-competitive randomized algorithms and the constant-competitive lower bounds known for these settings.
We first analyze the natural Harmonic algorithm for the line, that for each request chooses one of its two closest servers with probability inversely proportional to the distance to that server; we show this is O(log k) competitive (with suitable pre-processing). The proof of this algorithm uses a path-coupling (a.k.a. hybrid argument) approach that might be of interest in itself. The second algorithm proceeds by embedding the metric into a random HST, and then picking randomly from among the closest available servers in the HST; this selection is based upon how the servers are distributed within the tree. This algorithm is O(1)-competitive for the types of HSTs obtained from embedding doubling metrics, and hence implies an O(log k) competitive algorithm for all doubling metrics.

Abstract: The interpolation method, originally developed in statistical physics, transforms distributions of random CSPs to distributions of much simpler problems while bounding the change in a number of associated statistical quantities along the transformation path. After a number of further mathematical developments, it is now known that, in principle, the method can yield rigorous unsatisfiability bounds if one ``plugs in an appropriate functional distribution''. A caveat of the method is that both ``identifying appropriate'' distribution and ``plugging them in" can only be done by non-rigorous stochastic optimization methods. This is because the distributions required are, in fact, infinite dimensional objects that seem beyond analytical penetration. We develop an variant of the interpolation method for random CSPs on arbitrary degree distributions which trades accuracy for numerical tractability. In particular, our bounds only require the solution of a 1-dimensional optimization problem (which typically turns out to be trivial) and as such can be used to compute explicit rigorous unsatisfiability bounds.

Abstract: We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic max (min) polynomial equations,in time polynomial in both the encoding size of the system of equations and in $\log(1/\epsilon)$, where $\epsilon > 0$ is the desired additive error bound of the solution. (The model of computation is the standard Turing machine model.)
These equations form the Bellman optimality equations for several important classes of {\em infinite-state} Markov Decision Processes (MDPs). Thus, as a corollary, we obtain the first polynomial time algorithms for computing to within arbitrary desired precision the {\em optimal value} vector for several classes of infinite-state MDPs which arise as extensions of classic, and heavily studied, purely stochastic processes. These include both the problem of maximizing and mininizing the {\em termination (extinction) probability} of multi-type branching MDPs, stochastic context-free MDPs, and 1-exit Recursive MDPs. We also show that we can compute in P-time an $\epsilon$-optimal policy for any given desired $\epsilon > 0$.

Abstract: We present a general method for de-amortizing essentially any Binary Search Tree (BST) algorithm. In particular, by transforming Splay Trees, our method produces a BST that has the same asymptotic cost as Splay Trees on any access sequence while performing each search in O(log n) worst case time. By transforming Multi-Splay Trees, we obtain a BST that is O(loglog n) competitive, satisfies the scanning theorem, the static optimality theorem, the static finger theorem, the working set theorem, and performs each search in O(log n) worst case time. Moreover, we prove that if there is a dynamically optimal BST algorithm, then there is a dynamically optimal BST algorithm that answers every search in O(log n) worst case time.

Abstract: We study the $k$-party `number on the forehead' communication complexity of composed functions $f \circ g$, where $f:\{0,1\}^n \to \{\pm 1\}$, $g : \{0,1\}^k \to \{0,1\}$ and for $(x_1,\ldots,x_k) \in (\{0,1\}^n)^k$, $f \circ g(x_1,\ldots,x_k) = f(\ldots,g(x_{1,i},\ldots,x_{k,i}), \ldots)$. We show that there is an $O(\log^3 n)$ cost simultaneous protocol for $sym \circ g$ when $k > 1+\log n$, $sym$ is any symmetric function and $g$ is \emph{any function}. Previously, an efficient protocol was only known for $sym \circ g$ when $g$ is symmetric and ``compressible''. We also get a non-simultaneous protocol for $\f{sym} \circ g$ of cost $O(n/2^k \cdot \log n+ k \log n)$ for any $k \geq 2$.
In the setting of $k \leq 1+\log n$, we study more closely functions of the form $majority \circ g$, $mod_m \circ g$, and $nor \circ g$, where the latter two are generalizations of the well-known and studied functions Generalized Inner Product and Disjointness respectively. We characterize the communication complexity of these functions with respect to the choice of $g$. As the main application of our results, we answer a question posed by Babai et al. ({\it SIAM Journal on Computing, 33:137--166, 2004}) and determine the communication complexity of $\f{majority} \circ qcsb_k$, where $qcsb_k$ is the ``quadratic character of the sum of the bits'' function.

Abstract: We study the problem of releasing k-way marginals of a database D ∈ ({0,1}^d)^n, while preserving differential privacy. The answer to a k-way marginal query is the fraction of D’s records x ∈ {0,1}^d with a given value in each of a given set of up to k columns. Marginal queries enable a rich class of statistical analyses of a dataset, and designing efficient algorithms for privately releasing marginal queries has been identified as an important open problem in private data analysis (cf. Barak et. al., PODS ’07).
We give an algorithm that runs in time d^O(sqrt(k)) and releases a private summary capable of answering any k-way marginal query with at most 1% error on every query as long as n ≥ d^O(sqrt(k)). To our knowledge, ours is the first algorithm capable of privately releasing marginal queries with non-trivial worst-case accuracy guarantees in time substantially smaller than the number of k-way marginal queries, which is d^{\Theta(k)} (for k ≪ d).