Computational complexity theory
Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used; the theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e. the amount of resources needed to solve them, such as time and storage. Other measures of complexity are used, such as the amount of communication, the number of gates in a circuit and the number of processors. One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do; the P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.
Related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kind of problems can, in principle, be solved algorithmically. A computational problem can be viewed as an infinite collection of instances together with a solution for every instance; the input string for a computational problem is referred to as a problem instance, should not be confused with the problem itself.
In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing; the instance is a number and the solution is "yes" if the number is prime and "no" otherwise. Stated another way, the instance is a particular input to the problem, the solution is the output corresponding to the given input. To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.
When considering computational problems, a problem instance is a string over an alphabet. The alphabet is taken to be the binary alphabet, thus the strings are bitstrings; as in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists in binary. Though some proofs of complexity-theoretic theorems assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding; this can be achieved by ensuring that different representations can be transformed into each other efficiently. Decision problems are one of the central objects of study in computational complexity theory. A decision problem is a special type of computational problem whose answer is either yes or no, or alternately either 1 or 0. A decision problem can be viewed as a formal language, where the members of the language are instances whose output is yes, the non-members are those instances whose output is no.
The objective is to decide, with the aid of an algorithm, whether a given input string is a member of the formal language under consideration. If the algorithm deciding this problem returns the answer yes, the algorithm is said to accept the input string, otherwise it is said to reject the input. An example of a decision problem is the following; the input is an arbitrary graph. The problem consists in deciding; the formal language associated with this decision problem is the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings. A function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem—that is, the output isn't just yes or no. Notable examples include the integer factorization problem, it is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not the case, since function problems can be recast as decision problems.
For example, the multiplication of two integers can be expressed as the set of triples such that the relation a × b = c holds. Deciding whether a given triple is a member of this set corresponds to solving
Constantinos Daskalakis is a Greek theoretical computer scientist. He is a professor at MIT's Electrical Engineering and Computer Science department and a member of the MIT Computer Science and Artificial Intelligence Laboratory, he was awarded the Rolf Nevanlinna Prize in 2018. Daskalakis was born in Athens on 29 April 1981, his grandparents originated from Crete. He has Nikolaos; when Daskalakis was in eighth grade, his father bought an Amstrad CPC, which Daskalakis stayed up all night attempting to learn how it worked. He attended Varvakeio High School, completed his undergraduate studies in the National Technical University of Athens, where in 2004 he received his Diploma in Electrical and Computer Engineering, he completed his undergraduate thesis "On the Existence of Pure Nash Equilibria in Graphical Games with succinct description" under the supervision of Stathis Zachos. As an undergraduate, Daskalakis attained perfect scores in all but one of his classes, something which had not been achieved in the university's history.
He continued to study at University of California, where he received his PhD in Electrical Engineering and Computer Science in 2008 under the supervision of Christos Papadimitriou. After attaining his Ph. D. he spent a year as a postdoctoral researcher in Jennifer Chayes's group at Microsoft Research, New England. Daskalakis works on computation theory and its interface with game theory, probability theory and machine learning, he has resolved long-standing open problems about the computational complexity of the Nash equilibrium, the mathematical structure and computational complexity of multi-item auctions, the behavior of machine-learning methods such as the expectation–maximization algorithm. He has obtained computationally and statistically efficient methods for statistical hypothesis testing and learning in high-dimensional settings, as well as results characterizing the structure and concentration properties of high-dimensional distributions, his Ph. D. thesis was awarded the 2008 ACM Doctoral Dissertation Award.
Together with Paul Goldberg and Christos Papadimitriou, they received the 2008 Game Theory and Computer Science Prize for their paper "The Complexity of Computing a Nash Equilibrium". He became a tenured Professor at MIT in May 2015. Constantinos Daskalakis won the 2008 Doctoral Dissertation Award from ACM for advancing our understanding of behavior in complex networks of interacting individuals, such as those enabled and created by the Internet, his dissertation, entitled “The Complexity of Nash Equilibria,” provides a novel, algorithmic perspective on Game Theory and the concept of the Nash equilibrium. For this work Daskalakis was awarded the 2008 Kalai Prize for outstanding articles at the interface of computer science and game theory, along with Christos Papadimitriou and Paul W. Goldberg. In 2018, Daskalakis was awarded the Nevanlinna Prize for "transforming our understanding of the computational complexity of fundamental problems in markets, auctions and other economic structures", he received the Simons Foundation Investigator award in Theoretical Computer Science, an award designed for "outstanding scientists in their most productive years," who are "providing leadership to the field".
Personal page Constantinos Daskalakis publications indexed by Google Scholar Constantinos Daskalakis publications indexed by the Scopus bibliographic database
William Henry Gates III is an American business magnate, author and humanitarian. He is best known as the principal founder of Microsoft Corporation. During his career at Microsoft, Gates held the positions of chairman, CEO and chief software architect, while being the largest individual shareholder until May 2014. In 1975, Gates and Paul Allen launched Microsoft, which became the world's largest PC software company. Gates led the company as chief executive officer until stepping down in January 2000, but he remained as chairman and created the position of chief software architect for himself. In June 2006, Gates announced that he would be transitioning from full-time work at Microsoft to part-time work and full-time work at the Bill & Melinda Gates Foundation, the private charitable foundation that he and his wife, Melinda Gates, established in 2000, he transferred his duties to Ray Ozzie and Craig Mundie. He stepped down as chairman of Microsoft in February 2014 and assumed a new post as technology adviser to support the newly appointed CEO Satya Nadella.
Gates is one of the best-known entrepreneurs of the personal computer revolution. He has been criticized for his business tactics; this opinion has been upheld by numerous court rulings. Since 1987, Gates has been included in the Forbes list of the world's wealthiest people, an index of the wealthiest documented individuals and ranking against those with wealth, not able to be ascertained. From 1995 to 2017, he held the Forbes title of the richest person in the world all but four of those years, held it from March 2014 to July 2017, with an estimated net worth of US$89.9 billion as of October 2017. However, on July 27, 2017, since October 27, 2017, he has been surpassed by Amazon founder and CEO Jeff Bezos, who had an estimated net worth of US$90.6 billion at the time. As of August 6, 2018, Gates had a net worth of $95.4 billion, making him the second-richest person in the world, behind Bezos. In his career and since leaving Microsoft, Gates pursued a number of philanthropic endeavors, he donated large amounts of money to various charitable organizations and scientific research programs through the Bill & Melinda Gates Foundation, reported to be the world's largest private charity.
In 2009, Gates and Warren Buffett founded The Giving Pledge, whereby they and other billionaires pledge to give at least half of their wealth to philanthropy. The foundation works to save lives and improve global health, is working with Rotary International to eliminate polio. Gates was born in Seattle, Washington, on October 28, 1955, he is the son of Mary Maxwell Gates. His ancestry includes English, German and Scots-Irish, his father was a prominent lawyer, his mother served on the board of directors for First Interstate BancSystem and the United Way. Gates' maternal grandfather was J. W. Maxwell, a national bank president. Gates has one older sister, a younger sister, Libby, he is the fourth of his name in his family, but is known as William Gates III or "Trey" because his father had the "II" suffix. The family lived in the Sand Point area of Seattle in a home, once damaged by a rare tornado when Gates was seven years old. Early on in his life, Gates observed; when Gates was young, his family attended a church of the Congregational Christian Churches, a Protestant Reformed denomination.
The family encouraged competition. There was always a reward for winning and there was always a penalty for losing". At 13, he enrolled in the Lakeside School, a private preparatory school and wrote his first software program; when Gates was in the eighth grade, the Mothers' Club at the school used proceeds from Lakeside School's rummage sale to buy a Teletype Model 33 ASR terminal and a block of computer time on a General Electric computer for the school's students. Gates took an interest in programming the GE system in BASIC, was excused from math classes to pursue his interest, he wrote his first computer program on this machine: an implementation of tic-tac-toe that allowed users to play games against the computer. Gates was fascinated by the machine; when he reflected back on that moment, he said, "There was just something neat about the machine." After the Mothers Club donation was exhausted, he and other students sought time on systems including DEC PDP minicomputers. One of these systems was a PDP-10 belonging to Computer Center Corporation, which banned four Lakeside students – Gates, Paul Allen, Ric Weiland, Kent Evans – for the summer after it caught them exploiting bugs in the operating system to obtain free computer time.
At the end of the ban, the four students offered to find bugs in CCC's software in exchange for extra computer time. Rather than use the system via Teletype, Gates went to CCC's offices and studied source code for various programs that ran on the system, including programs in Fortran and machine language; the arrangement with CCC continued until 1970. The following year, Information Sciences, Inc. hired the four Lakeside students to write a payroll program in COBOL, providing them computer time and royalties. After his administrators became aware of his programming abilities, Gates wrote the school's student information system software to schedule students in classes, he modified the code so that he was placed in classes with "a disproportionate number of interesting girls." He stated that "it
Leland Stanford Junior University is a private research university in Stanford, California. Stanford is known for its academic strength, proximity to Silicon Valley, ranking as one of the world's top universities; the university was founded in 1885 by Leland and Jane Stanford in memory of their only child, Leland Stanford Jr. who had died of typhoid fever at age 15 the previous year. Stanford was a U. S. Senator and former Governor of California who made his fortune as a railroad tycoon; the school admitted its first students on October 1, 1891, as a coeducational and non-denominational institution. Stanford University struggled financially after the death of Leland Stanford in 1893 and again after much of the campus was damaged by the 1906 San Francisco earthquake. Following World War II, Provost Frederick Terman supported faculty and graduates' entrepreneurialism to build self-sufficient local industry in what would be known as Silicon Valley; the university is one of the top fundraising institutions in the country, becoming the first school to raise more than a billion dollars in a year.
The university is organized around three traditional schools consisting of 40 academic departments at the undergraduate and graduate level and four professional schools that focus on graduate programs in Law, Medicine and Business. Stanford's undergraduate program is the most selective in the United States by acceptance rate. Students compete in 36 varsity sports, the university is one of two private institutions in the Division I FBS Pac-12 Conference, it has gained the most for a university. Stanford athletes have won 512 individual championships, Stanford has won the NACDA Directors' Cup for 24 consecutive years, beginning in 1994–1995. In addition, Stanford students and alumni have won 270 Olympic medals including 139 gold medals; as of October 2018, 83 Nobel laureates, 27 Turing Award laureates, 8 Fields Medalists have been affiliated with Stanford as students, faculty or staff. In addition, Stanford University is noted for its entrepreneurship and is one of the most successful universities in attracting funding for start-ups.
Stanford alumni have founded a large number of companies, which combined produce more than $2.7 trillion in annual revenue and have created 5.4 million jobs as of 2011 equivalent to the 10th largest economy in the world. Stanford is the alma mater of 30 living billionaires and 17 astronauts, is one of the leading producers of members of the United States Congress. Stanford University was founded in 1885 by Leland and Jane Stanford, dedicated to Leland Stanford Jr, their only child; the institution opened in 1891 on Stanford's previous Palo Alto farm. Despite being impacted by earthquakes in both 1906 and 1989, the campus was rebuilt each time. In 1919, The Hoover Institution on War and Peace was started by Herbert Hoover to preserve artifacts related to World War I; the Stanford Medical Center, completed in 1959, is a teaching hospital with over 800 beds. The SLAC National Accelerator Laboratory, established in 1962, performs research in particle physics. Jane and Leland Stanford modeled their university after the great eastern universities, most Cornell University and Harvard University.
Stanford opened being called the "Cornell of the West" in 1891 due to faculty being former Cornell affiliates including its first president, David Starr Jordan. Both Cornell and Stanford were among the first to have higher education be accessible and open to women as well as to men. Cornell is credited as one of the first American universities to adopt this radical departure from traditional education, Stanford became an early adopter as well. Most of Stanford University is on one of the largest in the United States, it is located on the San Francisco Peninsula, in the northwest part of the Santa Clara Valley 37 miles southeast of San Francisco and 20 miles northwest of San Jose. In 2008, 60% of this land remained undeveloped. Stanford's main campus includes a census-designated place within unincorporated Santa Clara County, although some of the university land is within the city limits of Palo Alto; the campus includes much land in unincorporated San Mateo County, as well as in the city limits of Menlo Park and Portola Valley.
The academic central campus is adjacent to Palo Alto, bounded by El Camino Real, Stanford Avenue, Junipero Serra Boulevard, Sand Hill Road. The United States Postal Service has assigned it two ZIP Codes: 94305 for campus mail and 94309 for P. O. box mail. It lies within area code 650. Stanford operates or intends to operate in various locations outside of its central campus. On the founding grant: Jasper Ridge Biological Preserve is a 1,200-acre natural reserve south of the central campus owned by the university and used by wildlife biologists for research. SLAC National Accelerator Laboratory is a facility west of the central campus operated by the university for the Department of Energy, it contains the longest linear particle accelerator in the world, 2 miles on 426 acres of land. Golf course and a seasonal lake: The university has its own golf course and a seasonal lake, both home to the vulnerable California tiger salamander; as of 2012 Lake Laguni
Logicomix: An Epic Search for Truth is a graphic novel about the foundational quest in mathematics, written by Apostolos Doxiadis, author of Uncle Petros and Goldbach's Conjecture, theoretical computer scientist Christos Papadimitriou of the University of California, Berkeley. Character design and artwork are by Alecos Papadatos and color is by Annie Di Donna; the book was written in English, was translated into Greek by author Apostolos Doxiadis for the release in Greece, which preceded the UK and U. S. releases. Set between the late 19th century and the present day, the graphic novel Logicomix is based on the story of the so-called "foundational quest" in mathematics. Logicomix intertwines the philosophical struggles with the characters' own personal turmoil; these are in turn played out just upstage of the momentous historical events of the era and the ideological battles which gave rise to them. The narrator of the story is Bertrand Russell, who stands as an icon of many of these themes: a sensitive and introspective man, Russell was not just a philosopher and pacifist, he was one of the prominent figures in the foundational quest.
Russell's life story, depicted by Logicomix, is itself a journey through the goals and struggles, triumph and tragedy shared by many great thinkers of the 20th century: Georg Cantor, Ludwig Wittgenstein, G. E. Moore, Alfred North Whitehead, David Hilbert, Gottlob Frege, Henri Poincaré, Kurt Gödel, Alan Turing. A parallel tale, set in present-day Athens, records the creators’ disagreement on the meaning of the story, thus setting in relief the foundational quest as a quintessentially modern adventure, it is on the one hand a tragedy of the hubris of rationalism, which descends inextricably on madness, on the other an origin myth of the computer. In chronological order: Greece – October 20, 2008, Ikaros Publications, ISBN 978-960-8399-67-9 Netherlands – August 15, 2009, De Vliegende Hollander, ISBN 978-90-495-0079-5 United Kingdom – September 7, 2009, Bloomsbury, ISBN 0-7475-9720-0 United States – September 29, 2009, Bloomsbury USA, ISBN 1-59691-452-1 France – May 10, 2010, Vuibert, ISBN 978-2-7117-4351-3 Italy – June 10, 2010, Guanda, ISBN 978-88-6088-168-7 Germany – August 30, 2010, Atrium-Verlag, ISBN 978-3-85535-069-8 Finland – September 10, 2010, Avain, ISBN 978-951-692-786-5 Brazil – 2010, Martins Fontes, ISBN 978-85-7827-278-4 Croatia - 2010, Logicomix Print Ltd. / Mate d.o.o.
ISBN 978-953-246-119-0 Spain – March 24, 2011, Ediciones Sins Entido, ISBN 978-84-96722-74-3 Norway – 2010, Arneberg, ISBN 978-82-8220-028-8 Poland – November 2011, W. A. B. ISBN 978-83-7747-535-5 Denmark – February 2012, Politisk Revy, ISBN 978-87-7378-325-2 Czech Republic – September 2012, Dokoran, ISBN 978-80-7363-401-8 Turkey – October 2012, Albatros Kitap, ISBN 978-975-906-7151 Russia – March 2014, Kar'era Press, ISBN 978-5-904946-70-8 Iran – March 2014, Fatemi Publishing Co. ISBN 978-964-318-755-2 Israel – 2016, Aliyat Hagag press, ISBN 978-965-545-071-2 Jim Holt reviewed the book for the New York Times and says the story "is presented with real graphic verve." Although he does note "one serious misstep" involving the overplaying of the impact Russell's paradox had on mathematics. A review at The Guardian said that the "authors tell the story with a humour and lightness of touch that pokes fun at the philosophers and mathematicians involved, but never trivialises the philosophy or the mathematics" concluding that "Doxiadis has shown that by using fiction to provide an emotional context to mathematical discoveries it can make for a gripping read.
Uncle Petros was a bestseller and the much more ambitious Logicomix deserves to be one too."The book was recommended by the New Statesman in late September. On October 2 the book made the New York Times, Sunday Book Review, Editor's Choice list and the next week it was #1 on the NYT Graphic Novel Best Seller list; the book sold out on the day it was released in the United States and United Kingdom, got into the Top 10 on Amazon.com and Amazon.co.uk, leading the manager of a major Athens bookstore to say "No Greek book has sold abroad like this in 30 years." According to Paolo Mancosu, the authors "admittedly take liberties with the real course of events", for example with reference to the alleged meetings Russell would have had with Frege and Cantor. Although "such departures from reality can be fruitful for narrative purposes", according to Mancosu, in some cases they are objectionable, as the portrayal of Frege as a "rabid paranoid antisemite", the "constant refrain of the alleged causal link between logic and madness".
From "the conceptual point of view, some of the major ideas about the foundation of mathematics are conveyed with reasonable accuracy", although sometimes errors and inaccuracies occur. However, the global judgement by Mancosu is positive: I enjoyed reading Logicomix immensely; the authors have tackled an complicated subject with thought provoking ideas in an aesthetically pleasing and entertaining fashion. Thus, my few critical remarks should not mislead you. I recommend Logicomix though my recommendation is qualified: the reader should provide his/her grain of salt. "A labor of love completed". Athens Plus. 2008-10-24. P. 14. Psaropoulos, John. "Beauty is truth, truth beauty". Athens News. Athens: Myenpi Publishing. Retrieved 22 October 2010. Logicomix at the Comic Book DB Official website Unusual Greek math comic tops bestseller lists worldwide, Deutsche Welle, October 12, 2009 Logicomix, en epic search for truth Making of Logicomix Math, Philosophy and Bertrand Russell’s Search for Truth, Publishers Weekly, April 14, 2009
Computer science is the study of processes that interact with data and that can be represented as data in the form of programs. It enables the use of algorithms to manipulate and communicate digital information. A computer scientist studies the theory of computation and the practice of designing software systems, its fields can be divided into practical disciplines. Computational complexity theory is abstract, while computer graphics emphasizes real-world applications. Programming language theory considers approaches to the description of computational processes, while computer programming itself involves the use of programming languages and complex systems. Human–computer interaction considers the challenges in making computers useful and accessible; the earliest foundations of what would become computer science predate the invention of the modern digital computer. Machines for calculating fixed numerical tasks such as the abacus have existed since antiquity, aiding in computations such as multiplication and division.
Algorithms for performing computations have existed since antiquity before the development of sophisticated computing equipment. Wilhelm Schickard designed and constructed the first working mechanical calculator in 1623. In 1673, Gottfried Leibniz demonstrated a digital mechanical calculator, called the Stepped Reckoner, he may be considered the first computer scientist and information theorist, among other reasons, documenting the binary number system. In 1820, Thomas de Colmar launched the mechanical calculator industry when he released his simplified arithmometer, the first calculating machine strong enough and reliable enough to be used daily in an office environment. Charles Babbage started the design of the first automatic mechanical calculator, his Difference Engine, in 1822, which gave him the idea of the first programmable mechanical calculator, his Analytical Engine, he started developing this machine in 1834, "in less than two years, he had sketched out many of the salient features of the modern computer".
"A crucial step was the adoption of a punched card system derived from the Jacquard loom" making it infinitely programmable. In 1843, during the translation of a French article on the Analytical Engine, Ada Lovelace wrote, in one of the many notes she included, an algorithm to compute the Bernoulli numbers, considered to be the first computer program. Around 1885, Herman Hollerith invented the tabulator, which used punched cards to process statistical information. In 1937, one hundred years after Babbage's impossible dream, Howard Aiken convinced IBM, making all kinds of punched card equipment and was in the calculator business to develop his giant programmable calculator, the ASCC/Harvard Mark I, based on Babbage's Analytical Engine, which itself used cards and a central computing unit; when the machine was finished, some hailed it as "Babbage's dream come true". During the 1940s, as new and more powerful computing machines were developed, the term computer came to refer to the machines rather than their human predecessors.
As it became clear that computers could be used for more than just mathematical calculations, the field of computer science broadened to study computation in general. In 1945, IBM founded the Watson Scientific Computing Laboratory at Columbia University in New York City; the renovated fraternity house on Manhattan's West Side was IBM's first laboratory devoted to pure science. The lab is the forerunner of IBM's Research Division, which today operates research facilities around the world; the close relationship between IBM and the university was instrumental in the emergence of a new scientific discipline, with Columbia offering one of the first academic-credit courses in computer science in 1946. Computer science began to be established as a distinct academic discipline in the 1950s and early 1960s; the world's first computer science degree program, the Cambridge Diploma in Computer Science, began at the University of Cambridge Computer Laboratory in 1953. The first computer science degree program in the United States was formed at Purdue University in 1962.
Since practical computers became available, many applications of computing have become distinct areas of study in their own rights. Although many believed it was impossible that computers themselves could be a scientific field of study, in the late fifties it became accepted among the greater academic population, it is the now well-known IBM brand that formed part of the computer science revolution during this time. IBM released the IBM 704 and the IBM 709 computers, which were used during the exploration period of such devices. "Still, working with the IBM was frustrating if you had misplaced as much as one letter in one instruction, the program would crash, you would have to start the whole process over again". During the late 1950s, the computer science discipline was much in its developmental stages, such issues were commonplace. Time has seen significant improvements in the effectiveness of computing technology. Modern society has seen a significant shift in the users of computer technology, from usage only by experts and professionals, to a near-ubiquitous user base.
Computers were quite costly, some degree of humanitarian aid was needed for efficient use—in part from professional computer operators. As computer adoption became more widespread and affordable, less human assistance was needed for common usage. Despite its short history as a formal academic discipline, computer science has made a number of fundamental contributions to science and society—in fact, along with electronics, it is
Paris Christos Kanellakis was a Greek American computer scientist. Kanellakis was born on December 3, 1953 in Athens as the only child of General Eleftherios and Mrs. Argyroula Kanellakis. In 1976, he received a diploma in electrical engineering from the National Technical University of Athens, with a thesis supervised by Emmanuel Protonotarios, he continued his studies at the graduate level in electrical engineering and computer science at the Massachusetts Institute of Technology. He received his M. Sc. degree in 1978. His thesis Algorithms for a scheduling application of the Asymmetric Traveling Salesman Problem was supervised by Ron Rivest and Michael Athans, although Christos Papadimitriou was involved, he continued working for his Ph. D. with Papadimitriou as advisor. He submitted his thesis The complexity of concurrency control for distributed databases in September 1981, he was awarded the doctorate degree in February 1982. In 1981, he joined the Computer Science Department at Brown University as assistant professor.
He obtained tenure as associate professor in 1986, became full professor in 1990. He interrupted his stay at Brown in 1984 for a junior sabbatical as visiting assistant professor at the MIT Laboratory for Computer Science, working with Nancy Lynch, in 1988 for a year at INRIA on special assignment leave, working with Serge Abiteboul. Between 1982 and 1991, he paid several short visits to the IBM T. J. Watson Research Center, his awards include a Sloan Research Fellowship in mathematics. During 1989-90, he was IBM Associate Professor of Computer Science, he was born a Greek citizen, obtained U. S. citizenship in 1988. Kanellakis died on December 20, 1995 together with his wife, Maria Teresa Otoya, their two children and Stephanos, in the crash of American Airlines Flight 965 while en route to an annual holiday reunion with his wife's family, his scientific contributions lie in the fields of database theory—comprising work on deductive databases, object-oriented databases, constraint databases—as well as in fault-tolerant distributed computation and in type theory.
While at Brown, he supervised seven Ph. D. theses there and one at MIT. He participated in the program committees of numerous editions of international meetings, including PODS, VLDB, LICS, STOC, FOCS, STACS, PODC, he served as editorial advisor to the scientific journals Information and Computation, SIAM Journal on Computing, Theoretical Computer Science, ACM Transactions on Database Systems, Journal of Logic Programming, Chicago Journal of Theoretical Computer Science, Applied Mathematics Letters. Together with Alex Shvartsman, they co-authored the monograph Fault-Tolerant Parallel Computation. At the time of his death, the book was still incomplete. In 1996, the Association for Computing Machinery instituted the Paris Kanellakis Theory and Practice Award, granted yearly to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". Past recipients include Leonard Adleman, Whitfield Diffie, Martin Hellman, Ralph Merkle, Ron Rivest, Adi Shamir,Abraham Lempel and Jacob Ziv,Randy Bryant, Edmund Clarke, E. Allen Emerson, Ken McMillan,Danny Sleator and Robert Tarjan,Narendra Karmarkar,Eugene Myers,Peter Franaszek,Gary Miller, Michael Rabin, Robert Solovay, Volker Strassen,Yoav Freund and Robert Schapire,Gerard Holzmann, Robert Kurshan, Moshe Vardi, Pierre Wolper,Robert Brayton,Bruno Buchberger,Corinna Cortes and Vladimir Vapnik,Mihir Bellare and Phillip Rogaway,Kurt Mehlhorn,Hanan Samet,Andrei Broder, Moses Charikar, Piotr Indyk, Robert Blumofe and Charles Leiserson.
After donations from Kanellakis's parents, three graduate fellowships and a prize have been established in his memory at the three institutions where he studied and worked: Brown, MIT, NTUA. Since 1997, the Department of Computer Science at Brown has been offering two Paris Kanellakis Fellowships every year, each of which lasts for one year and is awarded preferably to graduate students from Greece. Past recipients include Christos Amanatidis, Aris Anagnostopoulos, Alexandru Balan, Foteini Baldimtsi, Glencora L. Borradaile, Costas Busch, Irina Calciu, Daniel Acevedo Feliz, Esha Gosh, Arjun Guha, Serdar Kadioglu, Evgenios Kornaropoulos, Hammurabi Mendes, Michail Michailidis, Tomer Moscovich, Shay Mozes, Olga Ohrimenko, Olga Papaemmanouil, Charalampos Papamanthou, Alexandra Papoutsaki, Eric Ely Rachlin, Emmanuel Renieris, Warren Schudy, Nikos Triandopoulos, Ioannis Tsochantaridis, Aggeliki Tsoli, Ioannis Vergados. Since 1999, the Department of Electrical Engineering and Computer Science at MIT has been offering one Paris Kanellakis Fellowship every year, which lasts for one year and is awarded to a graduate student, either Greek or American of Greek descent.
Past recipients include Nikolaos Andrikogiannopoulos, Georgios Angelopoulos, Christos Mario Christoudias, Apostolos Fertis, Vasileios-Marios Gkortsas, Themistoklis Gouleakis, Manolis Kamvysselis, Christos Kapoutsis, Aristeidis Karalis, Georgia-Evangelia Katsargyri, Georgios Papachristoudis, Anastasios Sidiropoulos, Katerina Sotiraki, Christos Tzamos. Since 2000, NTUA has been offering one Paris Kanellakis Prize every year, awarded to the student of the School of Electrical and Computer Engineering who earns the greatest GPA over all courses of the third and fourth years of study in the field of Information Technol