BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Luca Trevisan

Luca Trevisan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingComputational ComplexityDiscrete Mathematicsmath.SPMachine Learningmath.COmath.PRCryptography and Securitymath.MGquant-ph

Catalog footprint

What is connected

26works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

26 published item(s)

preprint2022arXiv

Bond Percolation in Small-World Graphs with Power-Law Distribution

\emph{Full-bond percolation} with parameter $p$ is the process in which, given a graph, for every edge independently, we delete the edge with probability $1-p$. Bond percolation is motivated by problems in mathematical physics and it is studied in parallel computing and network science to understand the resilience of distributed systems to random link failure and the spread of information in networks through unreliable links. Full-bond percolation is also equivalent to the \emph{Reed-Frost process}, a network version of \emph{SIR} epidemic spreading, in which the graph represents contacts among people and $p$ corresponds to the probability that a contact between an infected person and a susceptible one causes a transmission of the infection. We consider \emph{one-dimensional power-law small-world graphs} with parameter $α$ obtained as the union of a cycle with additional long-range random edges: each pair of nodes $(u,v)$ at distance $L$ on the cycle is connected by a long-range edge $(u,v)$, with probability proportional to $1/L^α$. Our analysis determines three phases for the percolation subgraph $G_p$ of the small-world graph, depending on the value of $α$. 1) If $α< 1$, there is a $p<1$ such that, with high probability, there are $Ω(n)$ nodes that are reachable in $G_p$ from one another in $O(\log n)$ hops; 2) If $1 < α< 2$, there is a $p<1$ such that, with high probability, there are $Ω(n)$ nodes that are reachable in $G_p$ from one another in $\log^{O(1)}(n)$ hops; 3) If $α> 2$, for every $p<1$, with high probability all connected components of $G_p$ have size $O(\log n)$. The setting of full-bond percolation in finite graphs studied in this paper, which is the one that corresponds to the network SIR model of epidemic spreading, had not been analyzed before.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Percolation and Epidemic Processes in One-Dimensional Small-World Networks

We obtain tight thresholds for bond percolation on one-dimensional small-world graphs, and apply such results to obtain tight thresholds for the \emph{Independent Cascade} process and the \emph{Reed-Frost} process in such graphs. These are the first fully rigorous results establishing a phase transition for bond percolation and SIR epidemic processes in small-world graphs. Although one-dimensional small-world graphs are an idealized and unrealistic network model, a number of realistic qualitative epidemiological phenomena emerge from our analysis, including the epidemic spread through a sequence of local outbreaks, the danger posed by random connections, and the effect of super-spreader events.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models

Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem in which one is seeking to reconstruct a latent clustering that has been corrupted by random noise and adversarial modifications. Concerning the latter, there is a standard "post-adversarial" model in the literature, in which adversarial modifications come after the noise. Here, we introduce and analyse a "pre-adversarial" model in which adversarial modifications come before the noise. Given an input coming from such a semi-adversarial generative model, the goal is to reconstruct almost perfectly and with high probability the latent clustering. We focus on the case where the hidden clusters have nearly equal size and show the following. In the pre-adversarial setting, spectral algorithms are optimal, in the sense that they reconstruct all the way to the information-theoretic threshold beyond which no reconstruction is possible. This is in contrast to the post-adversarial setting, in which their ability to restore the hidden clusters stops before the threshold, but the gap is optimally filled by SDP-based algorithms. These results highlight a heretofore unknown robustness of spectral algorithms, showing them less brittle than previously thought.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Finding a Bounded-Degree Expander Inside a Dense One

It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Singer conjecture that if $G=(V,E)$ is a $Δ$-regular dense expander then there is an edge-induced subgraph $H=(V,E_H)$ of $G$ of constant maximum degree which is also an expander. As with other consequences of the MSS theorem, it is not clear how one would explicitly construct such a subgraph. We show that such a subgraph (although with quantitatively weaker expansion and near-regularity properties than those predicted by MSS) can be constructed with high probability in linear time, via a simple algorithm. Our algorithm allows a distributed implementation that runs in $\mathcal O(\log n)$ rounds and does $\mathcal O(n)$ total work with high probability. The analysis of the algorithm is complicated by the complex dependencies that arise between edges and between choices made in different rounds. We sidestep these difficulties by following the combinatorial approach of counting the number of possible random choices of the algorithm which lead to failure. We do so by a compression argument showing that such random choices can be encoded with a non-trivial compression. Our algorithm bears some similarity to the way agents construct a communication graph in a peer-to-peer network, and, in the bipartite case, to the way agents select servers in blockchain protocols.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Expansion and Flooding in Dynamic Random Networks with Node Churn

