Yuval Peres

Orcid: 0000-0001-5456-6323

According to our database1, Yuval Peres authored at least 105 papers between 1995 and 2022.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2022
Exact Minimum Number of Bits to Stabilize a Linear System.
IEEE Trans. Autom. Control., 2022

2021
Stabilizing a System With an Unbounded Random Gain Using Only Finitely Many Bits.
IEEE Trans. Inf. Theory, 2021

Consensus with Bounded Space and Minimal Communication.
CoRR, 2021

Multiplayer Bandit Learning, from Competition to Cooperation.
Proceedings of the Conference on Learning Theory, 2021

2020
Adversarial Hypothesis Testing and a Quantum Stein's Lemma for Restricted Measurements.
IEEE Trans. Inf. Theory, 2020

Communication cost of consensus for nodes with limited memory.
Proc. Natl. Acad. Sci. USA, 2020

The string of diamonds is nearly tight for rumour spreading.
Comb. Probab. Comput., 2020

Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without.
Proceedings of the Conference on Learning Theory, 2020

2019
Online learning with an almost perfect expert.
Proc. Natl. Acad. Sci. USA, 2019

Perfect Bayesian Equilibria in repeated sales.
Games Econ. Behav., 2019

Optimal Freshness Crawl Under Politeness Constraints.
Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, 2019

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 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. Discret. Math., 2018

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

Tractable near-optimal policies for crawling.
Proc. Natl. Acad. Sci. USA, 2018

Stabilizing a system with an unbounded random gain using only a finite number of bits.
CoRR, 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

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

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
Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling.
Am. Math. Mon., 2017

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

Surprise Probabilities in Markov Chains.
Comb. Probab. Comput., 2017

How fragile are information cascades?
CoRR, 2017

Mixing time estimation in reversible Markov chains from a single sample path.
CoRR, 2017

Trace reconstruction with exp(O(n<sup>1/3</sup>)) 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
The Range of a Rotor Walk.
Am. Math. Mon., 2016

Four random permutations conjugated by an adversary generate <i>S</i><sub>n</sub> with high probability.
Random Struct. Algorithms, 2016

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

When multiplicative noise stymies control.
CoRR, 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

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 Z<sup>d</sup>.
SIAM J. Discret. Math., 2014

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

The looping constant of ℤ<sup>d</sup>.
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.
Comb. Probab. Comput., 2014

Finding Hidden Cliques in Linear Time with High Probability.
Comb. Probab. Comput., 2014

Four Random Permutations Conjugated by an Adversary Generate $S_n$ with High Probability.
CoRR, 2014

Bandits with switching costs: <i>T</i><sup>2/3</sup> regret.
Proceedings of the Symposium on Theory of Computing, 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 <i>O</i>(<i>n</i><sup>2</sup>) time with high probability.
J. ACM, 2013

Separating signal from noise.
CoRR, 2013

Bandits with Switching Costs: T^{2/3} Regret.
CoRR, 2013

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

Mechanisms for Risk Averse Agents, Without Loss
CoRR, 2012

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

The Evolution of the Cover Time.
Comb. Probab. Comput., 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

2010
Pólya's Theorem on Random Walks via Pólya's Urn.
Am. Math. Mon., 2010

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

Diameters in Supercritical Random Graphs Via First Passage Percolation.
Comb. Probab. Comput., 2010

Entropy Rate for Hidden Markov Chains with rare transitions
CoRR, 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(n<sup>2</sup>) Time with High Probability.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Maximum Overhang.
Am. Math. Mon., 2009

A note on a complex Hilbert metric with application to domain of analyticity for entropy rate of hidden Markov processes
CoRR, 2009

Reconstruction on Trees: Exponential Moment Bounds for Linear Estimators.
CoRR, 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
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.
Am. Math. Mon., 2007

On the maximum satisfiability of random formulas.
J. ACM, 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.
Comb. Probab. Comput., 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.
Comb., 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.
Am. Math. Mon., 2003

The Threshold for Random k-SAT is 2<sup>k</sup>ln2 - O(k)
CoRR, 2003

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

The threshold for random k-SAT is 2<sup>k</sup> (ln 2 - O(k)).
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 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 A, 1999

1997
Self-Affine Carpets on the Square Lattice.
Comb. Probab. Comput., 1997

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


  Loading...