Institute for Pure and Applied Mathematics University of California, Los Angeles Box 957121 Los Angeles, CA 90095-7121 Tel: (310) 825-2627 / Fax: (310) 825-4756 E-mail:

Los Alamos National Laboratory Modeling, Algorithms and Informatics Group Computer and Computational Sciences Division MS-B256 Los Alamos, NM 87545 WWW: http://www.lanl.gov/home/percus

Research Interests:

• Combinatorial optimization
• Local-search heuristics
• Condensed matter: random disordered systems
• Algorithms in computational biology

Education:

• Université Paris-Sud, Orsay: PhD in statistical physics
  September 1997

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

• Harvard University: BA in physics
  June 1992

Positions Held:

• Associate Director, Institute for Pure and Applied Mathematics, University of California, Los Angeles
  July 2003 - present

• Member of the Technical Staff, Los Alamos National Laboratory: Computer & Computational Sciences Division
  June 2000 - present

• Associate Adjunct Professor, Department of Computer Science and Engineering, University of California, Riverside
  December 2002 - October 2005

• Postdoctoral Research Associate, Los Alamos National Laboratory: Center for Nonlinear Studies and Computer Research & Applications Group
  October 1997 - June 2000

Publications:

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

• 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 kth-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).

Funding:

• Co-PI on DOE Weapons Supported Research (WSR) Computer Science Research Foundation project New Approaches to Fault Tolerance (total budget: $696K)
  October 2005 - September 2008

• Co-PI on NSF ACT award Intelligent Extraction of Information from Graphs and High-Dimensional Data (total budget: $200K)
  July 2005

• Senior Personnel on NSF renewal award Institute for Pure and Applied Mathematics (total budget: $17M)
  July 2005 - June 2010

• Co-PI on DOE Laboratory-Directed Research and Development (LDRD) Directed Research project Statistical Physics of Infrastructure Networks (total budget: $4.5M)
  October 2003 - September 2006

• PI on DOE Laboratory-Directed Research and Development (LDRD) Exploratory Research project Improving Local Search (total budget: $840K)
  October 2002 - September 2005

• Co-PI on DOE Laboratory-Directed Research and Development (LDRD) Exploratory Research project Extremal Optimization (total budget: $320K)
  October 1999 - September 2002

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

Professional Activities and Service:

• Ex-officio member of Board of Trustees, Institute for Pure and Applied Mathematics, University of California, Los Angeles
  July 2003 - present

• Ex-officio member of Science Advisory Board, Institute for Pure and Applied Mathematics, University of California, Los Angeles
  July 2003 - present

• Created two new quarter-long graduate courses on Heuristic Methods in Optimization, University of California, Riverside, Department of Computer Science and Engineering
  January - June 2003

• Lead organizer of Phase Transitions in Computer Science symposium, Annual Meeting of the American Association for the Advancement of Science, Seattle
  February 2004

• Lead organizer of Phase Transitions and Algorithmic Complexity workshop, Institute for Pure and Applied Mathematics, University of California, Los Angeles
  June 2002

• Lead organizer of Computational Complexity and Statistical Physics workshop, Santa Fe, New Mexico
  September 2001

• Co-organizer of Frontiers in Combinatorics workshop, Los Alamos, New Mexico
  July - August 1998

• 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
  

• 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

• Reviewer for
  • Annals of Applied Probability
  • Applied Acoustics
  • Applied Mathematical Modeling
  • INFORMS Journal on Computing
  • Inverse Problems in Science and Engineering
  • Journal of Physics A
  • Lecture Notes in Physics, special volume on "Complex Networks"
  • NSF Division of Materials Research
  • Physica A
  • Physical Review Letters
  • Physical Review E
  • Physics Letters A
  • Proceedings of the Royal Society A
  • 2003 ACM/SIAM Symposium on Discrete Algorithms