Improved analysis of higher order random walks and applications. (English) Zbl 07298321
Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 1198-1211 (2020).
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Ron Aharoni and Eli Berger. The intersection of a matroid and a simplicial complex. Transactions of the American Mathematical Society, 358(11):4895-4917, 2006. · Zbl 1108.05023 |
| [2] | Karim Adiprasito, June Huh, and Eric Katz. Hodge theory for combinatorial geometries. Annals of Mathematics, 188(2):381-452, 2018. · Zbl 1442.14194 |
| [3] | Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, and Madhur Tulsiani. List decoding of direct sum codes. In SODA, 2020. · Zbl 1518.94146 |
| [4] | Vedat Levi Alev, Fernando Granha Jeronimo, and Madhur Tulsiani. Approximating constraint satisfaction problems on high dimensional expanders. In FOCS, 2019. |
| [5] | David Aldous. Random walks on finite groups and rapidly mixing markov chains. In Séminaire de Probabilités XVII 1981/82, pages 243-297. Springer, 1983. · Zbl 0514.60067 |
| [6] | Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model (Manuscript). · Zbl 1522.05449 |
| [7] | Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials ii: high-dimensional walks and an fpras for counting bases of a matroid. In STOC, pages 1-12. ACM, 2019. · Zbl 1433.68606 |
| [8] | Russ Bubley and Martin E. Dyer. Path coupling: A technique for proving rapid mixing in markov chains. In FOCS, pages 223-231, 1997. · Zbl 1321.68378 |
| [9] | Petter Brändén and June Huh. Lorentzian polynomials. arXiv preprint arXiv:1902.03719, 2019. |
| [10] | Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013. · Zbl 0863.15001 |
| [11] | Sergey G Bobkov and Prasad Tetali. Modified logarithmic sobolev inequalities in discrete settings. Journal of Theoretical Probability, 19(2):289-336, 2006. · Zbl 1113.60072 |
| [12] | Mary Cryan, Heng Guo, and Giorgos Mousa. Modified log-sobolev inequalities for strongly log-concave distributions. CoRR, abs/1903.06081, 2019. · Zbl 1478.60200 |
| [13] | Yotam Dikstein and Irit Dinur. Agreement testing theorems on layered set systems. 2019. |
| [14] | Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha. Boolean function analysis on high-dimensional expanders. In APPROX/RANDOM, pages 38:1-38:20, 2018. · Zbl 1522.68739 |
| [15] | Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1-17, 1991. · Zbl 0799.68107 |
| [16] | Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, and Amnon Ta-Shma. List decoding with double samplers. In SODA, pages 2134-2153, 2019. · Zbl 1435.94155 |
| [17] | Irit Dinur and Tali Kaufman. High dimensional expanders imply agreement expanders. In FOCS, pages 974-985, 2017. |
| [18] | Dominic Dotterrer, Tali Kaufman, and Uli Wagner. On expansion and topological overlap. In SOCG, pages 35:1-35:10, 2016. · Zbl 1391.57009 |
| [19] | Persi Diaconis, Laurent Saloff-Coste, et al. Logarithmic sobolev inequalities for finite markov chains. The Annals of Applied Probability, 6(3):695-750, 1996. · Zbl 0867.60043 |
| [20] | Shai Evra and Tali Kaufman. Bounded degree cosystolic expanders of every dimension. In STOC, pages 36-48, 2016. · Zbl 1376.05095 |
| [21] | Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and János Pach. Overlap properties of geometric expanders. In SODA, pages 1188-1197, 2011. · Zbl 1376.05101 |
| [22] | Tom Feder and Milena Mihail. Balanced matroids. In Proceedings of the Twenty Fourth Annual ACM Symposium on the Theory of Computing, pages 26-38. Citeseer, 1992. |
| [23] | Chris Godsil. Mathematics stackexchange url: https://math.stackexchange.com/questions/2527245/what-graph-have-exactly-one-positive-eigenvalue,. |
| [24] | Mikhail Gromov. Singularities, expanders and topology of maps. part 2: From combinatorics to topology via algebraic isoperimetry. Geometric and Functional Analysis, 20(2):416-526, 2010. · Zbl 1251.05039 |
| [25] | Thomas P Hayes. A simple condition implying rapid mixing of single-site dynamics on spin systems. In FOCS, pages 39-46. IEEE, 2006. |
| [26] | Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. · Zbl 1147.68608 |
| [27] | June Huh and Botong Wang. Enumeration of points, lines, planes, etc. Acta Mathematica, 218(2):297-317, 2017. · Zbl 1386.05021 |
| [28] | Mark Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Struct. Algorithms, 7(2):157-166, 1995. · Zbl 0833.60070 |
| [29] | Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149-1178, 1989. · Zbl 0723.05107 |
| [30] | Mark Jerrum, Jung-Bae Son, Prasad Tetali, Eric Vigoda, et al. Elementary bounds on poincaré and log-sobolev constants for decomposable markov chains. The Annals of Applied Probability, 14(4):1741-1765, 2004. · Zbl 1067.60065 |
| [31] | Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51(4):671-697, 2004. · Zbl 1204.65044 |
| [32] | Mark R Jerrum, Leslie G Valiant, and Vijay V Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169-188, 1986. · Zbl 0597.68056 |
| [33] | Tali Kaufman, David Kazhdan, and Alexander Lubotzky. Isoperimetric inequalities for ramanujan complexes and topological expanders. Geometric and Functional Analysis, 26(1):250-287, 2016. · Zbl 1339.05075 |
| [34] | Tali Kaufman and Alexander Lubotzky. High dimensional expanders and property testing. In (ITCS), pages 501-506, 2014. · Zbl 1365.68462 |
| [35] | Tali Kaufman and David Mass. Walking on the edge and cosystolic expansion. CoRR, abs/1606.01844, 2016. |
| [36] | Tali Kaufman and David Mass. High dimensional random walks and colorful expansion. In ITCS, pages 4:1-4:27, 2017. · Zbl 1402.05197 |
| [37] | Tali Kaufman and Izhar Oppenheim. High order random walks: Beyond spectral gap. In APPROX/RANDOM, pages 47:1-47:17, 2018. · Zbl 1522.05451 |
| [38] | Nathan Linial and Roy Meshulam. Homological connectivity of random 2-complexes. Combinatorica, 26(4):475-487, 2006. · Zbl 1121.55013 |
| [39] | Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang. High-dimensional expanders from expanders. CoRR, abs/1907.10771, 2019. · Zbl 1522.05270 |
| [40] | Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Explicit constructions of ramanujan complexes of type. Eur. J. Comb., 26(6):965-993, 2005. · Zbl 1135.05038 |
| [41] | László Lovász and Santosh Vempala. Simulated annealing in convex bodies and an o*(n4) volume algorithm. Journal of Computer and System Sciences, 72(2):392-417, 2006. · Zbl 1090.68112 |
| [42] | Roy Meshulam. The clique complex and hypergraph matching. Combinatorica, 21(1):89-94, 2001. · Zbl 1107.05302 |
| [43] | Ravi Montenegro and Prasad Tetali. Mathematical aspects of mixing times in markov chains. Foundations and Trends in Theoretical Computer Science, 1(3), 2005. · Zbl 1193.68138 |
| [44] | Michael Mitzenmacher and Eli Upfal. Probability and computing - randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. · Zbl 1092.60001 |
| [45] | Milena Mihail and Umesh Vazirani. On the expansion of 0/1 polytopes. Journal of Combinatorial Theory, 1987. |
| [46] | R. Meshulam and N. Wallach. Homological connectivity of random k-dimensional complexes. Random Struct. Algorithms, 34(3):408-417, 2009. · Zbl 1177.55011 |
| [47] | Izhar Oppenheim. Local spectral expansion approach to high dimensional expanders part I: descent of spectral gaps. Discrete & Computational Geometry, 59(2):293-330, 2018. · Zbl 1383.05312 |
| [48] | Ori Parzanchevski, Ron Rosenthal, and Ran J. Tessler. Isoperimetric inequalities in simplicial complexes. Combinatorica, 36(2):195-227, 2016. · Zbl 1389.05174 |
| [49] | Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science & Business Media, 2003. · Zbl 1041.90001 |
| [50] | Alistair Sinclair. Improved bounds for mixing rates of markov chains and multicommodity flow. Combinatorics, probability and Computing, 1(4):351-370, 1992. · Zbl 0801.90039 |
| [51] | Alistair Sinclair. Algorithms for random generation and counting. progress in theoretical computer science, 1993. · Zbl 0780.68096 |
| [52] | Eric Vigoda. Improved bounds for sampling colorings. Journal of Mathematical Physics, 41(3):1555-1569, 2000. · Zbl 0978.60083 |
| [53] | Dror Weitz. Counting independent sets up to the tree threshold. In STOC, pages 140-149. ACM, 2006. · Zbl 1301.68276 |
| [54] | EL Wilmer, David A Levin, and Yuval Peres. Markov chains and mixing times. American Mathematical Soc., Providence, 2009. · Zbl 1160.60001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