We study expansion and information diffusion in dynamic networks, that is in networks in which nodes and edges are continuously created and destroyed. We consider information diffusion by {\em flooding}, the process by which, once a node is informed, it broadcasts its information to all its neighbors. We study models in which the network is {\em sparse}, meaning that it has $\mathcal{O}(n)$ edges, where $n$ is the number of nodes, and in which edges are created randomly, rather than according to a carefully designed distributed algorithm. In our models, when a node is "born", it connects to $d=\mathcal{O}(1)$ random other nodes. An edge remains alive as long as both its endpoints do. If no further edge creation takes place, we show that, although the network will have $Ω_d(n)$ isolated nodes, it is possible, with large constant probability, to inform a $1-exp(-Ω(d))$ fraction of nodes in $\mathcal{O}(\log n)$ time. Furthermore, the graph exhibits, at any given time, a "large-set expansion" property. We also consider models with {\em edge regeneration}, in which if an edge $(v,w)$ chosen by $v$ at birth goes down because of the death of $w$, the edge is replaced by a fresh random edge $(v,z)$. In models with edge regeneration, we prove that the network is, with high probability, a vertex expander at any given time, and flooding takes $\mathcal{O}(\log n)$ time. The above results hold both for a simple but artificial streaming model of node churn, in which at each time step one node is born and the oldest node dies, and in a more realistic continuous-time model in which the time between births is Poisson and the lifetime of each node follows an exponential distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming

For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming (SDP), to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with few triangles and in $K_r$-free graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Subexponential LPs Approximate Max-Cut

