Sorin Istrail

Early Life and Education

Târgu-Neamț and Iasi

Sorin Istrail was born in Târgu-Neamț, Judetul Neamț, District of Moldova, Romania, to Carol Istrail and Roza Istrail, who provided unconditional love and inspiration. He graduated from Scoala Generala No. 2, now Scoala Domneasca, and from Liceul “Stefan Cel Mare,” now Colegiul National “Stefan Cel Mare.” His mathematics teachers – Constatin Bumbea in elementary school and Mihai Turcu in high school – were his inspirations. He began his academic journey in 1971 where he studied computer science at Universitatea „Alexandru Ioan Cuza" (University of Iasi) in Iasi, Romania, and in 1975 graduated summa cum laude (perfect grade of 10) and valedictorian (one of three “sefi de promotie”) in the university’s first graduating class of Informatica (Computer Science) students.

After graduation, he accepted a research position in the University of Iasi’s Computer Center and at “Al. Myller” Mathematical Institute (Seminarul Matematic), where he remained until 1983. In 2010 the University of Iasi celebrated its 150 years anniversary, and its “Al. Myller” Mathematical Institute celebrated its 100 years anniversary. Vice-Rector Professor Luchian and the University invited Istrail to the celebration and awarded him the title of Professor Honoris Causa of the University A. I. Cuza, Iasi. text 1

Ph.D. at University of Bucharest

Istrail continued his academic trajectory in 1976 in the doctoral program at the Department of Mathematics of the University of Bucharest. Under the guidance of Professors Solomon Marcus and Sergiu Rudeanu, he earned his Ph.D. in 1979 with the thesis “Context- Sensitive Languages and Applications to Program Semantics and Number Theory.” In graduate school he worked on advancing the theory of context-sensitive Chomsky grammars, and of Marcus contextual grammars. Overall, Istrail wrote 20 papers on formal languages and Chomsky grammars and Marcus contextual grammars. Istrail proved a theorem – a favorite of Professor Marcus – showing a deep connection between Chomsky grammars and number theory: “The necessary and sufficient condition for a number to be algebraic of degree 2 is for the language of mathematical expressions of its continuous fractions reduces to be context-free” (Revue Romaine de Mathematiques Pure and Applied (1977)).

He also developed a theory of computation for context-sensitive grammars and identified a set of recursive functions computable by them. (Information and Control (1978, 1979)).

Solving a problem proposed by Georghe Paun, Istrail constructed an infinite square-free sequence over three letters using a simple momorphism (h(a)=abc, h(b)=ac, h(c)=b), which the French school of combinatorics calls the “morphisme d’Istrail.” Analogous to the minimal and aperiodic tiling theory problems – where in 2D, the solution to the “einstein” (ein Stein) problem was found for one tile that tiles aperiodically the infinite Euclidean 2D space, and in 3D, Hilbert’s 18th problem where the search is for one polyhedron that aperiodically tiles the infinite Euclidean 3D space (problem still open) – we have Istrail’s morphism as the minimal aperiodic tiling solution for the infinite 1D space with three tiles (letters). 1983-1992:

Postdoctoral studies at MIT

In 1983 Istrail’s journey continued in America where he joined Wesleyan University as an Assistant Professor of Computer Science and pursued postdoctoral studies at MIT with Professor Albert Meyer (1984 to 1992). His research with Professor Meyer focused on axiomatizing the semantics of concurrent programs. It culminated in the publication of a logical expressive power separation of Robert Milner’s Calculus of Communicating Systems and Tony Hoare’s Theory of Communicating Sequential Processes: “Bisimulation Can’t Be Traced,” (Principles of Programming Languages (1988), Journal of the Association for Computing Machinery (JACM) (1995)).

