Will Perkins

According to our database, Will Perkins authored at least 48 papers between 2010 and 2024.

Collaborative distances:

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

2024

Fast and Perfect Sampling of Subgraphs and Polymer Systems.

Antonio Blanca, Sarah Cannon, Will Perkins

ACM Trans. Algorithms, January, 2024

On the zeroes of hypergraph independence polynomials.

David J. Galvin, Gwen McKinley, Will Perkins, Michail Sarantis, Prasad Tetali

Comb. Probab. Comput., January, 2024

On the hardness of finding balanced independent sets in random bipartite graphs.

Will Perkins, Yuzhou Wang

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Approximation Algorithms for the Random Field Ising Model.

Tyler Helmuth, Holden Lee, Will Perkins, Mohan Ravichandran, Qiang Wu

SIAM J. Discret. Math., September, 2023

Approximately counting independent sets in bipartite graphs via graph containers.

Matthew Jenssen, Will Perkins, Aditya Potukuchi

Random Struct. Algorithms, August, 2023

Efficient sampling and counting algorithms for the Potts model on <i>ℤ</i>^<i>d</i> at all temperatures.

Christian Borgs, Jennifer T. Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali

Random Struct. Algorithms, August, 2023

Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs.

Ewan Davies, Will Perkins

SIAM J. Comput., April, 2023

Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization.

David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Perfect Sampling for Hard Spheres from Strong Spatial Mixing.

Konrad Anand, Andreas Göbel, Marcus Pappik, Will Perkins

Proceedings of the Approximation, 2023

2022

On the number of independent sets in uniform, regular, linear hypergraphs.

Emma Cohen, Will Perkins, Michail Sarantis, Prasad Tetali

Eur. J. Comb., 2022

Independent sets of a given size and structure in the hypercube.

Matthew Jenssen, Will Perkins, Aditya Potukuchi

Comb. Probab. Comput., 2022

Strong spatial mixing for repulsive point processes.

Marcus Michelen, Will Perkins

CoRR, 2022

Approximate counting and sampling via local central limit theorems.

Vishesh Jain, Will Perkins, Ashwin Sah, Mehtaab Sawhney

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Computational thresholds for the fixed-magnetization Ising model.

Charlie Carlson, Ewan Davies, Alexandra Kolla, Will Perkins

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Algorithms and Barriers in the Symmetric Binary Perceptron Model.

David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Fast algorithms at low temperatures via Markov chains.

Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, Eric Vigoda

Random Struct. Algorithms, 2021

A proof of the upper matching conjecture for large graphs.

Ewan Davies, Matthew Jenssen, Will Perkins

J. Comb. Theory, Ser. B, 2021

Frozen 1-RSB structure of the symmetric Ising perceptron.

Will Perkins, Changji Xu

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Algorithms for #BIS-Hard Problems on Expander Graphs.

Matthew Jenssen, Peter Keevash, Will Perkins

SIAM J. Comput., 2020

Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs.

Tyler Helmuth, Matthew Jenssen, Will Perkins

CoRR, 2020

Correlation decay for hard spheres via Markov chains.

Tyler Helmuth, Will Perkins, Samantha Petti

CoRR, 2020

Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures.

Christian Borgs, Jennifer T. Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Counting independent sets in unbalanced bipartite graphs.

Sarah Cannon, Will Perkins

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Efficient sampling and counting algorithms for the Potts model on Z^d at all temperatures.

Christian Borgs, Jennifer T. Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali

CoRR, 2019

Algorithmic Pirogov-Sinai theory.

Tyler Helmuth, Will Perkins, Guus Regts

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

Extremes of the internal energy of the Potts model on cubic graphs.

Ewan Davies, Matthew Jenssen, Will Perkins, Barnaby Roberts

Random Struct. Algorithms, 2018

Counting independent sets in cubic graphs of given girth.

Guillem Perarnau, Will Perkins

J. Comb. Theory, Ser. B, 2018

On the Resilience of Bipartite Networks.

Shelby Heinecke, Will Perkins, Lev Reyzin

Proceedings of the 56th Annual Allerton Conference on Communication, 2018

2017

Independent sets, matchings, and occupancy fractions.

Ewan Davies, Matthew Jenssen, Will Perkins, Barnaby Roberts

J. Lond. Math. Soc., 2017

Tight bounds on the coefficients of partition functions via stability.

Ewan Davies, Matthew Jenssen, Barnaby Roberts, Will Perkins

Electron. Notes Discret. Math., 2017

Limits of discrete distributions and Gibbs measures on random graphs.

Amin Coja-Oghlan, Will Perkins, Kathrin Skubch

Eur. J. Comb., 2017

The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph.

Emma Cohen, Péter Csikvári, Will Perkins, Prasad Tetali

Eur. J. Comb., 2017

On the Widom-Rowlinson Occupancy Fraction in Regular Graphs.

Emma Cohen, Will Perkins, Prasad Tetali

Comb. Probab. Comput., 2017

Information-theoretic thresholds from the cavity method.

Amin Coja-Oghlan, Florent Krzakala, Will Perkins, Lenka Zdeborová

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

2016

Spectral thresholds in the bipartite stochastic block model.

Laura Florescu, Will Perkins

Proceedings of the 29th Conference on Learning Theory, 2016

Belief Propagation on Replica Symmetric Random Factor Graph Models.

Amin Coja-Oghlan, Will Perkins

Proceedings of the Approximation, 2016

2015

Random <i>k</i>-SAT and the power of two choices.

Will Perkins

Random Struct. Algorithms, 2015

Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's.

Vitaly Feldman, Will Perkins, Santosh S. Vempala

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

2014

On the Complexity of Random Satisfiability Problems with Planted Solutions.

Vitaly Feldman, Will Perkins, Santosh S. Vempala

Electron. Colloquium Comput. Complex., 2014

Subsampled Power Iteration: a New Algorithm for Block Models and Planted CSP's.

Vitaly Feldman, Will Perkins, Santosh S. Vempala

CoRR, 2014

On Sharp Thresholds in Random Geometric Graphs.

Milan Bradonjic, Will Perkins

Proceedings of the Approximation, 2014

2013

The forgetfulness of balls and bins.

Will Perkins

Random Struct. Algorithms, 2013

The Bohman-Frieze process near criticality.

Mihyun Kang, Will Perkins, Joel Spencer

Random Struct. Algorithms, 2013

On the Resilience of Bipartite Networks.

Will Perkins, Lev Reyzin

CoRR, 2013

Thresholds for Random Geometric k-SAT.

Milan Bradonjic, Will Perkins

CoRR, 2013

2012

Random k-SAT and the Power of Two Choices

Will Perkins

CoRR, 2012

2011

Computing the confidence levels for a root-mean-square test of goodness-of-fit.

William Perkins, Mark Tygert, Rachel A. Ward

Appl. Math. Comput., 2011

2010

Hardness of Finding Independent Sets in Almost 3-Colorable Graphs.

Irit Dinur, Subhash Khot, Will Perkins, Muli Safra

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