Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these suboptimal, some cases completely failing detect communities even when other such as belief propagation can do so. Here we introduce a new class spectral based on non-backtracking walk directed edges graph. The spectrum this operator is much better-behaved than that adjacency matrix or commonly used matrices, maintaining strong separation...

In this paper we show a reduction from the Unique Games problem to of approximating MAX‐CUT within factor $\alpha_{\text{\tiny{GW}}} + \epsilon$ for all $\epsilon > 0$; here \approx .878567$ denotes approximation ratio achieved by algorithm Goemans and Williamson in [J. Assoc. Comput. Mach., 42 (1995), pp. 1115–1145]. This implies that if Conjecture Khot [Proceedings 34th Annual ACM Symposium on Theory Computing, 2002, 767–775] holds, then Goemans–Williamson is optimal. Our result indicates...

We study the problem of fairly allocating a set indivisible goods to people from an algorithmic perspective. fair division has been central topic in economic literature and several concepts fairness have suggested. The criterion that we focus on is envy-freeness. In our model, monotone utility function associated with every player specifying value each subset for player. An allocation envy-free if prefers her own share than any other When are divisible, allocations always exist. presence...

In this paper we study functions with low influences on product probability spaces.These are f W 1 n !‫ޒ‬ that have EOEVar i OEf small compared to VarOEf for each .The analysis of boolean 1; 1g !f has become a central problem in discrete Fourier analysis.It is motivated by fundamental questions arising from the construction probabilistically checkable proofs theoretical computer science and problems theory social choice economics.We prove an invariance principle multilinear polynomials...

We prove and extend a conjecture of Kempe, Kleinberg, Tardos (KKT) on the spread influence in social networks.

We introduce a simple computationally efficient algorithm for reconstructing phylogenies from multiple gene trees in the presence of incomplete lineage sorting, that is, when topology may differ species tree. show our technique is statistically consistent under standard stochastic assumptions, it returns correct tree given sufficiently many unlinked loci. also can tolerate moderate estimation errors.

Markov chain Monte Carlo (MCMC) algorithms play a critical role in the Bayesian approach to phylogenetic inference. We present theoretical analysis of rate convergence many widely used chains. For N characters generated from uniform mixture two trees, we prove that chains take an exponentially long (in N) number iterations converge posterior distribution. Nevertheless, likelihood plots for sample runs deceivingly suggest rapidly unique tree. Our results rely on novel mathematical...

In this paper we derive tight bounds on the expected value of products low influence functions defined correlated probability spaces. The proofs are based extending Fourier theory to an arbitrary number spaces, a generalization invariance principle recently obtained with O'Donnell and Oleszkiewicz for multilinear polynomials influences bounded degree properties multi-dimensional Gaussian distributions.

The planted bisection model is a random graph in which the nodes are divided into two equal-sized communities and then edges added randomly way that depends on community membership. We establish necessary sufficient conditions for asymptotic recoverability of this model. When asymptotically recoverable, we give an efficient algorithm successfully recovers it. also show recoverable if only with high probability every node belongs to same as majority its neighbors.

The dynamics of random transitive delegations on a graph are particular interest when viewed through the lens an emerging voting paradigm: liquid democracy. This paradigm allows voters to choose between directly and transitively delegating their votes other so that those selected cast vote weighted by number they received. In epistemic setting, where decide binary issue for which there is ground truth, previous work showed few may amass such large amount influence democracy less likely...

We consider a process in which information is transmitted from given root node on noisy -dary tree network T. start with uniform symbol taken an alphabet \(\mathcal{A}\). Each edge of the independent copy some channel (Markov chain) M, where M irreducible and aperiodic The goal to reconstruct at symbols nth level tree. This model has been studied theory, genetics statistical physics. basic question is: it possible (some on)the root? In other words, does probability correct reconstruction...

Consider a tree network $T$, where each edge acts as an independent copy of given channel $M$, and information is propagated from the root. For which $T$ $M$ does configuration obtained at level $n$ typically contain significant on root variable? This problem arose independently in biology, theory statistical physics. all $b$, we construct for variable break $b$-ary second that tree, yet sufficiently large $B>b$, mutual between $B$-ary bounded away zero $n$. construction related to...

This article provides a new conceptual perspective on survey propagation , which is an iterative algorithm recently introduced by the statistical physics community that very effective in solving random k -SAT problems even with densities close to satisfiability threshold. We first describe how any SAT formula can be associated novel family of Markov fields (MRFs), parameterized real number ρ ∈ [0, 1]. then show applying belief propagation---a well-known “message-passing” technique for...

In this paper, we study functions with low influences on product probability spaces. The analysis of Boolean f {-1, 1}/sup n/ /spl rarr/ 1} has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction probabilistically checkable proofs theoretical computer science and problems theory social choice economics. We prove an invariance principle for multilinear polynomials bounded degree; it shows that under mild conditions...

We apply the theory of Markov random fields on trees to derive a phase transition in number samples needed order reconstruct phylogenies. consider Cavender-Farris-Neyman model evolution trees, where all inner nodes have degree at least $3$, and net each edge is bounded by $\epsilon$. Motivated conjecture M. Steel, we show that if $2 (1 - 2 \epsilon )^2 > 1$, then for balanced topology underlying tree, having $n$ leaves, can be reconstructed from $O(\log n)$ (characters) leaves. On other...

In this paper, we give evidence suggesting that MAX-CUT is NP-hard to approximate within a factor of /spl alpha//sub cw/+ epsi/, for all epsi/ > 0, where cw/ denotes the approximation ratio achieved by Goemans-Williamson algorithm (1995). ap/ .878567. This result conditional, relying on two conjectures: a) unique games conjecture Khot; and, b) very believable call majority stablest conjecture. These results indicate geometric nature might be intrinsic problem. The same conjectures also imply...

We study the AprxColoring$(q,Q)$ problem: Given a graph G, decide whether $\chi(G)\le q$ or $\chi(G)\ge Q$. present hardness results for this problem any constants $3\le q<Q$. For $q\ge4$, our result is based on Khot's 2-to-1 label cover, which conjectured to be NP-hard [S. Khot, Proceedings of 34th Annual ACM Symposium Theory Computing, 2002, pp. 767–775]. $q=3$, we base certain “${\rhd\hskip-0.5em<}$-shaped” variant his conjecture. Previously no was known $q=3$ and $Q\ge6$. At heart proof...