Wesleyan colleague Professor Alan Cobham brought to Professor Istrail the Universal Traversal Sequences (UTS) problem proposed by Steve Cook, a problem of fundamental importance in computational complexity theory of logarithmic space complexity classes (deterministic logarithmic space L, and non-deterministic logarithmic space NL), within the L vs. NL seminal open question one of the most studied problems in computational complexity theory. With mentorship from MIT Professor Michael Sipser, Professor Istrail provided the first construction of universal traversal sequences of 2-regular graphs in log-space: “Polynomial Traversing Sequences for Cycles are Constructible” (Symposium on the Theory of Computing (STOC) (1988), Foundations of Computer Science (FOCS) (1990)). The complete proof of his algorithmic construction is long, about 70 pages. Professor Istrail considers this result the deepest computer science algorithm he has designed and published. It was proved non-constructively by Aleliunas, Karp, Lipton, Lovasz, and Rackoff that UTSs of length O(𝑑2𝑛3 log 𝑛) exist (see FOCS (1979)). Prior constructions were “brute force” in length, which for logarithmic space computations are of size O(𝑛log n ). Professor Istrail’s UTS construction has size O(𝑛4.76) i.e., polynomial length, and is constructible in logarithmic space. The general case is still open, and Professor Istrail continues his work there, but after 37 years, his result is still the only UTS construction for any general graph class.

In 1992, together with Lenny Heath, inspired by VLSI circuitry design applications and topological graph theory, and with great interactions and mentorship support from Professor Tom Leighton (MIT), they designed algorithms for book embedding of genus 𝑔 graphs in O(𝑔) pages, on orientable and non-orientable surfaces (STOC (1987), JACM (1992)). They proved a lower bound of O(sqrt(g)) and conjectured O(sqrt(g)) pages as the optimal bound. S. Malitz in his MIT Ph.D. thesis proved non-constructively their conjecture (FOCS (1988)).

Career

1992-2000: Sandia National Laboratories

In 1992, Professor Istrail joined Sandia National Labs. There, he co-founded the Computational Biology Project with Ernie Brickell (Department Manager) and Dr. Fred Howes (Manager of the U.S. Department of Energy’s (DOE) Applied Mathematics Program, which was founded at DOE by John von Neumann). He led the project through 2000. Istrail’s transition into computational biology began with work on algorithmic strategies for genome physical mapping problems, a key challenge of the Human Genome Project started at DOE by Charles DeLisi. Collaboration with Michael Waterman (University of Southern California) provided statistically rigorous foundations for the computational methods developed.

In 1994, the next challenge arose for Istrail and his research group – the Protein Folding Problem, which is of fundamental importance in biology, biochemistry, biophysics, and biotechnology. Working with Bill Hart, Istrail developed the first approximation algorithms in the literature with mathematical guaranteed error bounds for a protein folding lattice model: “Fast Protein Folding in the Hydrophobic-Hydrophilic Model Within Three-Eighths of Optimal” (STOC (1995), International Conference on Research of Computational Molecular Biology (RECOMB) (1997)). The algorithms applied to one of the most studied lattice biophysical protein folding models –the HP-model (Hydrophobic-Polar model) of Ken Dill. Istrail’s search for an exactly solvable protein folding model has continued for almost 30 years. He also continued his research on the thermodynamic hypothesis and the protein folding energy function inference using combinatorics and computer science methods as well as voting theory and mathematical economics theory.

Istrail also worked on problems related to drug design and combinatorial chemistry. He and his collaborators designed chemical graph theory algorithms for designing chemical compounds based on the “Lipinski rule of 5” and toxicity avoidance.

Bill Camp, Istrail’s division director at Sandia, brought to him the Three-Dimensional Ising Model Problem and became his mentor on statistical mechanics of the 3D Ising Model. The problem had a lengthy history. In 1944, Lars Onsager, Brown University Professor of Chemistry from 1928-1933 and the 1968 winner of the Nobel Prize for Chemistry, obtained the analytical exact computation of the phase transition and the exact solution for the 2D planar Ising Model (Ising ferromagnetic 2D plane grid). His seminal exact mathematical proof of the 2D planar Ising model partition function formula is considered a tour de force, one of the most extraordinary mathematical proofs in statistical physics. Answering the call to “make [the proof] human,” a dream team of mathematicians and physicists, including Kac, Ward, Feynman, Hurst, Kasteleyn and Temperley, attempted until 1975 to generalize Onsager’s proof to three dimensions, but without success. Kac and Ward, with contributions from Feynman, obtained a combinatorial proof of the Onsager 2D theorem. In 2000, Istrail published the paper "Statistical Mechanics, Three-Dimensionality and NP-completeness. I. Universality of Intractability for the Partition Function of the Ising Model Across Non-Planar Lattices" at the Symposium on the Theory of Computing (STOC 2000). His paper showed, for several Ising spin glass models, that for every non-planar (and therefore every 3D) model, computing the partition function is NP-complete. Istrail’s proofs were axiomatic: Non-planarity plus Translational Invariance implies NP-completeness. He obtained the negative solution (computational intractability) of this 50-year-old unresolved problem in statistical mechanics, which asked for the derivation of the analytical closed form of the partition function of the 3D Ising Model. Istrail’s paper on the 3D Ising Model was included in the Top 100 Most Important Discoveries of the U.S. Department of Energy (DOE)'s first 25 years, and the 7th top achievement of DOE in Advanced Scientific Computing.

