We consider the communication complexity of the graph connectivity problem, where the edges of an n-vertex undirected graph G are distributed between two parties Alice and Bob, who are then required to communicate to determine if G is connected. We show that in any randomized protocol with two-rounds of communication, Alice and Bob must exchange Ω(nlog n) bits; such a lower bound for one-round protocols was shown by Sun and Woodruff (APPROX/RANDOM 2015). A one-round deterministic protocol, where Alice sends O(n log n) bits and Bob determines the answer, was observed by Hajnal, Maass and Turan (STOC 1988); they also showed a matching lower bound of Ω(n log n) bits for deterministic protocols with unbounded rounds of communication. For randomized protocols, a reduction from the set disjointness problem due to Babai, Frankl and Simon (FOCS 1986) implies a randomized lower bound of Ω(n) even with unbounded rounds of communication. Whether this lower bound can be improved to Ω(n log n) has been an outstanding open question, whose algorithmic implications were recently emphasized by Apers, Efron, Gawrychowski, Lee, Mukopadhyay and Nanongkai (FOCS 2022). Our lower bound for randomized two-round protocols is based on a reduction from a restricted version of the two-player pointer chasing problem originally studied by Papadimitriou and Sipser (JCSS 1984). Using this reduction, we show an ω(n) lower bounds on graph connectivity for any constant number of rounds by extending deterministic lower bounds shown by Ponzio, Radhakrishnan and Venkatesh (JCSS 2001) to the randomized setting.

For Affine Control Programs or Static Control Programs (SCoP), symbolic counting of reuse distances could induce polynomials for each reuse pair. These polynomials along with cache capacity constraints lead to non-affine (semi-algebraic) sets; and counting these sets is considered to be a hard problem. The state-of-the-art methods use various exact enumeration techniques relying on existing cardinality algorithms that can efficiently count affine sets. We propose BullsEye , a novel, scalable, accurate, and problem-size independent approximation framework. It is an analytical cache model for fully associative caches with LRU replacement policy focusing on sampling and linearization of non-affine stack distance polynomials. First, we propose a simple domain sampling method that can improve the scalability of exact enumeration. Second, we propose linearization techniques relying on Handelman’s theorem and Bernstein’s representation . To improve the scalability of the Handelman’s theorem linearization technique, we propose template (Interval or Octagon) sub-polyhedral approximations. Our methods obtain significant compile-time improvements with high-accuracy when compared to HayStack on important polyhedral compilation kernels such as nussinov , cholesky , and adi from PolyBench , and harris , gaussianblur from LLVM -TestSuite. Overall, on PolyBench kernels, our methods show up to 3.31× (geomean) speedup with errors below ≈ 0.08% (geomean) for the octagon sub-polyhedral approximation.

In the Euclidean k-Means problem we are given a collection of n points D in an Euclidean space and a positive integer k. Our goal is to identify a collection of k points in the same space (centers) so as to minimize the sum of the squared Euclidean distances between each point in D and the closest center. This problem is known to be APX-hard and the current best approximation ratio is a primal-dual 6.357 approximation based on a standard LP for the problem [Ahmadian et al. FOCS'17, SICOMP'20]. In this note we show how a minor modification of Ahmadian et al.'s analysis leads to a slightly improved 6.12903 approximation. As a related result, we also show that the mentioned LP has integrality gap at least 16+515>1.2157.

Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a 2-partition of the vertex set of the graph that minimizes the considered objective. However, for many natural applications, one might require a graph to be partitioned into k parts, for some k >=slant 2. For a k-partition S_1, ..., S_k of the vertex set of a graph G = (V,E), the k-way edge expansion (resp. vertex expansion) of {S_1, ..., S_k} is defined as max_{i in [k]} Phi(S_i), and the balanced k-way edge expansion (resp. vertex expansion) of G is defined as min_{{S_1, ..., S_k} in P_k} max_{i in [k]} Phi(S_i) , where P_k is the set of all balanced k-partitions of V (i.e each part of a k-partition in P_k should have cardinality |V|/k), and Phi(S) denotes the edge expansion (resp. vertex expansion) of S subset V. We study a natural planted model for graphs where the vertex set of a graph has a k-partition S_1, ..., S_k such that the graph induced on each S_i has large expansion, but each S_i has small edge expansion (resp. vertex expansion) in the graph. We give bi-criteria approximation algorithms for computing the balanced k-way edge expansion (resp. vertex expansion) of instances in this planted model.

