# Yuval Peres

According to our database1, Yuval Peres authored at least 84 papers between 1995 and 2019.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2019
Online learning with an almost perfect expert.
Proc. Natl. Acad. Sci. U.S.A., 2019

Sorted Top-k in Rounds.
Proceedings of the Conference on Learning Theory, 2019

Random walks on graphs: new bounds on hitting, meeting, coalescing and returning.
Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics, 2019

2018
Optimal Control for Diffusions on Graphs.
SIAM J. Discrete Math., 2018

Sensitivity of Mixing Times in Eulerian Digraphs.
SIAM J. Discrete Math., 2018

Tractable near-optimal policies for crawling.
Proc. Natl. Acad. Sci. U.S.A., 2018

Exponentially slow mixing in the mean-field Swendsen-Wang dynamics.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Estimating graph parameters via random walks with restarts.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Comparing mixing times on sparse random graphs.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Stabilizing a System with an Unbounded Random Gain Using Only Finitely Many Bits.
Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

Testing Graph Clusterability: Algorithms and Lower Bounds.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Subpolynomial trace reconstruction for random strings \{and arbitrary deletion probability.
Proceedings of the Conference On Learning Theory, 2018

Exact minimum number of bits to stabilize a linear system.
Proceedings of the 57th IEEE Conference on Decision and Control, 2018

Electrostatic Methods for Perfect Matching and Safe Path Planning.
Proceedings of the 57th IEEE Conference on Decision and Control, 2018

Trace reconstruction with varying deletion probabilities.
Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics, 2018

2017
Competing first passage percolation on random regular graphs.
Random Struct. Algorithms, 2017

Trace reconstruction with exp(O(n1/3)) samples.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Local max-cut in smoothed polynomial time.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Random Walks in Polytopes and Negative Dependence.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Tight Lower Bounds for Multiplicative Weights Algorithmic Families.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Cutoff for a Stratified Random Walk on the Hypercube.
Proceedings of the Approximation, 2017

The String of Diamonds Is Tight for Rumor Spreading.
Proceedings of the Approximation, 2017

2016
Four random permutations conjugated by an adversary generate Sn with high probability.
Random Struct. Algorithms, 2016

Almost Optimal Local Graph Clustering Using Evolving Sets.
J. ACM, 2016

Towards Optimal Algorithms for Prediction with Expert Advice.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

A tiger by the tail: When multiplicative noise stymies control.
Proceedings of the IEEE International Symposium on Information Theory, 2016

Rate-limited control of systems with uncertain gain.
Proceedings of the 54th Annual Allerton Conference on Communication, 2016

2015
Graphical balanced allocations and the (1 + β)-choice process.
Random Struct. Algorithms, 2015

Surprise probabilities in Markov chains.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Perfect Bayesian Equilibria in Repeated Sales.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Characterization of cutoff for reversible Markov chains.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Approval Voting and Incentives in Crowdsourcing.
Proceedings of the 32nd International Conference on Machine Learning, 2015

Bandit Convex Optimization: $$\sqrt{T}$$ Regret in One Dimension.
Proceedings of The 28th Conference on Learning Theory, 2015

2014
Escape Rates for Rotor Walks in Zd.
SIAM J. Discrete Math., 2014

Shortest-Weight Paths in Random Regular Graphs.
SIAM J. Discrete Math., 2014

The looping constant of ℤd.
Random Struct. Algorithms, 2014

Anatomy of the giant component: The strictly supercritical regime.
Eur. J. Comb., 2014

Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures.
Combinatorics, Probability & Computing, 2014

Bandits with switching costs: T2/3 regret.
Proceedings of the Symposium on Theory of Computing, 2014

Adversarial hypothesis testing and a quantum stein's lemma for restricted measurements.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Online Learning with Composite Loss Functions.
Proceedings of The 27th Conference on Learning Theory, 2014

Permuted Random Walk Exits Typically in Linear Time.
Proceedings of the 2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics, 2014

2013
Selling in Exclusive Markets: Some Observations on Prior-Free Mechanism Design.
ACM Trans. Economics and Comput., 2013

Noise Tolerance of Expanders and Sublinear Expansion Reconstruction.
SIAM J. Comput., 2013

All-pairs shortest paths in O(n2) time with high probability.
J. ACM, 2013

2012
Hitting Times for Random Walks with Restarts.
SIAM J. Discrete Math., 2012

2011
Anatomy of a young giant component in the random graph.
Random Struct. Algorithms, 2011

The Evolution of the Cover Time.
Combinatorics, Probability & Computing, 2011

Cover times, blanket times, and majorizing measures.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Mobile Geometric Graphs: Detection, Coverage and Percolation.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Finding Hidden Cliques in Linear Time with High Probability.
Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics, 2011

2010
Pólya's Theorem on Random Walks via Pólya's Urn.
The American Mathematical Monthly, 2010

Critical percolation on random regular graphs.
Random Struct. Algorithms, 2010

Diameters in Supercritical Random Graphs Via First Passage Percolation.
Combinatorics, Probability & Computing, 2010

Local Dynamics in Bargaining Networks via Random-Turn Games.
Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

The (1 + beta)-Choice Process and Weighted Balls-into-Bins.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

All-Pairs Shortest Paths in O(n2) Time with High Probability.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Finding sparse cuts locally using evolving sets.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

The unreasonable effectiveness of martingales.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

The Glauber Dynamics for Colourings of Bounded Degree Trees.
Proceedings of the Approximation, 2009

Zeros of Gaussian Analytic Functions and Determinantal Point Processes.
University Lecture Series 51, American Mathematical Society, ISBN: 978-0-8218-4373-4, 2009

2008
Maximum overhang.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Noise Tolerance of Expanders and Sublinear Expander Reconstruction.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

A Birthday Paradox for Markov Chains, with an Optimal Bound for Collision in the Pollard Rho Algorithm for Discrete Logarithm.
Proceedings of the Algorithmic Number Theory, 8th International Symposium, 2008

2007
Random-Turn Hex and Other Selection Games.
The American Mathematical Monthly, 2007

Mixing Time Power Laws at Criticality.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006
Bootstrap Percolation on Infinite Trees and Non-Amenable Groups.
Combinatorics, Probability & Computing, 2006

Trees and Markov convexity.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005
New Coins From Old: Computing With Unknown Bias.
Combinatorica, 2005

2004
Identifying several biased coins encountered by a hidden random walk.
Random Struct. Algorithms, 2004

Shuffling by Semi-Random Transpositions.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Fractals with Positive Length and Zero Buffon Needle Probability.
The American Mathematical Monthly, 2003

Evolving sets and mixin.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

The threshold for random k-SAT is 2k (ln 2 - O(k)).
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

On the Maximum Satisfiability of Random Formulas.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

The Speed of Simple Random Walk and Anchored Expansion on Percolation Clusters: an Overview.
Proceedings of the Discrete Random Walks, 2003

2002
Decayed MCMC Filtering.
Proceedings of the UAI '02, 2002

2001
Glauber Dynamics on Trees and Hyperbolic Graphs.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
Percolation in a dependent random environment.
Random Struct. Algorithms, 2000

1999
Resistance Bounds for First-Passage Percolation and Maximum Flow.
J. Comb. Theory, Ser. A, 1999

1997
Self-Affine Carpets on the Square Lattice.
Combinatorics, Probability & Computing, 1997

1995
Fractional Products of Sets.
Random Struct. Algorithms, 1995