Institute of Mathematical Sciences

Claremont Graduate University

710 N. College Ave.

Claremont, CA 91711

Tel: 909-607-0744 / Fax: 909-607-8261

https://scholar.cgu.edu/allon-percus/

**Research Interests:**

- Discrete optimization
- Statistical physics of algorithms and networks
- Random combinatorial structures
- Computational complexity

**Education:**

- Université Paris-Sud, Orsay: PhD in theoretical physics

Thesis topic:*The Traveling Salesman and Related Stochastic Problems*

September 1997 - École Normale Supérieure, Paris: DEA (MS equivalent) in theoretical physics

September 1994 - Harvard University: BA in physics

June 1992

**Regular Appointments:**

- Professor, Institute of Mathematical Sciences, Claremont Graduate University

July 2016 – present - Associate Professor, Institute of Mathematical Sciences, Claremont Graduate University

January 2009 – June 2016 - Member of the Technical Staff, Information Sciences Group, Los Alamos National Laboratory

June 2000 – December 2008

**Adjunct and Visiting Appointments:**

- Adjunct Faculty, Computational Science Research Center, San Diego State University

August 2009 – present - Visiting Associate Researcher, Department of Mathematics, University of California, Los Angeles

July 2009 – August 2012 - Visiting Researcher, New Mexico Consortium

September 2008 – August 2012 - Visiting Associate Professor, Department of Mathematics, University of California, Los Angeles

July 2006 – October 2008 - Associate Director, Institute for Pure and Applied Mathematics, University of California, Los Angeles

July 2003 – June 2006 - Associate Adjunct Professor, Department of Computer Science and Engineering, University of California, Riverside

December 2002 – October 2005 - Postdoctoral Research Associate, Center for Nonlinear Studies and Computer Research & Applications Group, Los Alamos National Laboratory

October 1997 – June 2000

**Book:**

- 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.

**Published Papers:**