In 2000, Istrail’s research on computational statistical mechanics was selected by a workshop sponsored by the National Science Foundation, ACM/SIGACT, DIMACS and SIAM as the basis for a major theoretical computer science challenge for the 21st century. (This workshop was similar to the 1900 International Congress of Mathematicians when Hilbert presented the list of major unresolved mathematical problems that would become the main focus for 20th Century research.) The citation for the challenge read: “In recent years there have been an increasing number of collaborations between theoretical computer scientists and physicists interested in statistical mechanics. Microsoft Research has an entire department devoted to such work. The synergy is due to the fact that both groups of researchers are interested in the same sorts of problems but bring different sets of tools and ways of thought to them. The classical physics problem that serves as a motivation is the behavior of matter (from gases to crystal lattices) in the presence of heat, magnetism, or other external forces. One fundamental quantity that physicists are interested in is the “partition function” for a given model, which is needed if probabilities are to be normalized. For one well- studied model, the Ising model for spin glasses, we now have almost completely characterized the complexity of computing the partition function. It has long been known to be polynomial- time computable for planar lattices, and now, due to results of Istrail (STOC 2000), it is known to be NP-hard for any non-planar lattice. One challenge is to extend this work to other important models.”

In 1997, with Professors Pavel Pevzner and Michael Waterman, Istrail co-founded RECOMB (the International Annual Conference on Research in Computational Molecular Biology) in Santa Fe, New Mexico. RECOMB 2025, now in its 29th year, will be held in Seoul, South Korea, in April. Istrail is Co-Editor with Pevzner and Waterman of the book series “Lecture Notes in Bioinformatics” published by Springer. Between 2000 and 2020, Istrail and Waterman served as Co-Editors-in-Chief of the Journal of Computational Biology (Mary Ann Liebert, Inc., publisher).

2000-2005: Celera Genomics

(2000-2005 )

Istrail joined Celera Genomics in 2000 as the Senior Director of Informatics Research, and later become Head of the Informatics Research Department (2002-2005). Having come from Sandia Labs – on an Air Force base in Albuquerque, New Mexico, where decades earlier in Los Alamos Laboratory, the sister atomic energy laboratory, von Neumann and a dream team of scientists worked on the extraordinary Manhattan Project – he now found himself in Rockville, Maryland, among a dream team of scientists pursuing another bigger-than-life scientific endeavor – the Celera Genome Project. Working closely with Celera President Craig Venter was life changing, a profound experience for Istrail and the Informatics Research team. Venter trained and inspired them to master the art of making the impossible possible in genomics. “Algorithms are the make-or- break of Celera,” Venter told them. Inspired by this “Venter School of Leadership,” Istrail’s group played a major role in constructing the computational assembly of the human genome and co-authored the paper J. C. Venter et al. “The Sequence of the Human Genome,” SCIENCE (2001) which, with over 20,000 citations to date, is one of the most cited scientific papers of all time. Istrail’s group also built a powerful suite of genome-assembly-to-genome-assembly alignment algorithms that was used to compare all human genome assemblies to date – S. Istrail et al. “Whole Genome Shotgun Assembly and Comparison of Human Genome Assemblies” (Proceedings of the National Academy of Sciences (PNAS) (2004)).

