181 citations · 1.5k across the 84 of their papers we have counts for
4 papers · 1 filter
Concentration of Markov chains with bounded moments
Assaf Naor, Shravas Rao, Oded Regev
Let be a finite state stationary Markov chain, and suppose that is a real-valued function on the state space. If is bounded, then Gillman's expande…
The two possible values of the chromatic number of a random graph
Dimitris Achlioptas, Assaf Naor
Given d \in (0,infty) let k_d be the smallest integer k such that d < 2k\log k. We prove that the chromatic number of a random graph G(n,d/n) is either k_d or k_d+1 almost surely.
A probabilistic approach to the geometry of the \ell_p^n-ball
Franck Barthe, Olivier Guedon, Shahar Mendelson +1
This article investigates, by probabilistic methods, various geometric questions on B_p^n, the unit ball of \ell_p^n. We propose realizations in terms of independent random variabl…
On the Maximum Satisfiability of Random Formulas
Dimitris Achlioptas, Assaf Naor, Yuval Peres
Maximum satisfiability is a canonical NP-hard optimization problem that appears empirically hard for random instances. Let us say that a Conjunctive normal form (CNF) formula consi…