We show that for every $\varepsilon > 0$, the degree-$n^\varepsilon$ Sherali-Adams linear program (with $\exp(\tilde{O}(n^\varepsilon))$ variables and constraints) approximates the maximum cut problem within a factor of $(\frac{1}{2}+\varepsilon')$, for some $\varepsilon'(\varepsilon) > 0$. Our result provides a surprising converse to known lower bounds against all linear programming relaxations of Max-Cut, and hence resolves the extension complexity of approximate Max-Cut for approximation factors close to $\frac{1}{2}$ (up to the function $\varepsilon'(\varepsilon)$). Previously, only semidefinite programs and spectral methods were known to yield approximation factors better than $\frac 12$ for Max-Cut in time $2^{o(n)}$. We also show that constant-degree Sherali-Adams linear programs (with $\text{poly}(n)$ variables and constraints) can solve Max-Cut with approximation factor close to $1$ on graphs of small threshold rank: this is the first connection of which we are aware between threshold rank and linear programming-based algorithms. Our results separate the power of Sherali-Adams versus Lovász-Schrijver hierarchies for approximating Max-Cut, since it is known that $(\frac{1}{2}+\varepsilon)$ approximation of Max Cut requires $Ω_\varepsilon (n)$ rounds in the Lovász-Schrijver hierarchy. We also provide a subexponential time approximation for Khot's Unique Games problem: we show that for every $\varepsilon > 0$ the degree-$(n^\varepsilon \log q)$ Sherali-Adams linear program distinguishes instances of Unique Games of value $\geq 1-\varepsilon'$ from instances of value $\leq \varepsilon'$, for some $\varepsilon'( \varepsilon) >0$, where $q$ is the alphabet size. Such guarantees are qualitatively similar to those of previous subexponential-time algorithms for Unique Games but our algorithm does not rely on semidefinite programming or subspace enumeration techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Find Your Place: Simple Distributed Algorithms for Community Detection

Given an underlying graph, we consider the following \emph{dynamics}: Initially, each node locally chooses a value in $\{-1,1\}$, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Approximation of non-boolean 2CSP

We develop a polynomial time $Ω\left ( \frac 1R \log R \right)$ approximate algorithm for Max 2CSP-$R$, the problem where we are given a collection of constraints, each involving two variables, where each variable ranges over a set of size $R$, and we want to find an assignment to the variables that maximizes the number of satisfied constraints. Assuming the Unique Games Conjecture, this is the best possible approximation up to constant factors. Previously, a $1/R$-approximate algorithm was known, based on linear programming. Our algorithm is based on semidefinite programming (SDP) and on a novel rounding technique. The SDP that we use has an almost-matching integrality gap.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Beating the random assignment on constraint satisfaction problems of bounded degree

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac{1}{2} + Ω(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a \emph{quantum} algorithm to find an assignment satisfying a $\frac{1}{2} + Ω(D^{-3/4})$ fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a $μ+ Ω(1/\sqrt{D})$ fraction of constraints, where $μ$ is the fraction that would be satisfied by a uniformly random assignment.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Near-Optimal UGC-hardness of Approximating Max k-CSP_R

In this paper, we prove an almost-optimal hardness for Max $k$-CSP$_R$ based on Khot's Unique Games Conjecture (UGC). In Max $k$-CSP$_R$, we are given a set of predicates each of which depends on exactly $k$ variables. Each variable can take any value from $1, 2, \dots, R$. The goal is to find an assignment to variables that maximizes the number of satisfied predicates. Assuming the Unique Games Conjecture, we show that it is NP-hard to approximate Max $k$-CSP$_R$ to within factor $2^{O(k \log k)}(\log R)^{k/2}/R^{k - 1}$ for any $k, R$. To the best of our knowledge, this result improves on all the known hardness of approximation results when $3 \leq k = o(\log R/\log \log R)$. In this case, the previous best hardness result was NP-hardness of approximating within a factor $O(k/R^{k-2})$ by Chan. When $k = 2$, our result matches the best known UGC-hardness result of Khot, Kindler, Mossel and O'Donnell. In addition, by extending an algorithm for Max 2-CSP$_R$ by Kindler, Kolla and Trevisan, we provide an $Ω(\log R/R^{k - 1})$-approximation algorithm for Max $k$-CSP$_R$. This algorithm implies that our inapproximability result is tight up to a factor of $2^{O(k \log k)}(\log R)^{k/2 - 1}$. In comparison, when $3 \leq k$ is a constant, the previously known gap was $O(R)$, which is significantly larger than our gap of $O(\text{polylog } R)$. Finally, we show that we can replace the Unique Games Conjecture assumption with Khot's $d$-to-1 Conjecture and still get asymptotically the same hardness of approximation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Quantum lower bound for inverting a permutation with advice

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S \ge \tildeΩ(εN)$ for quantum algorithms that invert a random permutation $f$ on an $ε$ fraction of inputs, where $T$ is the number of queries to $f$ and $S$ is the amount of advice. This answers an open question of De et al. We also give a $Ω(\sqrt{N/m})$ quantum lower bound for the simpler but related Yao's box problem, which is the problem of recovering a bit $x_j$, given the ability to query an $N$-bit string $x$ at any index except the $j$-th, and also given $m$ bits of advice that depend on $x$ but not on $j$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Simple Dynamics for Plurality Consensus

We study a \emph{Plurality-Consensus} process in which each of $n$ anonymous agents of a communication network initially supports an opinion (a color chosen from a finite set $[k]$). Then, in every (synchronous) round, each agent can revise his color according to the opinions currently held by a random sample of his neighbors. It is assumed that the initial color configuration exhibits a sufficiently large \emph{bias} $s$ towards a fixed plurality color, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by $s$ additional nodes. The goal is having the process to converge to the \emph{stable} configuration in which all nodes support the initial plurality. We consider a basic model in which the network is a clique and the update rule (called here the \emph{3-majority dynamics}) of the process is the following: each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly). We prove that the process converges in time $\mathcal{O}( \min\{ k, (n/\log n)^{1/3} \} \, \log n )$ with high probability, provided that $s \geqslant c \sqrt{ \min\{ 2k, (n/\log n)^{1/3} \}\, n \log n}$. We then prove that our upper bound above is tight as long as $k \leqslant (n/\log n)^{1/4}$. This fact implies an exponential time-gap between the plurality-consensus process and the \emph{median} process studied by Doerr et al. in [ACM SPAA'11]. A natural question is whether looking at more (than three) random neighbors can significantly speed up the process. We provide a negative answer to this question: In particular, we show that samples of polylogarithmic size can speed up the process by a polylogarithmic factor only.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Stabilizing Consensus with Many Opinions

We consider the following distributed consensus problem: Each node in a complete communication network of size $n$ initially holds an \emph{opinion}, which is chosen arbitrarily from a finite set $Σ$. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be \emph{valid}, i.e., it should be one among those initially present in the system. This condition should be met even in the presence of an adaptive, malicious adversary who can modify the opinions of a bounded number of nodes in every round. We consider the \emph{3-majority dynamics}: At every round, every node pulls the opinion from three random neighbors and sets his new opinion to the majority one (ties are broken arbitrarily). Let $k$ be the number of valid opinions. We show that, if $k \leqslant n^α$, where $α$ is a suitable positive constant, the 3-majority dynamics converges in time polynomial in $k$ and $\log n$ with high probability even in the presence of an adversary who can affect up to $o(\sqrt{n})$ nodes at each round. Previously, the convergence of the 3-majority protocol was known for $|Σ| = 2$ only, with an argument that is robust to adversarial errors. On the other hand, no anonymous, uniform-gossip protocol that is robust to adversarial errors was known for $|Σ| > 2$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multi-way spectral partitioning and higher-order Cheeger inequalities

A basic fact in spectral graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero. It has been conjectured that an analogous characterization holds for higher multiplicities, i.e., there are $k$ eigenvalues close to zero if and only if the vertex set can be partitioned into $k$ subsets, each defining a sparse cut. We resolve this conjecture. Our result provides a theoretical justification for clustering algorithms that use the bottom $k$ eigenvectors to embed the vertices into $\mathbb R^k$, and then apply geometric considerations to the embedding. We also show that these techniques yield a nearly optimal tradeoff between the expansion of sets of size $\approx n/k$, and the $k$th smallest eigenvalue of the normalized Laplacian matrix, denoted $λ_k$. In particular, we show that in every graph there is a set of size at most $2n/k$ which has expansion at most $O(\sqrt{λ_k \log k})$. This bound is tight, up to constant factors, for the "noisy hypercube" graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Unique Games on the Hypercube

In this paper, we investigate the validity of the Unique Games Conjecture when the constraint graph is the boolean hypercube. We construct an almost optimal integrality gap instance on the Hypercube for the Goemans-Williamson semidefinite program (SDP) for Max-2-LIN$(\mathbb{Z}_2)$. We conjecture that adding triangle inequalities to the SDP provides a polynomial time algorithm to solve Unique Games on the hypercube.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank

We prove a structure theorem for the feasible solutions of the Arora-Rao-Vazirani SDP relaxation on low threshold rank graphs and on small-set expanders. We show that if G is a graph of bounded threshold rank or a small-set expander, then an optimal solution of the Arora-Rao-Vazirani relaxation (or of any stronger version of it) can be almost entirely covered by a small number of balls of bounded radius. Then, we show that, if k is the number of balls, a solution of this form can be rounded with an approximation factor of O(sqrt {log k}) in the case of the Arora-Rao-Vazirani relaxation, and with a constant-factor approximation in the case of the k-th round of the Sherali-Adams hierarchy starting at the Arora-Rao-Vazirani relaxation. The structure theorem and the rounding scheme combine to prove the following result, where G=(V,E) is a graph of expansion ϕ(G), λ_k is the k-th smallest eigenvalue of the normalized Laplacian of G, and ϕ_k(G) = \min_{disjoint S_1,...,S_k} \max_{1 <= i <= k} ϕ(S_i) is the largest expansion of any k disjoint subsets of V: if either λ_k >> log^{2.5} k \cdot phi(G) or ϕ_{k} (G) >> log k \cdot sqrt{log n}\cdot loglog n\cdot ϕ(G), then the Arora-Rao-Vazirani relaxation can be rounded in polynomial time with an approximation ratio O(sqrt{log k}). Stronger approximation guarantees are achievable in time exponential in k via relaxations in the Lasserre hierarchy. Guruswami and Sinop [GS13] and Arora, Ge and Sinop [AGS13] prove that 1+eps approximation is achievable in time 2^{O(k)} poly(n) if either λ_k > ϕ(G)/ poly(eps), or if SSE_{n/k} > sqrt{log k log n} \cdot ϕ(G)/ poly(eps), where SSE_s is the minimal expansion of sets of size at most s.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap

Let ϕ(G) be the minimum conductance of an undirected graph G, and let 0=λ_1 <= λ_2 <=... <= λ_n <= 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k >= 2, ϕ(G) = O(k) λ_2 / \sqrt{λ_k}, and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any k. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if λ_k$ is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?

In the {\em nonuniform sparsest cut} problem, given two undirected graphs $G$ and $H$ over the same set of vertices $V$, we want to find a cut $(S,V-S)$ that minimizes the ratio between the fraction of $G$-edges that are cut and the fraction of $H$-edges that are cut. The ratio (which is at most 1 in an optimal solution) is called the {\em sparsity} of the cut. In the {\em uniform sparsest cut} problem, $H$ is a clique over $V$. If $G$ is regular, it is possible to find a solution to the uniform sparsest cut of cost $O(\sqrt{opt})$ in nearly linear time. Is such an approximation, which we call "Cheege-type" approximation, achievable in the non-uniform case? We show that the answer is negative, assuming the Unique Games Conjecture, for general H. Furthermore, the Leighton-Rao linear programming relaxation and the spectral relaxation fail to find such an approximation even if $H$ is a clique over a subset of vertices. Using semidefinite programming, however, we can find Cheeger-type approximations in polynomial time whenever the adjacency matrix of $H$ has rank 1. (This includes the cases in which $H$ is a clique over a subset of vertices.)

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Partitioning into Expanders

Let G=(V,E) be an undirected graph, lambda_k be the k-th smallest eigenvalue of the normalized laplacian matrix of G. There is a basic fact in algebraic graph theory that lambda_k > 0 if and only if G has at most k-1 connected components. We prove a robust version of this fact. If lambda_k>0, then for some 1\leq \ell\leq k-1, V can be {\em partitioned} into l sets P_1,\ldots,P_l such that each P_i is a low-conductance set in G and induces a high conductance induced subgraph. In particular, ϕ(P_i)=O(l^3\sqrt{λ_l}) and ϕ(G[P_i]) >= λ_k/k^2). We make our results algorithmic by designing a simple polynomial time spectral algorithm to find such partitioning of G with a quadratic loss in the inside conductance of P_i's. Unlike the recent results on higher order Cheeger's inequality [LOT12,LRTV12], our algorithmic results do not use higher order eigenfunctions of G. If there is a sufficiently large gap between lambda_k and lambda_{k+1}, more precisely, if λ_{k+1} >= \poly(k) lambda_{k}^{1/4} then our algorithm finds a k partitioning of V into sets P_1,...,P_k such that the induced subgraph G[P_i] has a significantly larger conductance than the conductance of P_i in G. Such a partitioning may represent the best k clustering of G. Our algorithm is a simple local search that only uses the Spectral Partitioning algorithm as a subroutine. We expect to see further applications of this simple algorithm in clustering applications.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs

Kolla and Tulsiani [KT07,Kolla11} and Arora, Barak and Steurer [ABS10] introduced the technique of subspace enumeration, which gives approximation algorithms for graph problems such as unique games and small set expansion; the running time of such algorithms is exponential in the threshold-rank of the graph. Guruswami and Sinop [GS11,GS12], and Barak, Raghavendra, and Steurer [BRS11] developed an alternative approach to the design of approximation algorithms for graphs of bounded threshold-rank, based on semidefinite programming relaxations in the Lassere hierarchy and on novel rounding techniques. These algorithms are faster than the ones based on subspace enumeration and work on a broad class of problems. In this paper we develop a third approach to the design of such algorithms. We show, constructively, that graphs of bounded threshold-rank satisfy a weak Szemeredi regularity lemma analogous to the one proved by Frieze and Kannan [FK99] for dense graphs. The existence of efficient approximation algorithms is then a consequence of the regularity lemma, as shown by Frieze and Kannan. Applying our method to the Max Cut problem, we devise an algorithm that is faster than all previous algorithms, and is easier to describe and analyze.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Approximating the Expansion Profile and Almost Optimal Local Graph Clustering

Spectral partitioning is a simple, nearly-linear time, algorithm to find sparse cuts, and the Cheeger inequalities provide a worst-case guarantee for the quality of the approximation found by the algorithm. Local graph partitioning algorithms [ST08,ACL06,AP09] run in time that is nearly linear in the size of the output set, and their approximation guarantee is worse than the guarantee provided by the Cheeger inequalities by a polylogarithmic $\log^{Ω(1)} n$ factor. It has been a long standing open problem to design a local graph clustering algorithm with an approximation guarantee close to the guarantee of the Cheeger inequalities and with a running time nearly linear in the size of the output. In this paper we solve this problem; we design an algorithm with the same guarantee (up to a constant factor) as the Cheeger inequality, that runs in time slightly super linear in the size of the output. This is the first sublinear (in the size of the input) time algorithm with almost the same guarantee as the Cheeger's inequality. As a byproduct of our results, we prove a bicriteria approximation algorithm for the expansion profile of any graph. Let $ϕ(γ) = \min_{μ(S) \leq γ}ϕ(S)$. There is a polynomial time algorithm that, for any $γ,ε>0$, finds a set $S$ of measure $μ(S)\leq 2γ^{1+ε}$, and expansion $ϕ(S)\leq \sqrt{2ϕ(γ)/ε}$. Our proof techniques also provide a simpler proof of the structural result of Arora, Barak, Steurer [ABS10], that can be applied to irregular graphs. Our main technical tool is that for any set $S$ of vertices of a graph, a lazy $t$-step random walk started from a randomly chosen vertex of $S$, will remain entirely inside $S$ with probability at least $(1-ϕ(S)/2)^t$. This itself provides a new lower bound to the uniform mixing time of any finite states reversible markov chain.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Better Pseudorandom Generators from Milder Pseudorandom Restrictions

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near-optimal seed-length even in the low-error regime: We get seed-length O(log (n/epsilon)) for error epsilon. Previously, only constructions with seed-length O(\log^{3/2} n) or O(\log^2 n) were known for these classes with polynomially small error. The (pseudo)random restrictions we use are milder than those typically used for proving circuit lower bounds in that we only set a constant fraction of the bits at a time. While such restrictions do not simplify the functions drastically, we show that they can be derandomized using small-bias spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Information Spreading in Dynamic Graphs

We present a general approach to study the flooding time (a measure of how fast information spreads) in dynamic graphs (graphs whose topology changes with time according to a random process). We consider arbitrary converging Markovian dynamic graph process, that is, processes in which the topology of the graph at time $t$ depends only on its topology at time $t-1$ and which have a unique stationary distribution. The most well studied models of dynamic graphs are all Markovian and converging. Under general conditions, we bound the flooding time in terms of the mixing time of the dynamic graph process. We recover, as special cases of our result, bounds on the flooding time for the \emph{random trip} model and the \emph{random path} models; previous analysis techniques provided bounds only in restricted settings for such models. Our result also provides the first bound for the \emph{random waypoint} model (which is tight for certain ranges of parameters) whose analysis had been an important open question.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Higher-Order Cheeger's Inequality

A basic fact in algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue 1 in the normalized adjacency matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to 1. Cheeger's inequality provides an "approximate" version of the latter fact, and it states that a graph has a sparse cut (it is "almost disconnected") if and only if there are at least two eigenvalues that are close to one. It has been conjectured that an analogous characterization holds for higher multiplicities, that is there are $k$ eigenvalues close to 1 if and only if the vertex set can be partitioned into $k$ subsets, each defining a sparse cut. In this paper we resolve this conjecture. Our result provides a theoretical justification for clustering algorithms that use the top $k$ eigenvector to embed the vertices into $\R^k$, and then apply geometric considerations to the embedding.

0 citations0 reviewsNo code linkedOpen access