In 2002, Istrail’s Celera group, in collaboration with the company ClearForrest, won the ACM Knowledge Discovery and Data Mining Cup (the KDD Cup) – the top international data mining machine learning competition. The challenge at that time was the automatic annotation of a section of the Drosophila genome. Istrail’s Celera group also developed algorithms for SNPs and haplotype inference and analysis, with applications to population genetics, SNP assay design, and pharmacogenomics. In setting the research agenda of the SNPs and Haplotypes Team, collaboration with Andy Clark (Cornell University), one of the leading researchers in human genetics, was essential and inspiring. Collaboration with Waterman added strength and rigor to the developed algorithmic strategies. In 2021, one of Istrail’s Celera group’s papers – “SNPs Problems, Complexity and Algorithms”(2003) – received the 20-years Test-of-Time Award from the European Symposium of Algorithms. It pioneered the field of computational haplotyping, employing rigorous computer science methods. Istrail and his Ph.D. students and postdoctoral students and key collaborators like Bjarni Halldorsson (deCODE genetics and Reykyavik University), Russell Schwartz (Carnegie Mellon University) and Vineet Bafna (USCD) continued the research program on SNPs and haplotypes reconstruction and applications to medical bioinformatics and GWAS (genome-wide association studies) for autism, multiple sclerosis, heart disease, cancer pathology, HIV as well as well as applications for health and disease genomics for human and animals, and polyploidy haplotype reconstructions for plants and the human disease in brain, liver and heart cells. In collaboration with Eric Morrow (Brown), Istrail co-authored the paper “Intellectual Disability Is Associated with Increased Runs of Homozygosity in Simplex Autism” (American Journal of Human Genetics (2013)) where GWAS methods were developed using haplotype and pedigree analysis for estimating the age of a disease mutation for Autism.

In collaboration with Jonathan Yewdell (NIH), Istrail’s Celera group published an important viral genomics paper, S. I. et al. “Comparative Immunopeptidomics of Humans and Their Pathogens” (PNAS 2004).

In 2003, Istrail joined the ranks of Applied Biosystems Science Fellows, Informatics, as “Best in Class” – the highest distinction for individual technical contributions in Applied Biosystems. He was one of six Fellows at Celera/Applied Biosystems – a company with 800 scientists.

2005-present: California Institute of Technology and Brown University

After Celera, Istrail moved to California Institute of Technology (Caltech), in the Division of Biology as a visiting senior scientist, working with his longtime mentor and closest friend, Professor of Biological Sciences Eric Davidson.

