Yuval Peres

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

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2022

Exact Minimum Number of Bits to Stabilize a Linear System.

Victoria Kostina, Yuval Peres, Gireeja Ranade, Mark Sellke

IEEE Trans. Autom. Control., 2022

2021

Stabilizing a System With an Unbounded Random Gain Using Only Finitely Many Bits.

Victoria Kostina, Yuval Peres, Gireeja Ranade, Mark Sellke

IEEE Trans. Inf. Theory, 2021

Consensus with Bounded Space and Minimal Communication.

Simina Brânzei, Yuval Peres

CoRR, 2021

Multiplayer Bandit Learning, from Competition to Cooperation.

Simina Brânzei, Yuval Peres

Proceedings of the Conference on Learning Theory, 2021

2020

Adversarial Hypothesis Testing and a Quantum Stein's Lemma for Restricted Measurements.

Fernando G. S. L. Brandão, Aram W. Harrow, James R. Lee, Yuval Peres

IEEE Trans. Inf. Theory, 2020

Communication cost of consensus for nodes with limited memory.

Giulia Fanti, Nina Holden, Yuval Peres, Gireeja Ranade

Proc. Natl. Acad. Sci. USA, 2020

The string of diamonds is nearly tight for rumour spreading.

Omer Angel, Abbas Mehrabian, Yuval Peres

Comb. Probab. Comput., 2020

Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without.

Sébastien Bubeck, Yuanzhi Li, Yuval Peres, Mark Sellke

Proceedings of the Conference on Learning Theory, 2020

2019

Online learning with an almost perfect expert.

Simina Brânzei, Yuval Peres

Proc. Natl. Acad. Sci. USA, 2019

Perfect Bayesian Equilibria in repeated sales.

Nikhil R. Devanur, Yuval Peres, Balasubramanian Sivan

Games Econ. Behav., 2019

Optimal Freshness Crawl Under Politeness Constraints.

Andrey Kolobov, Yuval Peres, Eyal Lubetzky, Eric Horvitz

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.

Andrey Kolobov, Yuval Peres, Cheng Lu, Eric Horvitz

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Sorted Top-k in Rounds.

Mark Braverman, Jieming Mao, Yuval Peres

Proceedings of the Conference on Learning Theory, 2019

Random walks on graphs: new bounds on hitting, meeting, coalescing and returning.

Roberto I. Oliveira, Yuval Peres

Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics, 2019

2018

Optimal Control for Diffusions on Graphs.

Laura Florescu, Yuval Peres, Miklós Z. Rácz

SIAM J. Discret. Math., 2018

Sensitivity of Mixing Times in Eulerian Digraphs.

Lucas Boczkowski, Yuval Peres, Perla Sousi

SIAM J. Discret. Math., 2018

Tractable near-optimal policies for crawling.

Yossi Azar, Eric Horvitz, Eyal Lubetzky, Yuval Peres, Dafna Shahaf

Proc. Natl. Acad. Sci. USA, 2018

Stabilizing a system with an unbounded random gain using only a finite number of bits.

Victoria Kostina, Yuval Peres, Gireeja Ranade, Mark Sellke

CoRR, 2018

Exponentially slow mixing in the mean-field Swendsen-Wang dynamics.

Reza Gheissari, Eyal Lubetzky, Yuval Peres

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Estimating graph parameters via random walks with restarts.

Anna Ben-Hamou, Roberto I. Oliveira, Yuval Peres

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Comparing mixing times on sparse random graphs.