- X.-Z. Wu, A.G. Percus and K. Lerman, “Neighbor-neighbor correlations explain measurement bias in networks,”
*Scientific Reports*,**7**, 5576 (2017). - L.M. Smith, L. Zhu, K. Lerman and A.G. Percus, “Partitioning networks with node attributes by compressing information flow,”
*ACM Transactions on Knowledge Discovery from Data*,**11**, 15 (2016). - C. Garcia-Cardona, A. Flenner and A.G. Percus, “Multiclass semi-supervised learning on graphs using Ginzburg-Landau functional minimization,”
*Advances in Intelligent Systems and Computing*,**318**, 119-135 (2015). - A. Ma, A. Flenner, D. Needell and A.G. Percus, “Improving image clustering using sparse text and the wisdom of the crowds,”
*Proceedings of the 48th Annual Asilomar Conference on Signals, Systems, and Computers*, 1555-1557 (2014). - C. Garcia-Cardona, E. Merkurjev, A.L. Bertozzi, A. Flenner and A.G. Percus, “Multiclass data segmentation using diffuse interface methods on graphs,”
*IEEE Transactions on Pattern Analysis and Machine Intelligence,***36**, 1600-1613 (2014). - E. Merkurjev, C. Garcia-Cardona, A.L. Bertozzi, A. Flenner and A.G. Percus, “Diffuse interface methods for multiclass segmentation of high-dimensional data,”
*Applied Mathematics Letters*,**33**, 29-34 (2014). - L.M. Smith, K. Lerman, C. Garcia-Cardona, A.G. Percus and R. Ghosh, “Spectral clustering with epidemic diffusion,”
*Physical Review E*,**88**, 042813 (2013). - C. Garcia-Cardona, A. Flenner and A.G. Percus, “Multiclass diffuse interface models for semi-supervised learning on graphs,”
*Proceedings of the 2nd International Conference on Pattern Recognition Applications and Methods (ICPRAM 2013)*, 78-86 (2013). - M. Keeter, D. Moore, R. Muller, E. Nieters, J. Flenner, S.E. Martonosi, A.L. Bertozzi, A.G. Percus and R. Levy, “Cooperative search with autonomous vehicles in a 3D aquatic testbed,”
*Proceedings of the 2012 American Control Conference (ACC 2012)*, 3154-3160 (2012). - 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. - S. Eidenbenz, G. Ercal-Ozkaya, A. Meyerson, A. Percus and S. Varatharajan, “Incentive compatible and globally efficient position based routing for selfish reverse multicast in wireless sensor networks,”
*Algorithms***2**, 1303-1326 (2009). - G. Ercal-Ozkaya, S. Eidenbenz, A. Meyerson and A. Percus, “On a locally minimum cost forwarding game,”
*Proceedings of the Second ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing (FOWANC 2009)*, 29-36 (2009). - C. Wang, J.D. Hyman, A.G. Percus and R. Caflisch, “Parallel tempering for the traveling salesman problem,”
*International Journal of Modern Physics C***20**, 539-556 (2009). - M. Bradonjic, T. Müller and A.G. Percus, “Coloring geographical threshold graphs” (extended abstract),
*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). - S. Boettcher and A. Percus, “Optimizing glasses with extremal dynamics,”
*Proceedings of the 17th Workshop on Computer Simulation Studies in Condensed-Matter Physics*. Springer Proceedings in Physics (Springer, Berlin, 2006), Vol. 103, pp. 74-79. - 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 and A.G. Percus, “Extremal optimization at the phase transition of the 3-coloring problem,”
*Physical Review E***69**, 066703 (2004). - 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. - D. Aldous and A.G. Percus, “Scaling and universality in continuous length combinatorial optimization,”
*Proceedings of the National Academy of Sciences***100**, 11211-11215 (2003). - S. Boettcher and A.G. Percus, “Optimization with extremal dynamics,”
*Complexity***8**, 57-62 (2003). - S. Boettcher and A.G. Percus, “Extremal optimization: an evolutionary local-search algorithm,” in: H.K. Bhargava and N. Ye, eds.,
*Computational Modeling and Problem Solving in the Networked World: Interfaces in Computer Science and Operations Research*(Kluwer Academic Publishers, Dordrecht, Netherlands, 2003), pp. 61-77. - C.M. Brislawn, B.E. Wohlberg and A.G. Percus, “Resolution scability for arbitrary wavelet transforms in the JPEG-2000 standard”, in: T. Ebrahimi and T. Sikora, eds.,
*Visual Communications and Image Processing, Proceedings of SPIE***5150**, 774-784 (2003). - S. Boettcher and A.G. Percus, “Optimization with extremal dynamics,”
*Physical Review Letters***86**, 5211-5214 (2001). - S. Boettcher and A.G. Percus, “Extremal optimization for graph partitioning,”
*Physical Review E***64**, 026114 (2001). - S. Boettcher and A.G. Percus, “Nature’s way of optimizing,”
*Artificial Intelligence***119**, 275-286 (2000). - S. Boettcher and A.G. Percus, “Combining local search with co-evolution in a remarkably simple way,”
*Proceedings of the 2000 Congress on Evolutionary Computation*, 1578-1584 (2000). - S. Boettcher, A.G. Percus and M. Grigni, “Optimizing through co-evolutionary avalanches,”
*Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature*, 447-456 (2000). - E. Czabarka, G. Konjevod, M.V. Marathe, A.G. Percus and D.C. Torney, “Algorithms for optimizing production DNA sequencing,”
*Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’00)*, 399-408 (2000). - S. Boettcher and A.G. Percus, “Extremal optimization: Methods derived from co-evolution,”
*Proceedings of the 1999 Genetic and Evolutionary Computation Conference (GECCO ’99)*, 825-832 (1999). - A.G. Percus and O.C. Martin, “The stochastic traveling salesman problem: Finite size scaling and the cavity prediction,”
*Journal of Statistical Physics***94**, 739-758 (1999). - A.G. Percus and D.C. Torney, “Greedy algorithms for optimized DNA sequencing,”
*Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’99)*, S955-S956 (1999). - A.G. Percus and O.C. Martin, “Scaling universalities of
*k*th-nearest neighbor distances on closed manifolds,”*Advances in Applied Mathematics***21**, 424-436 (1998). - N.J. Cerf, J. Boutet de Monvel, O. Bohigas, O.C. Martin and A.G. Percus, “The random link approximation for the Euclidean traveling salesman problem,”
*Journal de Physique I***7**, 117-136 (1997). - A.G. Percus and O.C. Martin, “Finite size and dimensional dependence of the Euclidean traveling salesman problem,”
*Physical Review Letters***76**, 1188-1191 (1996). - H.M. Lacker and A. Percus, “How do ovarian follicles interact? A many-body problem with unusual symmetry and symmetry-breaking properties,”
*Journal of Statistical Physics***63**, 1133-1161 (1991).

