Faster access than browser!
83 relations: Alecos Papadatos, Algorithm characterizations, Algorithmic game theory, Alternating Turing machine, Apostolos Doxiadis, École Polytechnique Fédérale de Lausanne, Bill Gates, Bland's rule, BPP (complexity), Canadian traveller problem, Charging argument, Chris Umans, Computability, Configuration graph, Constantinos Daskalakis, Ellipsoid method, Epsilon-equilibrium, European Association for Theoretical Computer Science, Fast Fourier transform, Federated Computing Research Conference, Gödel Prize, Go and mathematics, Greece, Greeks, Hamiltonian path problem, Harry R. Lewis, IEEE John von Neumann Medal, Interactive proof system, International Parallel and Distributed Processing Symposium, Jayme Luiz Szwarcfiter, Joseph S. B. Mitchell, K-server problem, Kalai Prize, Kenneth Steiglitz, Knuth Prize, Lemke–Howson algorithm, Linear programming, Linear speedup theorem, List of comic books, List of computer scientists, List of Fellows of the Association for Computing Machinery, List of Greek Americans, List of Greeks, List of important publications in theoretical computer science, List of members of the National Academy of Engineering (Computer science), List of members of the National Academy of Sciences (computer and information sciences), List of people by Erdős number, List of PPAD-complete problems, List of PSPACE-complete problems, List of University of California, Berkeley faculty, ..., Logicomix, Ludwig Wittgenstein, Max-flow min-cut theorem, Member of the Academia Europaea, Mihalis Yannakakis, National Technical University of Athens, NEXPTIME, NL-complete, Non-deterministic Turing machine, One-way function, Pancake graph, Pancake sorting, Papadimitriou, Paris Kanellakis, Parity P, Polynomial hierarchy, PPA (complexity), PPAD (complexity), PPP (complexity), Pursuit-evasion, Randomized algorithm, Sharp-P-completeness of 01-permanent, Simplex algorithm, SL (complexity), SNP (complexity), Sperner's lemma, Stathis Zachos, Symmetric Turing machine, Time hierarchy theorem, Turing machine, Turing machine equivalents, UC Berkeley College of Engineering, Witsenhausen's counterexample. Expand index (33 more) »
Alecos Papadatos
Alecos Papadatos (Alexandros Papadatos, Alekos Papadatos; Αλέκος Παπαδάτος; born 1959) is a Greek comic book writer and illustrator, best known as the artist of Logicomix, a graphic novel written by Apostolos Doxiadis and Christos Papadimitriou.
New!!: Christos Papadimitriou and Alecos Papadatos · See more »
Algorithm characterizations
Algorithm characterizations are attempts to formalize the word algorithm.
New!!: Christos Papadimitriou and Algorithm characterizations · See more »
Algorithmic game theory
Algorithmic game theory is an area in the intersection of game theory and computer science, whose objective is to understand and design algorithms in strategic environments.
New!!: Christos Papadimitriou and Algorithmic game theory · See more »
Alternating Turing machine
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP.
New!!: Christos Papadimitriou and Alternating Turing machine · See more »
Apostolos Doxiadis
Apostolos K. Doxiadis (Απόστολος Κ. Δοξιάδης; born 1953) is a Greek writer.
New!!: Christos Papadimitriou and Apostolos Doxiadis · See more »
École Polytechnique Fédérale de Lausanne
The École polytechnique fédérale de Lausanne (EPFL) is a research institute and university in Lausanne, Switzerland, that specializes in natural sciences and engineering.
New!!: Christos Papadimitriou and École Polytechnique Fédérale de Lausanne · See more »
Bill Gates
William Henry Gates III (born October 28, 1955) is an American business magnate, investor, author, philanthropist, humanitarian, and principal founder of Microsoft Corporation.
New!!: Christos Papadimitriou and Bill Gates · See more »
Bland's rule
In mathematical optimization, Bland's rule (also known as Bland's algorithm or Bland's anti-cycling rule) is an algorithmic refinement of the simplex method for linear optimization.
New!!: Christos Papadimitriou and Bland's rule · See more »
BPP (complexity)
In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/2 for all instances.
New!!: Christos Papadimitriou and BPP (complexity) · See more »
Canadian traveller problem
In computer science and graph theory, the Canadian traveller problem (CTP) is a generalization of the shortest path problem to graphs that are partially observable.
New!!: Christos Papadimitriou and Canadian traveller problem · See more »
Charging argument
In computer science, a charging argument is used to compare the output of an optimization algorithm to an optimal solution.
New!!: Christos Papadimitriou and Charging argument · See more »
Chris Umans
Christopher Umans is Professor of computer science in the Computing and Mathematical Sciences Department at the California Institute of Technology.
New!!: Christos Papadimitriou and Chris Umans · See more »
Computability
Computability is the ability to solve a problem in an effective manner.
New!!: Christos Papadimitriou and Computability · See more »
Configuration graph
Configuration graphs are a theoretical tool used in computational complexity theory to prove a relation between graph reachability and complexity classes.
New!!: Christos Papadimitriou and Configuration graph · See more »
Constantinos Daskalakis
Constantinos Daskalakis (born 1981) is a Professor at MIT's Electrical Engineering and Computer Science department and a member of CSAIL.
New!!: Christos Papadimitriou and Constantinos Daskalakis · See more »
Ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions.
New!!: Christos Papadimitriou and Ellipsoid method · See more »
Epsilon-equilibrium
In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium.
New!!: Christos Papadimitriou and Epsilon-equilibrium · See more »
European Association for Theoretical Computer Science
The European Association for Theoretical Computer Science (EATCS) is an international organization with a European focus, founded in 1972.
New!!: Christos Papadimitriou and European Association for Theoretical Computer Science · See more »
Fast Fourier transform
A fast Fourier transform (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components.
New!!: Christos Papadimitriou and Fast Fourier transform · See more »
Federated Computing Research Conference
The Federated Computing Research Conference, FCRC, is an event that brings together several academic conferences, workshops, and plenary talks in the field of computer science.
New!!: Christos Papadimitriou and Federated Computing Research Conference · See more »
Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT).
New!!: Christos Papadimitriou and Gödel Prize · See more »
Go and mathematics
The game of Go is one of the most popular games in the world.
New!!: Christos Papadimitriou and Go and mathematics · See more »
Greece
No description.
New!!: Christos Papadimitriou and Greece · See more »
Greeks
The Greeks or Hellenes (Έλληνες, Éllines) are an ethnic group native to Greece, Cyprus, southern Albania, Italy, Turkey, Egypt and, to a lesser extent, other countries surrounding the Mediterranean Sea. They also form a significant diaspora, with Greek communities established around the world.. Greek colonies and communities have been historically established on the shores of the Mediterranean Sea and Black Sea, but the Greek people have always been centered on the Aegean and Ionian seas, where the Greek language has been spoken since the Bronze Age.. Until the early 20th century, Greeks were distributed between the Greek peninsula, the western coast of Asia Minor, the Black Sea coast, Cappadocia in central Anatolia, Egypt, the Balkans, Cyprus, and Constantinople. Many of these regions coincided to a large extent with the borders of the Byzantine Empire of the late 11th century and the Eastern Mediterranean areas of ancient Greek colonization. The cultural centers of the Greeks have included Athens, Thessalonica, Alexandria, Smyrna, and Constantinople at various periods. Most ethnic Greeks live nowadays within the borders of the modern Greek state and Cyprus. The Greek genocide and population exchange between Greece and Turkey nearly ended the three millennia-old Greek presence in Asia Minor. Other longstanding Greek populations can be found from southern Italy to the Caucasus and southern Russia and Ukraine and in the Greek diaspora communities in a number of other countries. Today, most Greeks are officially registered as members of the Greek Orthodox Church.CIA World Factbook on Greece: Greek Orthodox 98%, Greek Muslim 1.3%, other 0.7%. Greeks have greatly influenced and contributed to culture, arts, exploration, literature, philosophy, politics, architecture, music, mathematics, science and technology, business, cuisine, and sports, both historically and contemporarily.
New!!: Christos Papadimitriou and Greeks · See more »
Hamiltonian path problem
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected).
New!!: Christos Papadimitriou and Hamiltonian path problem · See more »
Harry R. Lewis
Lewis has been honored for his "particularly distinguished contributions to undergraduate teaching"; his students have included future entrepreneurs Bill Gates and Mark Zuckerberg, and numerous future faculty members at Harvard and other schools.
New!!: Christos Papadimitriou and Harry R. Lewis · See more »
IEEE John von Neumann Medal
The IEEE John von Neumann Medal was established by the IEEE Board of Directors in 1990 and may be presented annually "for outstanding achievements in computer-related science and technology." The achievements may be theoretical, technological, or entrepreneurial, and need not have been made immediately prior to the date of the award.
New!!: Christos Papadimitriou and IEEE John von Neumann Medal · See more »
Interactive proof system
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties.
New!!: Christos Papadimitriou and Interactive proof system · See more »
International Parallel and Distributed Processing Symposium
The International Parallel and Distributed Processing Symposium (or IPDPS) is an annual conference for engineers and scientists to present recent findings in the fields of parallel processing and distributed computing.
New!!: Christos Papadimitriou and International Parallel and Distributed Processing Symposium · See more »
Jayme Luiz Szwarcfiter
Jayme Luiz Szwarcfiter (born July 5, 1942 in Rio de Janeiro) is a computer scientist in Brazil.
New!!: Christos Papadimitriou and Jayme Luiz Szwarcfiter · See more »
Joseph S. B. Mitchell
Joseph S. B. Mitchell is an American computer scientist and mathematician.
New!!: Christos Papadimitriou and Joseph S. B. Mitchell · See more »
K-server problem
The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems).
New!!: Christos Papadimitriou and K-server problem · See more »
Kalai Prize
The Prize in Game Theory and Computer Science in Honour of Ehud Kalai is an award given by the Game Theory Society.
New!!: Christos Papadimitriou and Kalai Prize · See more »
Kenneth Steiglitz
Dr.
New!!: Christos Papadimitriou and Kenneth Steiglitz · See more »
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.
New!!: Christos Papadimitriou and Knuth Prize · See more »
Lemke–Howson algorithm
The Lemke–Howson algorithm is an algorithm that computes a Nash equilibrium of a bimatrix game, named after its inventors, Carlton E. Lemke and J. T. Howson.
New!!: Christos Papadimitriou and Lemke–Howson algorithm · See more »
Linear programming
Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.
New!!: Christos Papadimitriou and Linear programming · See more »
Linear speedup theorem
In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any Turing machine solving a problem in time f(n), there is another machine that solves the same problem in time at most cf(n) + n + 2.
New!!: Christos Papadimitriou and Linear speedup theorem · See more »
List of comic books
This is a list of comic books, by country.
New!!: Christos Papadimitriou and List of comic books · See more »
List of computer scientists
This is a list of computer scientists, people who do work in computer science, in particular researchers and authors.
New!!: Christos Papadimitriou and List of computer scientists · See more »
List of Fellows of the Association for Computing Machinery
This article lists ACM Fellows, an award and fellowship granted by the Association for Computing Machinery (ACM) as its highest honorary grade of membership, reserved for ACM members who have exhibited "professional excellence" in their "technical, professional and leadership contributions" Since 1993, the people that have been elected as Fellows are listed below.
New!!: Christos Papadimitriou and List of Fellows of the Association for Computing Machinery · See more »
List of Greek Americans
The following is a list of notable Greek Americans, including both original immigrants of Greek descent who obtained American citizenship and their American descendants.
New!!: Christos Papadimitriou and List of Greek Americans · See more »
List of Greeks
This is a list of notable Greeks.
New!!: Christos Papadimitriou and List of Greeks · See more »
List of important publications in theoretical computer science
This is a list of important publications in theoretical computer science, organized by field.
New!!: Christos Papadimitriou and List of important publications in theoretical computer science · See more »
List of members of the National Academy of Engineering (Computer science)
This list is a subsection of the List of members of the National Academy of Engineering, which includes over 2,000 current members of the United States National Academy of Engineering, each of whom is affiliated with one of 12 disciplinary sections.
New!!: Christos Papadimitriou and List of members of the National Academy of Engineering (Computer science) · See more »
List of members of the National Academy of Sciences (computer and information sciences)
*National Academy of Sciences (Computer and information sciences) Category:Lists of computer scientists.
New!!: Christos Papadimitriou and List of members of the National Academy of Sciences (computer and information sciences) · See more »
List of people by Erdős number
Paul Erdős (1913–1996) was the most prolifically published mathematician of all time.
New!!: Christos Papadimitriou and List of people by Erdős number · See more »
List of PPAD-complete problems
This is a list of PPAD-complete problems.
New!!: Christos Papadimitriou and List of PPAD-complete problems · See more »
List of PSPACE-complete problems
Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems.
New!!: Christos Papadimitriou and List of PSPACE-complete problems · See more »
List of University of California, Berkeley faculty
This page lists notable faculty (past and present) of the University of California, Berkeley.
New!!: Christos Papadimitriou and List of University of California, Berkeley faculty · See more »
Logicomix
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, and theoretical computer scientist Christos Papadimitriou of the University of California, Berkeley.
New!!: Christos Papadimitriou and Logicomix · See more »
Ludwig Wittgenstein
Ludwig Josef Johann Wittgenstein (26 April 1889 – 29 April 1951) was an Austrian-British philosopher who worked primarily in logic, the philosophy of mathematics, the philosophy of mind, and the philosophy of language.
New!!: Christos Papadimitriou and Ludwig Wittgenstein · See more »
Max-flow min-cut theorem
In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the ''source'' to the ''sink'' is equal to the total weight of the edges in the minimum cut, i.e. the smallest total weight of the edges which if removed would disconnect the source from the sink.
New!!: Christos Papadimitriou and Max-flow min-cut theorem · See more »
Member of the Academia Europaea
Membership of the Academia Europaea (MAE) is an award conferred by the Academia Europaea to individuals that have demonstrated “sustained academic excellence”.
New!!: Christos Papadimitriou and Member of the Academia Europaea · See more »
Mihalis Yannakakis
Mihalis Yannakakis (Μιχάλης Γιαννακάκης; born 13 September 1953 in Athens, Greece) (accessed 12 November 2009) is Professor of Computer Science at Columbia University.
New!!: Christos Papadimitriou and Mihalis Yannakakis · See more »
National Technical University of Athens
The National (Metsovian) Technical University of Athens (NTUA; Εθνικό Μετσόβιο Πολυτεχνείο, National Metsovian Polytechnic), sometimes known as Athens Polytechnic, is among the oldest higher education institutions of Greece and the most prestigious among engineering schools.
New!!: Christos Papadimitriou and National Technical University of Athens · See more »
NEXPTIME
In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2n O(1).
New!!: Christos Papadimitriou and NEXPTIME · See more »
NL-complete
In computational complexity theory, NL-complete is a complexity class containing the languages that are complete for NL, the class of decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.
New!!: Christos Papadimitriou and NL-complete · See more »
Non-deterministic Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers.
New!!: Christos Papadimitriou and Non-deterministic Turing machine · See more »
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input.
New!!: Christos Papadimitriou and One-way function · See more »
Pancake graph
In the mathematical field of graph theory, the pancake graph Pn or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals.
New!!: Christos Papadimitriou and Pancake graph · See more »
Pancake sorting
Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it.
New!!: Christos Papadimitriou and Pancake sorting · See more »
Papadimitriou
Papadimitriou (Greek: Παπαδημητρίου) is a Greek surname that may refer to.
New!!: Christos Papadimitriou and Papadimitriou · See more »
Paris Kanellakis
Paris Christos Kanellakis (Πάρις Χρήστος Κανελλάκης; December 3, 1953 – December 20, 1995) was a Greek American computer scientist.
New!!: Christos Papadimitriou and Paris Kanellakis · See more »
Parity P
In computational complexity theory, the complexity class ⊕P (pronounced "parity P") is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd.
New!!: Christos Papadimitriou and Parity P · See more »
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.
New!!: Christos Papadimitriou and Polynomial hierarchy · See more »
PPA (complexity)
In computational complexity theory, PPA is a complexity class, standing for "Polynomial Parity Argument" (on a graph).
New!!: Christos Papadimitriou and PPA (complexity) · See more »
PPAD (complexity)
In computer science, PPAD ("Polynomial Parity Arguments on Directed graphs") is a complexity class introduced by Christos Papadimitriou in 1994.
New!!: Christos Papadimitriou and PPAD (complexity) · See more »
PPP (complexity)
PPP is a complexity class, standing for "Polynomial Pigeonhole Principle".
New!!: Christos Papadimitriou and PPP (complexity) · See more »
Pursuit-evasion
Pursuit-evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment.
New!!: Christos Papadimitriou and Pursuit-evasion · See more »
Randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.
New!!: Christos Papadimitriou and Randomized algorithm · See more »
Sharp-P-completeness of 01-permanent
The #P-completeness of 01-permanent, sometimes known as Valiant's theorem,Christos H. Papadimitriou.
New!!: Christos Papadimitriou and Sharp-P-completeness of 01-permanent · See more »
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
New!!: Christos Papadimitriou and Simplex algorithm · See more »
SL (complexity)
In computational complexity theory, SL (Symmetric Logspace or Sym-L) is the complexity class of problems log-space reducible to USTCON (undirected s-t connectivity), which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component.
New!!: Christos Papadimitriou and SL (complexity) · See more »
SNP (complexity)
In computational complexity theory, SNP (from Strict NP) is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties.
New!!: Christos Papadimitriou and SNP (complexity) · See more »
Sperner's lemma
In mathematics, Sperner's lemma is a combinatorial analog of the Brouwer fixed point theorem, which is equivalent to it.
New!!: Christos Papadimitriou and Sperner's lemma · See more »
Stathis Zachos
Stathis K. Zachos (Στάθης (Ευστάθιος) Ζάχος; born 1947 in Athens) is a mathematician, logician and theoretical computer scientist.
New!!: Christos Papadimitriou and Stathis Zachos · See more »
Symmetric Turing machine
A symmetric Turing machine is a Turing machine which has a configuration graph that is undirected (that is, configuration i yields configuration j if and only if j yields i).
New!!: Christos Papadimitriou and Symmetric Turing machine · See more »
Time hierarchy theorem
In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines.
New!!: Christos Papadimitriou and Time hierarchy theorem · See more »
Turing machine
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.
New!!: Christos Papadimitriou and Turing machine · See more »
Turing machine equivalents
A Turing machine is a hypothetical computing device, first conceived by Alan Turing in 1936.
New!!: Christos Papadimitriou and Turing machine equivalents · See more »
UC Berkeley College of Engineering
The College of Engineering (CoE) is one of 14 schools and colleges at the University of California, Berkeley.
New!!: Christos Papadimitriou and UC Berkeley College of Engineering · See more »
Witsenhausen's counterexample
Witsenhausen's counterexample, shown in the figure below, is a deceptively simple toy problem in decentralized stochastic control.
New!!: Christos Papadimitriou and Witsenhausen's counterexample · See more »
Redirects here:
Christos H. Papadimitriou, Christos Harilaos Papadimitriou, Χρίστος Χαρίλαος Παπαδημητρίου.
References
[1] https://en.wikipedia.org/wiki/Christos_Papadimitriou