Istrail joined the Department of Computer Science at Brown University in 2005, where since 2006 he is the James A. and Julie N. Brown Professor of Computational and Mathematical Sciences and Professor of Computer Science. While at Brown, he served as the Director of Brown University’s Center for Computational Molecular Biology (2006-2011). In 2008, at Istrail’s invitation, Professor Marcus visited Brown and presented a lecture titled “The Loneliness of the Mathematician.” It was the first of what ultimately were 12 lectures at Brown – four in 2008 and eight in 2011. (All 12 will be published as a volume in the Romanian Magazine “Century XXI” (Secolul XXI) in 2025, part of the UNESCO Marcus 100th Anniversary Year Celebration) [1]. Two years later, “The Loneliness of the Mathematician” was retroactively deemed the inaugural presentation of the John von Neumann Distinguished Lecture Series launched as part of “John von Neumann Days at Brown,” a conference organized by the university’s newly gathered von Neumann Professors “cluster” – Istrail (Department of Computer Science), Leon Cooper (Department of Physics), Stu Geman (Department of Applied Mathematics) and Roberto Serrano (Department of Economics). The four professors represent the scientific disciplines in which von Neumann made his most famous seminal breakthroughs. The von Neumann professors “cluster” continued their work in 2015 when they designed the “Brown University 250th Anniversary Symposium: The Next 250 years.” Envisioned as an “academic cathedral” unified by von Neumann’s vision of “computation as a scientific lens,” the symposium, chaired by Istrail, consisted of von Neumann lectures in mathematics, physics, economics, computer science, and neuroscience. Von Neumann continued to be a common denominator in Istrail’s and Marcus’s collaborations. In 2012, they traveled to the Alan Turing Centennial Conference in Cambridge, UK. There, Professor Marcus delivered the lecture “Alan Turing and John von Neumann: Their Brains and Their Computers.” It was based on a paper with the same title written by Istrail and Marcus. Istrail presented two other papers at the Turing Centennial Conference. The first, coauthored with his “cluster” colleague Cooper, was titled “Mental Experience and the Turing Test: This Double Face is the Face of Mathematics.” The second was “Computer Science Through Urn Games: A Unified Framework for a Hierarchy of Solvable and Unsolvable Problems” by Istrail. (In addition to being a one of Istrail’s collaborators, Cooper, a recipient of the Nobel Prize for the discovery of superconductivity, was among Istrail’s beloved mentors. Sadly, he passed away in 2024.) Istrail’s work with CalTech’s Davidson between 2000 and 2015 was another fruitful partnership, making important contributions to constructing the sea urchin genome (Science 2006) and transcriptome assemblies (Science 2006, Istrail as co-senior author), causality based systems biology (“Functional cis-regulatory genomics for systems biology”, PNAS 2010, Istrail as co-senior author) and developing a mathematical information processing model for gene regulatory systems and networks in the papers S.I., and E. Davidson “Logic Functions of the Genomic cis-Regulatory Code” (PNAS 2005) and S.I., S. de Leon, E. Davison “The Regulatory Genome and the Computer” (Dev. Biol. 2007), a paper coinciding with the 50th anniversary of von Neumann’s seminal book, The Computer and the Brain. Written in the same style as von Neumann’s book, the 2007 paper presented a comparison between every component of the electronic computer and its counterpart in the Regulatory Genome’s information processing “computer” embedded in the wet-medium molecular biology of the cell. Davidson co-advised Professor Istrail’s Ph.D. student Ryan Tarpine, who wrote a thesis entitled “A Database of Causality-Inferred Structure-Function Information for Genomic cis-Regulatory Architecture” (Brown University, Department of Computer Science (2012)). Sadly, Professor Davidson passed away in 2015. In 2019, in the paper by S. I. “Eric Davidson's Regulatory Genome for Computer Science: Causality, Logic, and Proof Principles of the Genomic cis-Regulatory Code” Istrail provided an in depth presentation of the Davidson-Istrail research program, with its achievements, as well as remaining major open problems about the Regulatory Genome and Gene Regulatory Systems.

Professor Istrail’s legacy continues through the undergraduate, graduate and postdoctoral students he has mentored and who have gone on to make contributions in their respective fields, including Dejan Živković (Serbia), Ryan Tarpine (Google), Derek Aguiar (UConn), Doug McErlean (Google), Austin Huang (Google DeepMind), Fumei Lam and Alper Uzun (Brown), Younhun Kim (MIT), Shivam Nadimpalli (Columbia), and Pinar Demetci (MIT). His work with Dr. Lam developed a new linkage disequilibrium measure that satisfied long-standing desiderata that had not been simultaneously fulfilled previously: the curse of the pairwise: conservative extension from pairwise to multiple markers, and the interpretability of intermediate values (F. Lam, R. Tarpine, S. I. “Conservative Extensions of Linkage Disequilibrium Measures from Pairwise to Multi-Loci and Algorithms for Optimal Tagging SNP Selection” (RECOMB 2010)). Derek Aguiar’s PhD thesis “Cycling through trees: accurate genome-wide algorithms for haplotype assembly and phasing” (Brown University, Department of Computer Science (2014)) with Istrail as his Ph.D. advisor introduced the problem of assembling the haplotypes of genomes of humans, animals and plants, and jointly developed HapCompass, a leading software tool for haplotype assembly: Derek Aguiar and S. I. “HAPCOMPASS: A fast cycle basis algorithm for accurate haplotype assembly of sequence data” (Journal of Computational Biology (2012)) and “Haplotype assembly in polyploid genomes and identical by descent shared tracts” (Bioinformatics (2013)). Most recently, Professor Istrail with his students McErlean and Aguiar has developed a globally optimal algorithm for computing maximum likelihood haplotype phasing: D. McErlean, D. Aguiar and S.I. “A globally optimal algorithm for computing maximum likelihood haplotype phasings: expo-posynomial optimization by graph homomorphism” (PNAS to appear). With Demetci and Aguiar, the trio developed algorithmic strategies for combinatorial and statistical prediction of gene expression from haplotype sequence (Intelligent Systems in Molecular Biology, 2021, Bioinformatics (2021))

