Discrete mathematics, computer science and statistical physics have a shared heritage, dating back at least to the birth of modern computing. In recent years, an interdisciplinary area has blossomed at the junction of these fields. Insights from the mathematical and physical sciences have brought significant contributions to solving basic computational challenges. Researchers have successfully applied techniques from the study of phase transitions to analyze NP-complete problems such as satisfiability and graph coloring. This is leading to a new understanding of the structure of these problems, new ways to analyze algorithmic performance, and most excitingly, effective new algorithms. At the same time, computer science has provided significant new perspectives in probability and combinatorics. The study of complex networks has reinvigorated the graph theory community, providing a rich source of new models that aim at capturing the essential structure of real-world data.
This work has been funded by the DOE Laboratory-Directed Research and Development (LDRD) projects DR 2006117 and ER 20030137 at Los Alamos National Laboratory, the NSF award CCF-0829945, and the Air Force Office of Scientific Research MURI award FA9550-10-1-0569.
- B. Nettasinghe, A.G. Percus and K. Lerman, “Dynamics of affective polarization: from consensus to partisan divides,” arXiv:2403.16940 (2024).
- H. Pi, K. Burghardt, A.G. Percus and K. Lerman, “Clique densification in networks,” Physical Review E 107, L042301 (2023). Featured in Research Highlights: Z. Budrikis, “Networks get more cliquey as they grow,” Nature Reviews Physics 5, 442 (2023).
- K.A. Burghardt, Z. He, A.G. Percus and K. Lerman, “The emergence of heterogeneous scaling in research institutions,” Communications Physics 4, 189 (2021).
- S.-C. Ngo, A.G. Percus, K. Burghardt and K. Lerman, “The transsortative structure of networks,” Proceedings of the Royal Society A 476, 20190772 (2020).
- X.-Z. Wu, P.G. Fennell, A.G. Percus and K. Lerman, “Degree correlations amplify the growth of cascades in networks,” Physical Review E 98, 022321 (2018).
- X.-Z. Wu, A.G. Percus and K. Lerman, “Neighbor-neighbor correlations explain measurement bias in networks,” Scientific Reports 7, 5576 (2017).
- M. Bradonjic, T. Müller and A.G. Percus, “Coloring geographical threshold graphs” (full journal version), Discrete Mathematics and Theoretical Computer Science 12, 103-114 (2010).
- M. Bradonjic, A. Hagberg, N.W. Hengartner and A.G. Percus, “Component evolution in general random intersection graphs,” Proceedings of the 7th Workshop on Algorithms and Models for the Web-Graph (WAW2010). Lecture Notes in Computer Science (Springer-Verlag, Berlin, 2010), Vol. 6516, pp. 36-49.
- M. Bradonjic, T. Müller and A.G. Percus, “Coloring geographical threshold graphs,” Proceedings of the Fifth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 09), 11-16 (2009).
- M. Bradonjic, A. Hagberg and A.G. Percus, “The structure of geographical threshold graphs,” Internet Mathematics 5, 113-139 (2008).
- A.G. Percus, G. Istrate, B. Goncalves, R.Z. Sumi and S. Boettcher, “The peculiar phase structure of random graph bisection,” Journal of Mathematical Physics 49, 125219 (2008). Required copyright notice: copyright (2008) American Institute of Physics. This article may be downloaded for personal use only. Any other use requires prior permission of the author and the American Institute of Physics. The official version of the article may be found here.
- M. Bradonjic, A. Hagberg, and A.G. Percus, “Giant component and connectivity in geographical threshold graphs,” Proceedings of the 5th Workshop on Algorithms and Models for the Web-Graph (WAW2007). Lecture Notes in Computer Science (Springer-Verlag, Berlin, 2007), Vol. 4863, pp. 209-216.
- V. Krishnamurthy, M. Faloutsos, M. Chrobak, J.-H. Cui, L. Lao and A.G. Percus, “Sampling large internet topologies for simulation purposes,” Computer Networks 51, 4284-4302 (2007).
- A.G. Percus, G. Istrate and C. Moore, eds., Computational Complexity and Statistical Physics
(Oxford University Press, New York, 2006), including introductory chapter “Where statistical physics meets computation,” pp. 3-24.
- A.G. Percus, G. Istrate, S. Kasiviswanathan, S. Boettcher, N. Hengartner and B. Goncalves, “Belief propagation for graph bisection,” Los Alamos report LA-UR 06-6868 (2006).
- G. Istrate, S. Boettcher and A.G. Percus, “Spines of random constraint satisfaction problems: definition and connection with computational complexity,” Annals of Mathematics and Artificial Intelligence 44, 353-372 (2005).
- V. Krishnamurthy, M. Faloutsos, M. Chrobak, L. Lao, J.-H. Cui and A.G. Percus, “Reducing large internet topologies for faster simulations,” Proceedings of the 4th International IFIP-TC6 Networking Conference (NETWORKING 2005). Lecture Notes in Computer Science (Springer-Verlag, Berlin, 2005), Vol. 3462, pp. 328-341.
- S. Boettcher, G. Istrate and A.G. Percus, “Spines of random constraint satisfaction problems: definition and impact on computational complexity,” Proceedings of the 8th International Symposium on Artificial Intelligence and Mathematics (AIMATH ’04) AI&M 2-2004.