Mihalis Yannakakis is Professor of Computer Science at Columbia University. He is noted for his work in computational complexity and other related fields, he won the Donald E. Knuth Prize in 2005. Yannakakis was born in Athens, Greece in 1953 and attended Varvakeio High School for his early education, he graduated from the National Technical University of Athens in 1975 with a diploma in Electrical Engineering, earned his Ph. D. in Computer Science from Princeton University in 1979. His dissertation was entitled "The Complexity of Maximum Subgraph Problems". In 1978 he joined Bell Laboratories and served as Director of the Computing Principles Research Department starting from 1991 until 2001, when he left Bell laboratories and joined Avaya Laboratories. There he served as Director of the Computing Principles Research Department until 2002. In 2002 he joined Stanford University where he was a Professor of Computer Science, left in 2003 to join Columbia University in 2004, where he is serving as the Percy K. and Vida L. W. Hudson Professor of Computer Science.
From 1992 to 2003, Yannakakis served on the Editorial board of the SIAM Journal on Computing and was the Editor-in-chief between 1998 and 2003. He was a member of the editorial board of the Journal of the ACM from 1986 to 2000. Other editorial board memberships include the Journal of Computer and System Sciences, the Journal of Combinatorial Optimization, the Journal of Complexity, he has served on conference committees and chaired various conferences, such as the ACM Symposium on Principles of Database Systems and the IEEE Symposium on Foundations of Computer Science. As of November 2015, his publications have been cited close to 27,000 times, he has an h-index of 86. Yannakakis is known for his contributions to computer science in the areas of computational complexity theory, database theory, computer aided verification and testing, algorithmic graph theory. Among his contributions to complexity theory are two papers about the PCP theory and about hardness of approximation. In the Annual ACM Symposium on Theory of Computing of 1988, Yannakakis and Christos Papadimitriou introduced the definitions of the complexity classes Max-NP and Max-SNP.
Max-NP and Max-SNP contain a number of interesting optimization problems, it was shown by Yannakakis and Papadimitriou that these problems have some bounded error. These findings were able to explain the lack of progress, seen in the research community on the approximability of a number of optimization problems, including 3SAT, the Independent Set problem, the Travelling Salesman Problem. Yannakakis and Carsten Lund presented a number of findings regarding the hardness of computing approximations at the Annual ACM Symposium on Theory of Computing of 1993; these findings demonstrated the difficulty of efficiently computing approximate solutions to a number of minimization problems such as Graph coloring and Set covering. Given the unlikely scenario that NP-hard problems such as Graph coloring and Set covering would be solved optimally in polynomial time, there had been many attempts to develop efficient approximation solutions for them. In the area of database theory, his contributions include the initiation of the study of acyclic databases and of non-two-phase locking.
Acyclic database schemes are schemes that contain a single acyclic join dependency and a collection of functional dependencies. With regard to non two-phase locking, Yannakakis demonstrated how knowledge about the structure of a database and the forms of various transactions executed on them could be used to establish whether a particular locking policy is safe or not; the used two phase locking policies consist of two stages - for locking and unlocking entities - and to avoid such a policy it is necessary to impose some structure on the entities of a database. Such a policy need not be two-phase and these policies can be classified according to the connectivity of the above-mentioned hypergraph, 2PL policies being only one particular instance of these. Yannakakis went on to show that for the natural class of safe locking policies, freedom from deadlocks is determined on the order in which entities are accessed by transactions, from this derived simple conditions that would guarantee freedom from deadlocks for an L-policy.
He has contributed to the area of computer aided verification and testing, where he laid the rigorous algorithmic and complexity-theoretic foundations of the field. Some of his contributions include the designing of memory efficient algorithms for the verification of temporal properties of finite-state programs, determining the complexity of testing whether programs satisfy their specifications expressed in linear-time temporal logic, verifying that a model with timing constraints satisfies a given temporal property. Along with Alex Groce and Doron Peled, he introduced Adaptive Model Checking, showing that when inconsistencies are present between a system and the corresponding model, the results of
American Journal of Mathematics
The American Journal of Mathematics is a bimonthly mathematics journal published by the Johns Hopkins University Press. The American Journal of Mathematics is the oldest continuously published mathematical journal in the United States, established in 1878 at the Johns Hopkins University by James Joseph Sylvester, an English-born mathematician who served as the journal's editor-in-chief from its inception through early 1884. W. E. Story was associate editor in charge. For volume 7 Simon Newcomb became chief editor with Craig managing until 1894. With volume 16 it was "Edited by Thomas Craig with the Co-operation of Simon Newcomb" until 1898. Other notable mathematicians who have served as editors or editorial associates of the journal include Frank Morley, Oscar Zariski, Lars Ahlfors, Hermann Weyl, Wei-Liang Chow, S. S. Chern, André Weil, Harish-Chandra, Jean Dieudonné, Henri Cartan, Stephen Smale, Jun-Ichi Igusa, Joseph A. Shalika. Fields medalist Cédric Villani has speculated that "the most famous article in its long history" may be a 1958 paper by John Nash, "Continuity of solutions of parabolic and elliptic equations".
The American Journal of Mathematics is a general-interest mathematics journal covering all the major areas of contemporary mathematics. According to the Journal Citation Reports, its 2009 impact factor is 1.337, ranking it 22nd out of 255 journals in the category "Mathematics". As of June, 2012, the editors are Christopher D. Sogge, editor-in-chief, William Minicozzi II, Freydoon Shahidi, Vyacheslav Shokurov. Official website
Mathematics includes the study of such topics as quantity, structure and change. Mathematicians use patterns to formulate new conjectures; when mathematical structures are good models of real phenomena mathematical reasoning can provide insight or predictions about nature. Through the use of abstraction and logic, mathematics developed from counting, calculation and the systematic study of the shapes and motions of physical objects. Practical mathematics has been a human activity from as far back; the research required to solve mathematical problems can take years or centuries of sustained inquiry. Rigorous arguments first appeared in Greek mathematics, most notably in Euclid's Elements. Since the pioneering work of Giuseppe Peano, David Hilbert, others on axiomatic systems in the late 19th century, it has become customary to view mathematical research as establishing truth by rigorous deduction from appropriately chosen axioms and definitions. Mathematics developed at a slow pace until the Renaissance, when mathematical innovations interacting with new scientific discoveries led to a rapid increase in the rate of mathematical discovery that has continued to the present day.
Mathematics is essential in many fields, including natural science, medicine and the social sciences. Applied mathematics has led to new mathematical disciplines, such as statistics and game theory. Mathematicians engage in pure mathematics without having any application in mind, but practical applications for what began as pure mathematics are discovered later; the history of mathematics can be seen as an ever-increasing series of abstractions. The first abstraction, shared by many animals, was that of numbers: the realization that a collection of two apples and a collection of two oranges have something in common, namely quantity of their members; as evidenced by tallies found on bone, in addition to recognizing how to count physical objects, prehistoric peoples may have recognized how to count abstract quantities, like time – days, years. Evidence for more complex mathematics does not appear until around 3000 BC, when the Babylonians and Egyptians began using arithmetic and geometry for taxation and other financial calculations, for building and construction, for astronomy.
The most ancient mathematical texts from Mesopotamia and Egypt are from 2000–1800 BC. Many early texts mention Pythagorean triples and so, by inference, the Pythagorean theorem seems to be the most ancient and widespread mathematical development after basic arithmetic and geometry, it is in Babylonian mathematics that elementary arithmetic first appear in the archaeological record. The Babylonians possessed a place-value system, used a sexagesimal numeral system, still in use today for measuring angles and time. Beginning in the 6th century BC with the Pythagoreans, the Ancient Greeks began a systematic study of mathematics as a subject in its own right with Greek mathematics. Around 300 BC, Euclid introduced the axiomatic method still used in mathematics today, consisting of definition, axiom and proof, his textbook Elements is considered the most successful and influential textbook of all time. The greatest mathematician of antiquity is held to be Archimedes of Syracuse, he developed formulas for calculating the surface area and volume of solids of revolution and used the method of exhaustion to calculate the area under the arc of a parabola with the summation of an infinite series, in a manner not too dissimilar from modern calculus.
Other notable achievements of Greek mathematics are conic sections, trigonometry (Hipparchus of Nicaea, the beginnings of algebra. The Hindu–Arabic numeral system and the rules for the use of its operations, in use throughout the world today, evolved over the course of the first millennium AD in India and were transmitted to the Western world via Islamic mathematics. Other notable developments of Indian mathematics include the modern definition of sine and cosine, an early form of infinite series. During the Golden Age of Islam during the 9th and 10th centuries, mathematics saw many important innovations building on Greek mathematics; the most notable achievement of Islamic mathematics was the development of algebra. Other notable achievements of the Islamic period are advances in spherical trigonometry and the addition of the decimal point to the Arabic numeral system. Many notable mathematicians from this period were Persian, such as Al-Khwarismi, Omar Khayyam and Sharaf al-Dīn al-Ṭūsī. During the early modern period, mathematics began to develop at an accelerating pace in Western Europe.
The development of calculus by Newton and Leibniz in the 17th century revolutionized mathematics. Leonhard Euler was the most notable mathematician of the 18th century, contributing numerous theorems and discoveries; the foremost mathematician of the 19th century was the German mathematician Carl Friedrich Gauss, who made numerous contributions to fields such as algebra, differential geometry, matrix theory, number theory, statistics. In the early 20th century, Kurt Gödel transformed mathematics by publishing his incompleteness theorems, which show that any axiomatic system, consistent will contain unprovable propositions. Mathematics has since been extended, there has been a fruitful interaction between mathematics and science, to
Robert Endre Tarjan is an American computer scientist and mathematician. He is the discoverer of several graph algorithms, including Tarjan's off-line lowest common ancestors algorithm, co-inventor of both splay trees and Fibonacci heaps. Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University, the Chief Scientist at Intertrust Technologies Corporation, he was born in California. His father was a child psychiatrist specializing in mental retardation, ran a state hospital; as a child, Tarjan read a lot of science fiction, wanted to be an astronomer. He became interested in mathematics after reading Martin Gardner's mathematical games column in Scientific American, he became interested in math in the eighth grade, thanks to a "very stimulating" teacher. While he was in high school, Tarjan got a job, he first worked with real computers while studying astronomy at the Summer Science Program in 1964. Tarjan obtained a Bachelor's degree in mathematics from the California Institute of Technology in 1969.
At Stanford University, he received his master's degree in computer science in 1971 and a Ph. D. in computer science in 1972. At Stanford, he was supervised by Robert Floyd and Donald Knuth, both prominent computer scientists, his Ph. D. dissertation was An Efficient Planarity Algorithm. Tarjan selected computer science as his area of interest because he believed that computer science was a way of doing mathematics that could have a practical impact. Tarjan has been teaching at Princeton University since 1985, he has held academic positions at Cornell University, University of California, Stanford University, New York University. He has been a fellow of the NEC Research Institute. In April 2013 he joined Microsoft Research Silicon Valley in addition to the position at Princeton. In October 2014 he rejoined Intertrust Technologies as chief scientist. Tarjan has worked at AT&T Bell Labs, Intertrust Technologies and Hewlett Packard. Tarjan is known for his pioneering work on graph theory data structures.
Some of his well-known algorithms include Tarjan's off-line least common ancestors algorithm, Tarjan's connected components algorithm, he was one of five co-authors of the median of medians linear time selection algorithm. The Hopcroft-Tarjan planarity testing algorithm was the first linear-time algorithm for planarity-testing. Tarjan has developed important data structures such as the Fibonacci heap, the splay tree. Another significant contribution was the analysis of the disjoint-set data structure. Tarjan received the Turing Award jointly with John Hopcroft in 1986; the citation for the award states that it was: For fundamental achievements in the design and analysis of algorithms and data structures. Tarjan was elected an ACM Fellow in 1994; the citation for this award states: For seminal advances in the design and analysis of data structures and algorithms. Some of the other awards for Tarjan include: Nevanlinna Prize in Information Science – first recipient National Academy of Sciences Award for Initiatives in Research Paris Kanellakis Award in Theory and Practice, ACM Blaise Pascal Medal in Mathematics and Computer Science, European Academy of Sciences Caltech Distinguished Alumni Award, California Institute of Technology Tarjan holds at least 18 U.
S. patents. These include: J. Bentley, D. Sleator, R. E. Tarjan, U. S. Patent 4,796,003, Data Compaction, 1989 N. Mishra, R. Schreiber, R. E. Tarjan, U. S. Patent 7,818,272, Method for discovery of clusters of objects in an arbitrary undirected graph using a difference between a fraction of internal connections and maximum fraction of connections by an outside object, 2010 B. Pinkas, S. Haber, R. E. Tarjan, T. Sander, U. S. Patent 8220036, Establishing a secure channel with a human user, 2012 Tarjan, Robert E.. Data structures and network algorithms. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-187-5. OCLC 10120539. Tarjan, Robert E.. Notes on introductory combinatorics. Boston: Birkhauser. ISBN 978-0-8176-3170-3. OCLC 10018128. OCLC entries for Robert E Tarjan Robert E. Tarjan at DBLP Bibliography Server Robert E. Tarjan at DBLP Bibliography Server List of Robert Tarjan's patents on IPEXL's Patent Directory Robert Tarjan's home page at Princeton. Robert Endre Tarjan at the Mathematics Genealogy Project