2005-present: Co-Founder of the Moisil Intitute for Computer Science and Applications at University of Iasi

In 2012, Istrail, along with Professor Marcus; Professor Henri Luchian, Vice-Rector of University “Al. I. Cuza” Iasi; and the presidents of the University of Iasi and University of Bucharest founded the Grigore Moisil Institute of Computer Science and Applications at University of Iasi. The following year, the first Grigore Moisil Distinguished Lecture at the new institute was presented by Professor Kenneth Arrow of Stanford University, Nobel Laureate in Economics. At the time, Professor Arrow was considered the most famous economist in the United States. (Four of his students also received Nobel Prizes.) But the most exciting and sentimental distinction was that Professor’s Arrow parents were born in Romania. He received from University of Iasi the honorary title of Doctor Honoris Causa. The second Grigore Moisil Distinguished Lecture was given in 2014 by Princeton University’s John Conway, the John von Neumann Professor of Mathematics. At the time, Conway was considered the most famous mathematician alive.

Sorin's Essays

Istrail began writing storytelling essays about his scientific life when he arrived at Brown. His first was written at the request of the Department of Computer Science, which wanted him to tell the story of his journey from Romania to Brown. He co-wrote the essay, “Randomness is Beautiful: In Search of von Neumann,” with Tracie Sweeney, a senior editor at Brown. It appeared in the Department of Computer Science magazine, CONDUIT, Spring/Summer 2006. He ended the essay with a section called “Axioms,” lessons he’d learned from inspiring professors and personal heroes – above all, von Neumann. Taking his cue from von Neumann, Istrail’s axioms were:

Axiom 1. Randomness is beautiful;
Axiom 2. Work on the hardest problems;
Axiom 3. Continuously search for teachers;
Axiom 4. Scientific teams are fragile;
Axiom 5. A crisis is a terrible thing to waste;
Axiom 6. And in the end, the love you take is equal to the love you make;


Ken Arrow enjoyed the essay, in particular, he wrote to Istrail, “its light, yet penetrating touch into some deep thoughts on computing.” Additional essays were inspired by his professors and collaborators: Marcus, Edsger Dijkstra, Davidson, Waterman, Alberto Apostolico and Albert Meyer. Each was based on interactions with them (or in the case of von Neumann, hosting his daughter Marina von Neumann Whitman at Brown where she gave fascinating lectures about her father), or through published works and accounts by others. All end with “axioms” that Istrail hoped would capture the essence of what he learned from each subject, particularly those who excited and inspired him.

Here are Professor Marcus’s axioms:;


Axiom 0. Be a language theorist;
Axiom 1. Be a first-class scientist in at least one of the disciplines of your interdisciplinary research ;
Axiom 2. Be a mathematician of the continuous and discrete ;
Axiom 3. Be an intra-math, inter-sciences, and cross-cultures scientist ;
Axiom 4. Be the guardian of high standards ;
Axiom 5. Know a lot – really a lot – of mathematics;
Axiom 6. Be a storyteller [Moldovenii sint povestitori] ;


Axioms of several other professors are what Istrail calls “Marcus aspirational” or “marcusisms,” i.e., they eloquently highlight Marcus’s teachings and lessons learned [2]: - Eric Davidson “Serious people do thing seriously” - Eric Davidson “Have inexhaustible optimism, inexhaustible curiosity, inexhaustible energy and inexhaustible honesty!” - Sergiu Rudeanu “Critical feedback based on uncompromising high standards is fundamental to science” - Albert Meyer “Only major [computer science] results matter” - Edsger Dijkstra “Proofs are more important than theorems” - Michael Waterman “You know a man by his heroes” - John von Neumann “Work at the same time on the most abstract and most practical problems”

Essays in preparation:

*** Albert Meyer's Axioms

*** Craig Venter's Axioms

*** Ernst Ising and Lars Onsager and the Most Magnificent Scientific Achievement of a Brown University Professor