The problem of computing the vertex expansion of a graph is an NP-hard problem. The current best worst-case approximation guarantees for computing the vertex expansion of a graph are a $O(\sqrt{\log n})$-approximation algorithm due to Feige, Hajiaghayi and Lee [SIAM J. Comp., 2008], and $O(\sqrt{OPT \log d})$ bound in graphs having vertex degrees at most $d$, due to Louis, Raghavendra and Vempala [FOCS 2013]. We study a natural semi-random model of graphs with sparse vertex cuts. For certain ranges of parameters, we give an algorithm to recover the planted sparse vertex cut exactly. For a larger range of parameters, we give a constant factor bi-criteria approximation algorithm to compute the graph's balanced vertex expansion. Our algorithms are based on studying a semidefinite programming relaxation for the balanced vertex expansion of the graph. In addition to being a family of instances that will help us to better understand the complexity of the computation of vertex expansion, our model can also be used in the study of community detection where only a few nodes from each community interact with nodes from other communities. There has been a lot of work on studying random and semi-random graphs with planted sparse edge cuts. To the best of our knowledge, our model of semi-random graphs with planted sparse vertex cuts has not been studied before.

We consider the problem of embedding a finite set of points $\{x_1, \ldots, x_n\} \in \mathbb{R}^d$ that satisfy $\ell_2^2$ triangle inequalities into $\ell_1$, when the points are approximately low-dimensional. Goemans (unpublished, appears in a work of [Magen and Moharammi, 2008]) showed that such points residing in \emph{exactly} $d$ dimensions can be embedded into $\ell_1$ with distortion at most $\sqrt{d}$. We prove the following robust analogue of this statement: if there exists a $r$-dimensional subspace $Π$ such that the projections onto this subspace satisfy $\sum_{i,j \in [n]}\Vert Πx_i - Πx_j \Vert _2^2 \geq Ω(1) \sum_{i,j \in [n]}\Vert x_i - x_j \Vert _2^2$, then there is an embedding of the points into $\ell_1$ with $O(\sqrt{r})$ average distortion. A consequence of this result is that the integrality gap of the well-known Goemans-Linial SDP relaxation for the Uniform Sparsest Cut problem is $O(\sqrt{r})$ on graphs $G$ whose $r$-th smallest normalized eigenvalue of the Laplacian satisfies $λ_r(G)/n \geq Ω(1)Φ_{SDP} (G)$. Our result improves upon the previously known bound of $O(r)$ on the average distortion, and the integrality gap of the Goemans-Linial SDP under the same preconditions, proven in the previous works of [Deshpande and Venkat, 2014] and [Deshpande, Harsha and Venkat, 2016].

We investigate the value of parallel repetition of one-round games with any number of players k>=2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are *connected* in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.

Goemans showed that any n points x_1,..., x_n in d-dimensions satisfying l_2^2 triangle inequalities can be embedded into l_{1}, with worst-case distortion at most sqrt{d}. We consider an extension of this theorem to the case when the points are approximately low-dimensional as opposed to exactly low-dimensional, and prove the following analogous theorem, albeit with average distortion guarantees: There exists an l_{2}^{2}-to-l_{1} embedding with average distortion at most the stable rank, sr(M), of the matrix M consisting of columns {x_i-x_j}_{i

A recent result of Moshkovitz [Moshkovitz14] presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in [Moshkovitz14] to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel repetition. In this paper, we provide a fix by using a stronger graph that we call fortifiers. Fortifiers are graphs that have both l_1 and l_2 guarantees on induced distributions from large subsets. We then show that an expander with sufficient spectral gap, or a bi-regular extractor with stronger parameters (the latter is also the construction used in an independent update [Moshkovitz15] of [Moshkovitz14] with an alternate argument), is a good fortifier. We also show that using a fortifier (in particular l_2 guarantees) is necessary for obtaining the robustness required for fortification.

Guruswami and Sinop give a $O(1/δ)$ approximation guarantee for the non-uniform Sparsest Cut problem by solving $O(r)$-level Lasserre semidefinite constraints, provided that the generalized eigenvalues of the Laplacians of the cost and demand graphs satisfy a certain spectral condition, namely, $λ_{r+1} \geq Φ^{*}/(1-δ)$. Their key idea is a rounding technique that first maps a vector-valued solution to $[0, 1]$ using appropriately scaled projections onto Lasserre vectors. In this paper, we show that similar projections and analysis can be obtained using only $\ell_{2}^{2}$ triangle inequality constraints. This results in a $O(r/δ^{2})$ approximation guarantee for the non-uniform Sparsest Cut problem by adding only $\ell_{2}^{2}$ triangle inequality constraints to the usual semidefinite program, provided that the same spectral condition, $λ_{r+1} \geq Φ^{*}/(1-δ)$, holds.