Yitong Yin

Yiyao Zhang

CoRR, 2024

A Sampling Lovász Local Lemma for Large Domain Sizes.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Perfect Simulation of Las Vegas Algorithms via Local Computation.

[BibT_eX]

[DOI]

Xinyu Fu

Yonggang Jiang

CoRR, 2023

Correlation decay up to the sampling threshold in the local lemma regime.

[BibT_eX]

[DOI]

CoRR, 2023

Uniqueness and Rapid Mixing in the Bipartite Hardcore Model.

[BibT_eX]

[DOI]

Xiaoyu Chen

Jingcheng Liu

CoRR, 2023

Deterministic counting Lovász local lemma beyond linear programming.

[BibT_eX]

[DOI]

Kun He

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

Uniqueness and Rapid Mixing in the Bipartite Hardcore Model (extended abstract).

[BibT_eX]

[DOI]

Xiaoyu Chen

Jingcheng Liu

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Towards derandomising Markov chain Monte Carlo.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Self-stabilizing $(\varDelta +1)$-Coloring in Sublinear (in $\varDelta $) Rounds via Locally-Iterative Algorithms.

[BibT_eX]

[DOI]

Xinyu Fu

Chaodong Zheng

Proceedings of the Computing and Combinatorics - 29th International Conference, 2023

2022

Rapid Mixing from Spectral Independence beyond the Boolean Domain.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

Perfect sampling from spatial mixing.

[BibT_eX]

[DOI]

Heng Guo

Random Struct. Algorithms, 2022

Locally-iterative (Δ+1)-Coloring in Sublinear (in Δ) Rounds.

[BibT_eX]

[DOI]

Xinyu Fu

Chaodong Zheng

CoRR, 2022

Simple parallel algorithms for single-site dynamics.

[BibT_eX]

[DOI]

Hongyang Liu

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

Polynomial-Time Approximation of Zero-Free Partition Functions.

[BibT_eX]

[DOI]

Penghui Yao

Xinyuan Zhang

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time.

[BibT_eX]

[DOI]

Kun He

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

Optimal mixing for two-state anti-ferromagnetic spin systems.

[BibT_eX]

[DOI]

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

2021

Dynamic Sampling from Graphical Models.

[BibT_eX]

[DOI]

Nisheeth K. Vishnoi

SIAM J. Comput., 2021

Fast Sampling and Counting <i>k</i>-SAT Solutions in the Local Lemma Regime.

[BibT_eX]

[DOI]

J. ACM, 2021

Optimal Mixing Time for the Ising Model in the Uniqueness Regime.

[BibT_eX]

[DOI]

CoRR, 2021

Sampling constraint satisfaction solutions in the local lemma regime.

[BibT_eX]

[DOI]

Kun He

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

Distributed Metropolis Sampler with Optimal Parallelism.

[BibT_eX]

[DOI]

Thomas P. Hayes

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

Dynamic Inference in Probabilistic Graphical Models.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Rapid mixing of Glauber dynamics via spectral independence for all degrees.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

What can be sampled locally?

[BibT_eX]

[DOI]

Yuxin Sun

Distributed Comput., 2020

Fast sampling and counting k-SAT solutions in the local lemma regime.

[BibT_eX]

[DOI]

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

Succinct Filters for Sets of Unknown Sizes.

[BibT_eX]

[DOI]

Mingmou Liu

Huacheng Yu

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Counting hypergraph matchings up to uniqueness threshold.

[BibT_eX]

[DOI]

Renjie Song

Jinman Zhao

Inf. Comput., 2019

Dynamic MCMC Sampling.

[BibT_eX]

[DOI]

CoRR, 2019

Fully-Asynchronous Distributed Metropolis Sampler with Optimal Speedup.

[BibT_eX]

[DOI]

Thomas P. Hayes

CoRR, 2019

2018

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity.

[BibT_eX]

[DOI]

Mingmou Liu

Xiaoyin Pan

ACM Trans. Parallel Comput., 2018

Local Rejection Sampling with Soft Filters.

[BibT_eX]

[DOI]

Yahui Liu

CoRR, 2018

Distributed Symmetry Breaking in Sampling (Optimal Distributed Randomly Coloring with Fewer Colors).

[BibT_eX]

[DOI]

Thomas P. Hayes

CoRR, 2018

On Local Distributed Sampling and Counting.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

2016

Approximating the Partition Function of Two-Spin Systems.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Simple Average-Case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Sampling in Potts Model on Sparse Random Graphs.

[BibT_eX]

[DOI]

Chihao Zhang

Proceedings of the Approximation, 2016

2015

Expander chunked codes.

[BibT_eX]

[DOI]

EURASIP J. Adv. Signal Process., 2015

Spatial mixing and approximate counting for Potts model on graphs with bounded average degree.

[BibT_eX]

[DOI]

Chihao Zhang

CoRR, 2015

Counting hypergraph matchings up to uniqueness threshold.

[BibT_eX]

[DOI]

Jinman Zhao

CoRR, 2015

Spatial mixing and the connective constant: Optimal bounds.

[BibT_eX]

[DOI]

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

2014

Belief propagation for spatial spectrum access games.

[BibT_eX]

[DOI]

Yi-Kai Wang

Sheng Zhong

Proceedings of the Fifteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2014

Approximate capacities of two-dimensional codes by spatial mixing.

[BibT_eX]

[DOI]

Yi-Kai Wang

Sheng Zhong

Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29, 2014

Spatial Mixing of Coloring Random Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Certificates in Data Structures.

[BibT_eX]

[DOI]

Yaoyu Wang

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Approximate Counting via Correlation Decay on Planar Graphs.

[BibT_eX]

[DOI]

Chihao Zhang

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Correlation Decay up to Uniqueness in Spin Systems.

[BibT_eX]

[DOI]

Liang Li

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant.

[BibT_eX]

[DOI]

Alistair Sinclair

Piyush Srivastava

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Improved FPTAS for Multi-spin Systems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Low-contention data structures.

[BibT_eX]

[DOI]

David Eisenstat

J. Parallel Distributed Comput., 2012

Randomized load balancing by joining and splitting bins.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2012

Approximate counting via correlation decay in spin systems.

[BibT_eX]

[DOI]

Liang Li

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Expander graph based overlapped chunked codes.

[BibT_eX]

[DOI]

Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

2010

Cell-Probe Proofs.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2010

Assigning tasks for efficiency in Hadoop: extended abstract.

[BibT_eX]

[DOI]

Michael J. Fischer

Xueyuan Su

Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

2008

Ranged hash functions and the price of churn.

[BibT_eX]

[DOI]

Muli Safra

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

Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Path-independent load balancing with unreliable machines.

[BibT_eX]

[DOI]

Yang Richard Yang