Sorin's Advisor Genealogy up the tree to Euler and Leibnitz

By way of “advisor genealogy,” Marcus, has rooted many of his students and collaborators to the great mathematicians of the past. Via Marcus, Istrail has 10 links to Euler and 13 links to Leibnitz. Istrail also has Erdős number 2 via his paper with Marcus on Turing and von Neumann. (Marcus has Erdős number 1 via his paper P. Erdős, S. Marcus, “Sur la décomposition de l'espace Euclidien en ensembles homogenes, Acta Math. Acad. Sci. Hungar. 8 (1957), 443-452.) Istrail also has Erdős postcard number 1 – sent from Albuquerque, NM, co-signed by Erdos, and mailed to – who else? – Marcus, and Einstein number 4.

Research

TEXT

TEXT

Honors and Awards

• * 2025 Negruzzi National Prize - 200
• * Honorary Citizen title, Municipality of the City of Iasi, Romania, 2023
• * 20 Years Test-of-Time Award, European Symposium of Algorithms, 2021
• * Fellow, International Society for Computational Biology, 2021
• * 2010: Professor Honoris Causa, Alexandru Ioan Cuza University, Iasi, Romania
• * 2006: Endowed Chair Professor, Brown University
• * 2003: Applied Biosystems Science Fellow, Informatics
• “Best in Class” – Highest distinction for individual technical contributions in Applied Biosystems. One of four Fellows in a company of 800 scientists and 5500 employees. The other fellows are in the areas of biology, chemistry and materials science.
• * 2002: Manager of the Celera Sub-Team of the ClearForrest-Celera team that won the 2002 ACM Knowledge Discovery and Datamining Cup (ACM KDD Cup), arguably the top International Datamining/Machine Learning Competition. Theme: automatic genomic annotation of Drosophila literature that matches human expert genomic annotation.
• * 2001: Work on the Computational Complexity of the Three-Dimensional Ising Model was ranked in the top 10 most distinguished achievements in the “Advanced Scientific Computing Research” category and in the top 100 most important discoveries of the U.S. Department of Energy in its 25 years of existence.
• * 2000: Graduation Speaker for the Mathematics and Physics Class of 2000, University of New Mexico
• * 2000: ACM Service Recognition, ACM General Chair of the RECOMB Conference
• * 2000: Work on computational statistical mechanics selected as the basis for a major theoretical computer science challenge for the 21st Century by the “Workshop on challenges for Theoretical Computer Science at the Beginning of the 21st Century”; workshop sponsored by National Science Foundation, ACM/SIGACT, DIMACS, SIAM.
  
  Challenge: Computational Statistical Mechanics
  
  In recent years there have been an increasing number of collaborations between theoretical computer scientists and physicists interested in statistical mechanics. Microsoft Research has an entire department devoted to this sort of work. The synergy is due to the fact that both groups of researchers are interested in the same sorts of problems, but bring different sets of tools and ways of thought to them. The classical physics problem that serves as a motivation is the behavior of matter (from gases to crystal lattices) in the presence of heat, magnetism, or other external forces. One fundamental quantity that physicists are interested in is the “partition function” for a given model, which is needed if probabilities are to be normalized. For one well-studied model, the Ising model for spin glasses, we now have almost completely characterized the complexity of computing the partition function. It has long been known to be polynomial-time computable for planar lattices, and now, due to results of Istrail (STOC 2000) it is known to be NP-hard for any non-planar lattice. One challenge is to extend this work to other important models.
  
  
• * 1999: Keynote Speaker for the New Mexico Mathematics Olympiad Finalists
• * 1998: Scientific American “Best of 1998” included the Supercomputing Simulation of Protein Misfolding Project, done by my Sandia Labs group in collaboration with Jonathan King, MIT.
• * 1995: The STOC95 Program Committee referred to our STOC95 paper – the first protein folding algorithms in the literature generating provable near-optimal folds – as a “seminal contribution.”
• * 1995: Sandia National Laboratories Award for Excellence for “The first protein folding prediction algorithm with guaranteed error bounds”

Service to the Field

• TEXT1

Selected Publications

• TEXT