**Book Review:**

- A.G. Percus, review of: D.P. Landau and K. Binder,
*A Guide to Monte Carlo Simulations in Statistical Physics (3rd ed.)*,*The American Statistician***65:2**, 137-138 (May 2011).

**Preprints and Technical Reports:**

- M. Valera, Z. Guo, P. Kelly, S. Matz, A. Cantu, A.G. Percus, J.D. Hyman, G. Srinivasan and H.S. Viswanathan, “Machine learning for graph-based representations of three-dimensional discrete fracture networks,” arXiv:1705.09866 (2017).
- J. Sunu and A.G. Percus, “Dimensionality reduction for acoustic vehicle classification with spectral clustering,” arXiv:1705.09869 (2017).
- M. Bradonjic, A. Hagberg, N.W. Hengartner, N. Lemons and A.G. Percus, “The phase transition in inhomogeneous random intersection graphs,” arXiv:1301.7320 (2013).
- A.G. Percus, “The traveling salesman problem and kth-nearest neighbors,” Los Alamos report LA-UR 06-6896 (2006).
- 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).

**Funding:**

- PI, Los Alamos National Laboratory subcontract
*Mathematics Clinic: Machine Learning Algorithms for Graph-Based Representations of Fracture Networks*(total budget: $60K)

September 2016 – May 2017 - PI, Southern California Edison contract
*Mathematics Clinic: Predicting and Minimizing Volatility in Power Outages*(total budget: $60K)

September 2015 – May 2016 - Co-PI, Air Force Office of Scientific Research MURI award
*Inferring Structure and Forecasting Dynamics on Evolving Networks*(total budget: $538K)

October 2010 – September 2015 - PI, Southern California Edison contract
*Mathematics Clinic: Topological Optimization of Reliability Volatility in Power Distribution Networks*(total budget: $60K)

September 2014 – May 2015 - Co-PI, DOE/ASCR award
*Dynamics through Randomness: New Mathematical Approaches for Complex Networks*(total budget: $936K)

January 2010 – September 2013 - Co-PI, Office of Naval Research award
*Mathematics of Communication and Control for Dynamic Mobile Aquatic Sensors*(total budget: $165K)

April 2010 – September 2012 - Co-PI, NSF EMT award
*Harnessing Statistical Physics for Computing and Communications*(total budget: $388K)

September 2008 – August 2012 - PI, Southern California Edison contract
*Mathematics Clinic: Optimizing Transmission of Renewable Energy*(total budget: $60K)

September 2011 – May 2012 - PI, Computing Research Association award
*CI Fellows*(total budget: $193K)

January 2011 – May 2012 - PI, Los Alamos National Laboratory subcontract
*Mathematics Clinic: Optimizing Smart Power Grids*(total budget: $90K)

September 2009 – May 2011 - Senior Personnel, NSF award
*Institute for Pure and Applied Mathematics renewal*(total budget: $17M)

July 2005 – June 2010 - Co-PI, DOE Laboratory-Directed Research and Development (LDRD) Directed Research project
*Physics of Algorithms*(total budget: $4.9M)

October 2006 – September 2009 - PI, DOE Weapons Supported Research (WSR) Computer Science Research Foundation project
*New Approaches to Fault Tolerance*(total budget: $232K)