Anna Ben-Hamou, Eyal Lubetzky, Yuval Peres

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Testing Graph Clusterability: Algorithms and Lower Bounds.

Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, Yuval Peres

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Subpolynomial trace reconstruction for random strings \{and arbitrary deletion probability.

Nina Holden, Robin Pemantle, Yuval Peres

Proceedings of the Conference On Learning Theory, 2018

Electrostatic Methods for Perfect Matching and Safe Path Planning.

Nak-seung Patrick Hyun, Yuval Peres

Proceedings of the 57th IEEE Conference on Decision and Control, 2018

Trace reconstruction with varying deletion probabilities.

Lisa Hartung, Nina Holden, Yuval Peres

Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics, 2018

2017

Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling.

David A. Levin, Yuval Peres

Am. Math. Mon., 2017

Competing first passage percolation on random regular graphs.

Tonci Antunovic, Yael Dekel, Elchanan Mossel, Yuval Peres

Random Struct. Algorithms, 2017

Surprise Probabilities in Markov Chains.

James Norris, Yuval Peres, Alex Zhai

Comb. Probab. Comput., 2017

How fragile are information cascades?

Yuval Peres, Miklós Z. Rácz, Allan Sly, Izabella Stuhl

CoRR, 2017

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

Daniel J. Hsu, Aryeh Kontorovich, David A. Levin, Yuval Peres, Csaba Szepesvári

CoRR, 2017

Trace reconstruction with exp(O(n^1/3)) samples.

Fedor Nazarov, Yuval Peres

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Local max-cut in smoothed polynomial time.

Omer Angel, Sébastien Bubeck, Yuval Peres, Fan Wei

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Random Walks in Polytopes and Negative Dependence.

Yuval Peres, Mohit Singh, Nisheeth K. Vishnoi

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Tight Lower Bounds for Multiplicative Weights Algorithmic Families.

Nick Gravin, Yuval Peres, Balasubramanian Sivan

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice.

Yuval Peres, Alex Zhai

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Cutoff for a Stratified Random Walk on the Hypercube.

Anna Ben-Hamou, Yuval Peres

Proceedings of the Approximation, 2017

The String of Diamonds Is Tight for Rumor Spreading.

Omer Angel, Abbas Mehrabian, Yuval Peres

Proceedings of the Approximation, 2017

2016

The Range of a Rotor Walk.

Laura Florescu, Lionel Levine, Yuval Peres

Am. Math. Mon., 2016

Four random permutations conjugated by an adversary generate <i>S</i>_n with high probability.

Robin Pemantle, Yuval Peres, Igor Rivin

Random Struct. Algorithms, 2016

Almost Optimal Local Graph Clustering Using Evolving Sets.

Reid Andersen, Shayan Oveis Gharan, Yuval Peres, Luca Trevisan

J. ACM, 2016

When multiplicative noise stymies control.

Jian Ding, Yuval Peres, Gireeja Ranade, Alex Zhai

CoRR, 2016

Towards Optimal Algorithms for Prediction with Expert Advice.

Nick Gravin, Yuval Peres, Balasubramanian Sivan

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

A tiger by the tail: When multiplicative noise stymies control.

Jian Ding, Yuval Peres, Gireeja Ranade

Proceedings of the IEEE International Symposium on Information Theory, 2016

Rate-limited control of systems with uncertain gain.

Victoria Kostina, Yuval Peres, Miklós Z. Rácz, Gireeja Ranade

Proceedings of the 54th Annual Allerton Conference on Communication, 2016

2015

Graphical balanced allocations and the (1 + β)-choice process.

Yuval Peres, Kunal Talwar, Udi Wieder

Random Struct. Algorithms, 2015

Characterization of cutoff for reversible Markov chains.

Riddhipratim Basu, Jonathan Hermon, Yuval Peres

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Approval Voting and Incentives in Crowdsourcing.

Nihar B. Shah, Dengyong Zhou, Yuval Peres

Proceedings of the 32nd International Conference on Machine Learning, 2015

Bandit Convex Optimization: \(\sqrt{T}\) Regret in One Dimension.

Sébastien Bubeck, Ofer Dekel, Tomer Koren, Yuval Peres

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Escape Rates for Rotor Walks in Z^d.

Laura Florescu, Shirshendu Ganguly, Lionel Levine, Yuval Peres

SIAM J. Discret. Math., 2014

Shortest-Weight Paths in Random Regular Graphs.

Hamed Amini, Yuval Peres

SIAM J. Discret. Math., 2014

The looping constant of ℤ^d.

Lionel Levine, Yuval Peres

Random Struct. Algorithms, 2014

Anatomy of the giant component: The strictly supercritical regime.

Jian Ding, Eyal Lubetzky, Yuval Peres

Eur. J. Comb., 2014

Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures.

Robin Pemantle, Yuval Peres

Comb. Probab. Comput., 2014

Finding Hidden Cliques in Linear Time with High Probability.

Yael Dekel, Ori Gurel-Gurevich, Yuval Peres

Comb. Probab. Comput., 2014

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

Robin Pemantle, Yuval Peres, Igor Rivin

CoRR, 2014

Bandits with switching costs: <i>T</i>^2/3 regret.

Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres

Proceedings of the Symposium on Theory of Computing, 2014

Online Learning with Composite Loss Functions.

Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres

Proceedings of The 27th Conference on Learning Theory, 2014

Permuted Random Walk Exits Typically in Linear Time.

Shirshendu Ganguly, Yuval Peres

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.

Anna R. Karlin, C. Thach Nguyen, Yuval Peres

ACM Trans. Economics and Comput., 2013

Noise Tolerance of Expanders and Sublinear Expansion Reconstruction.

Satyen Kale, Yuval Peres, C. Seshadhri

SIAM J. Comput., 2013

All-pairs shortest paths in <i>O</i>(<i>n</i>²) time with high probability.

Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick

J. ACM, 2013

Separating signal from noise.

Nir Lev, Ron Peled, Yuval Peres

CoRR, 2013

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

Ofer Dekel, Jian Ding, Tomer Koren, Yuval Peres

CoRR, 2013

2012

Hitting Times for Random Walks with Restarts.

Svante Janson, Yuval Peres

SIAM J. Discret. Math., 2012

Mechanisms for Risk Averse Agents, Without Loss

Shaddin Dughmi, Yuval Peres

CoRR, 2012

2011

Anatomy of a young giant component in the random graph.

Jian Ding, Jeong Han Kim, Eyal Lubetzky, Yuval Peres

Random Struct. Algorithms, 2011

The Evolution of the Cover Time.

Martin T. Barlow, Jian Ding, Asaf Nachmias, Yuval Peres

Comb. Probab. Comput., 2011

Cover times, blanket times, and majorizing measures.

Jian Ding, James R. Lee, Yuval Peres

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Mobile Geometric Graphs: Detection, Coverage and Percolation.

Yuval Peres, Alistair Sinclair, Perla Sousi, Alexandre Stauffer

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.

David A. Levin, Yuval Peres

Am. Math. Mon., 2010

Critical percolation on random regular graphs.

Asaf Nachmias, Yuval Peres

Random Struct. Algorithms, 2010

Diameters in Supercritical Random Graphs Via First Passage Percolation.

Jian Ding, Jeong Han Kim, Eyal Lubetzky, Yuval Peres

Comb. Probab. Comput., 2010

Entropy Rate for Hidden Markov Chains with rare transitions

Yuval Peres, Anthony Quas

CoRR, 2010

Local Dynamics in Bargaining Networks via Random-Turn Games.

L. Elisa Celis, Nikhil R. Devanur, Yuval Peres

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

The (1 + beta)-Choice Process and Weighted Balls-into-Bins.

Yuval Peres, Kunal Talwar, Udi Wieder

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

All-Pairs Shortest Paths in O(n²) Time with High Probability.

Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Maximum Overhang.

Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick

Am. Math. Mon., 2009

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

Guangyue Han, Brian H. Marcus, Yuval Peres

CoRR, 2009

Reconstruction on Trees: Exponential Moment Bounds for Linear Estimators.

Yuval Peres, Sebastien Roch

CoRR, 2009

Finding sparse cuts locally using evolving sets.

Reid Andersen, Yuval Peres

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

The unreasonable effectiveness of martingales.

Yuval Peres

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks.

Yossi Azar, Benjamin E. Birnbaum, L. Elisa Celis, Nikhil R. Devanur, Yuval Peres

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

The Glauber Dynamics for Colourings of Bounded Degree Trees.

Brendan Lucier, Michael Molloy, Yuval Peres

Proceedings of the Approximation, 2009

Zeros of Gaussian Analytic Functions and Determinantal Point Processes.

J. Ben Hough, Manjunath Krishnapur, Yuval Peres, Bálint Virág

University Lecture Series 51, American Mathematical Society, ISBN: 978-0-8218-4373-4, 2009

2008

Noise Tolerance of Expanders and Sublinear Expander Reconstruction.

Satyen Kale, Yuval Peres, C. Seshadhri

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.

Jeong Han Kim, Ravi Montenegro, Yuval Peres, Prasad Tetali

Proceedings of the Algorithmic Number Theory, 8th International Symposium, 2008

2007

Random-Turn Hex and Other Selection Games.

Yuval Peres, Oded Schramm, Scott Sheffield, David Bruce Wilson

Am. Math. Mon., 2007

On the maximum satisfiability of random formulas.

Dimitris Achlioptas, Assaf Naor, Yuval Peres

J. ACM, 2007

Mixing Time Power Laws at Criticality.

Yun Long, Asaf Nachmias, Yuval Peres

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.

József Balogh, Yuval Peres, Gábor Pete

Comb. Probab. Comput., 2006

Trees and Markov convexity.

James R. Lee, Assaf Naor, Yuval Peres

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

New Coins From Old: Computing With Unknown Bias.

Elchanan Mossel, Yuval Peres

Comb., 2005

2004

Identifying several biased coins encountered by a hidden random walk.

David A. Levin, Yuval Peres

Random Struct. Algorithms, 2004

Shuffling by Semi-Random Transpositions.

Elchanan Mossel, Yuval Peres, Alistair Sinclair

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Fractals with Positive Length and Zero Buffon Needle Probability.

Yuval Peres, Károly Simon, Boris Solomyak

Am. Math. Mon., 2003

The Threshold for Random k-SAT is 2^kln2 - O(k)

Dimitris Achlioptas, Yuval Peres

CoRR, 2003

Evolving sets and mixin.

Ben Morris, Yuval Peres

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

The threshold for random k-SAT is 2^k (ln 2 - O(k)).

Dimitris Achlioptas, Yuval Peres

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.

Dayue Chen, Yuval Peres

Proceedings of the Discrete Random Walks, 2003

2002

Decayed MCMC Filtering.

Bhaskara Marthi, Hanna Pasula, Stuart Russell, Yuval Peres

Proceedings of the UAI '02, 2002

2001

Glauber Dynamics on Trees and Hyperbolic Graphs.

Claire Kenyon, Elchanan Mossel, Yuval Peres

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Percolation in a dependent random environment.

Johan Jonasson, Elchanan Mossel, Yuval Peres

Random Struct. Algorithms, 2000

1999

Resistance Bounds for First-Passage Percolation and Maximum Flow.

Russell Lyons, Robin Pemantle, Yuval Peres

J. Comb. Theory A, 1999

1997

Self-Affine Carpets on the Square Lattice.

Irene Hueter, Yuval Peres

Comb. Probab. Comput., 1997

1995

Fractional Products of Sets.

Ron Blei, Yuval Peres, James H. Schmerl

Random Struct. Algorithms, 1995