October 2005 – September 2006 - Co-PI, DOE Laboratory-Directed Research and Development (LDRD) Directed Research project
*Statistical Physics of Infrastructure Networks*(total budget: $4.5M)

October 2003 – September 2006 - PI, DOE Laboratory-Directed Research and Development (LDRD) Exploratory Research project
*Improving Local Search*(total budget: $840K)

October 2002 – September 2005 - Co-PI, NSF ACT award
*Intelligent Extraction of Information from Graphs and High-Dimensional Data*(total budget: $200K)

July 2005 - Co-PI, DOE Laboratory-Directed Research and Development (LDRD) Exploratory Research project
*Extremal Optimization*(total budget: $320K)

October 1999 – September 2002 - Co-PI, DOE Laboratory-Directed Research and Development (LDRD) Exploratory Research project
*Combinatorial Optimization in Biology*(total budget: $320K)

October 1999 – September 2002

**NOTE:**The Los Alamos LDRD program is the primary means of supporting basic research at LANL, which as a DOE laboratory is not eligible for NSF funding. Projects are selected by a peer-reviewed competition with a success rate of 10-20%.

**Teaching:**

- Math 164/264: Scientific Computing

Harvey Mudd College/Claremont Graduate University, Spring 2017 - Math 293-393: Mathematics Clinic

Claremont Graduate University, Fall 2016 – Spring 2017 - Math 387: Discrete Mathematical Modeling

Claremont Graduate University, Fall 2016 - Math 293-393: Mathematics Clinic

Claremont Graduate University, Fall 2015 – Spring 2016 - Math 293-393: Mathematics Clinic

Claremont Graduate University, Fall 2014 – Spring 2015 - Math 451: Statistical Mechanics and Lattice Models

Claremont Graduate University, Spring 2014 - Math 392: Mathematics Clinic

Claremont Graduate University, Fall 2013 - Math 389: Discrete Mathematical Modeling

Claremont Graduate University, Spring 2013 - Math 389: Discrete Mathematical Modeling

Claremont Graduate University, Spring 2012 - Math 392-393: Mathematics Clinic

Claremont Graduate University, Fall 2011 – Spring 2012 - Math 251: Probability

Claremont Graduate University, Fall 2011 - Math 164/264: Scientific Computing

Harvey Mudd College/Claremont Graduate University, Spring 2011 - Math 392-393: Mathematics Clinic

Claremont Graduate University, Fall 2010 – Spring 2011 - Math 451: Statistical Mechanics

Claremont Graduate University, Fall 2010 - Math 164/264: Scientific Computing

Harvey Mudd College/Claremont Graduate University, Spring 2010 - Math 392-393: Mathematics Clinic

Claremont Graduate University, Fall 2009 – Spring 2010 - Math 389: Discrete Mathematical Modeling

Claremont Graduate University, Fall 2009 - Math 251: Probability

Claremont Graduate University, Fall 2009 - Math 473: Combinatorial Optimization and Discrete Algorithms

Claremont Graduate University, Spring 2009 - Math 164/264: Scientific Computing

Harvey Mudd College/Claremont Graduate University, Spring 2009 - Math 290J: Discrete Algorithms and Phase Transitions

UCLA, Fall 2006 – Spring 2007 - CS 260: Monte Carlo Algorithms

UC Riverside, Spring 2003 - CS 260: Heuristic Methods in Optimization

UC Riverside, Winter 2003 - Industry Mentor for RIPS undergraduate research project at IPAM: Improving the Performance of Local Search Heuristics

UCLA, Summer 2002

**PhD Committees:**

- William Spinella

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2017 - Jennifer Flenner

CGU Mathematics, PhD 2017 - Deng Zhou

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2016 - Shaher Abdallah

CGU/CSULB Joint Doctoral Program in Engineering and Industrial Applied Mathematics, PhD 2016 - Martin Kandes

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2015 - Mariangel Garcia

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2015 - Daniel Herrlin

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2015 - Peng Zhao

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2015 - Omair Zubairi

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2015 - Micah Schuster

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2015 - Mark Wilson

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2015 - Gene Ko

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2015 - Melodie Hallett

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2015 - Xun Sun

CGU Mathematics, PhD 2015 - Wei Wang

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2015 - David Heckman

CGU Mathematics, PhD 2015 - Mohammad Abouali

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2014 - Nicolas Chaumont

CGU/KGI Joint Doctoral Program in Computational and Systems Biology, PhD 2014 - Mary Thomas

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2014 - Cristina Garcia-Cardona

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2013**(committee chair)** - Jonathan Wilson

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2013 - Dany De Cecchis

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2012 - Sara Zarei

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2012 - Rafael Navarro

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2012 - Ron Caplan

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2012 - Joris Billen

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2012 - Sammuel Jalali

CGU/CSULB Joint Doctoral Program in Engineering and Industrial Applied Mathematics, PhD 2012 - Justin Ku

CGU Information Systems and Technology, PhD 2012 - Dwayne Chambers

CGU Mathematics, PhD 2011 - Michael Vodhanel

CGU Mathematics, PhD 2011 - Todd Coburn

CGU/CSULB Joint Doctoral Program in Engineering and Industrial Applied Mathematics, PhD 2010 - Hai Ah Nam

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2010 - Rodrigo Negreiros

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2009 - Kun Marhadi

CGU/SDSU Joint Doctoral Program in Computational Science, PhD 2009 - Milan Bradonjic

UCLA Electrical Engineering, PhD 2008*(committee chair)* - Gunes Ercal

UCLA Computer Science, PhD 2008

**Professional Service and Distinctions:**

- Director, CGU Engineering and Industrial Applied Mathematics Clinic

July 2010 – present - Avery Fellow, Claremont Graduate University and Harvey Mudd College

January 2009 – June 2011, January 2017 – June 2018 - Society for Industrial and Applied Mathematics (SIAM) Committee on Gene Golub SIAM Summer School

October 2013 – September 2017 - Director, Institute of Mathematical Sciences, Claremont Graduate University

July 2013 – June 2015 - CGU Task Committee for Faculty Review of Provost

January 2014 – May 2014 - Program Committee, 2013 Workshop on Algorithms and Models for the Web Graph
- Program Committee, 2012 Workshop on Algorithms and Models for the Web Graph
- Organizing Committee,
*Algorithmic Game Theory*workshop, Institute for Pure and Applied Mathematics, University of California, Los Angeles

January 2011 - CGU Faculty Executive Committee

August 2009 – December 2009 - Organizing Committee,
*Physics of Algorithms*workshop, Santa Fe, New Mexico

September 2009 - Review Panel, DOE Office of Nonproliferation Research and Development

March 2008 - Organizing Committee,
*Algorithms, Inference, and Statistical Physics*workshop, Santa Fe, New Mexico

May 2007 - Advisory Committee,
*NetSci07 – International Conference on Network Science*, New York

May 2007 - Board of Trustees (member ex-officio), Institute for Pure and Applied Mathematics, University of California, Los Angeles

July 2003 – June 2006 - Science Advisory Board (member ex-officio), Institute for Pure and Applied Mathematics, University of California, Los Angeles

July 2003 – June 2006 - Review Panel, DOE NNSA Office of Research and Engineering

April 2005 - Review Panel, DOE Laboratory-Directed Research and Development (LDRD) Directed Research program

June 2004 - Organizer,
*Phase Transitions in Computer Science*symposium, Annual Meeting of the American Association for the Advancement of Science, Seattle

February 2004 - Advisory Board, Los Alamos National Laboratory Research Library

December 1998 – June 2003 - Program Committee, 2003 Congress on Evolutionary Computation
- Program Committee, 2002 Congress on Evolutionary Computation
- Organizing Committee chair,
*Phase Transitions and Algorithmic Complexity*workshop, Institute for Pure and Applied Mathematics, University of California, Los Angeles

June 2002 - Organizing Committee chair,
*Computational Complexity and Statistical Physics*workshop, Santa Fe, New Mexico

September 2001 - Co-organizer,
*Frontiers in Combinatorics*workshop, Los Alamos, New Mexico

July-August 1998