|
PPAD
In computer science, PPAD ("Polynomial Parity Arguments on Directed graphs") is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument. The class attracted significant attention in the field of algorithmic game theory because it contains the problem of computing a Nash equilibrium: this problem was shown to be complete for PPAD by Daskalakis, Goldberg and Papadimitriou with at least 3 players and later extended by Chen and Deng to 2 players.*. Definition PPAD is a subset of the class TFNP, the class of function problems in FNP that are guaranteed to be total. The TFNP formal definition is given as follows: :A binary relation P(''x'',''y'') is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(''x'',''y'') holds given both ''x'' and ''y'', and for every ''x'', there exists a ''y'' such that P(''x'',''y'') holds. Subclas ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
TFNP
In computational complexity theory, the complexity class TFNP is the class of total function problems which can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial". TFNP contains many natural problems that are of interest to computer scientists. These problems include integer factorization, finding a Nash Equilibrium of a game, and searching for local optima. TFNP is widely conjectured to contain problems that are computationally intractable, and several such problems have been shown to be hard under cryptographic assumptions. However, there are no known unconditional intractability results or results showing NP-hardness of TFNP problems. TFNP is not believed to have any complete problems.Goldberg ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PPP (complexity)
In computational complexity theory, the complexity class PPP (polynomial pigeonhole principle) is a subclass of TFNP. It is the class of search problems that can be shown to be total by an application of the pigeonhole principle. Christos Papadimitriou introduced it in the same paper that introduced PPAD and PPA. PPP contains both PPAD and PWPP (polynomial weak pigeonhole principle) as subclasses. These complexity classes are of particular interest in cryptography because they are strongly related to cryptographic primitives such as one-way permutations and collision-resistant hash functions. Definition PPP is the set of all function computation problems that admit a polynomial-time reduction to the ''PIGEON'' problem, defined as follows: :Given a Boolean circuit C having the same number n of input bits as output bits, find either an input x that is mapped to the output C(x) = 0^n, or two distinct inputs x \ne y that are mapped to the same output C(x) = C(y). A problem is PPP-co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PPA (complexity)
In computational complexity theory, PPA is a complexity class, standing for "Polynomial Parity Argument" (on a graph). Introduced by Christos Papadimitriou in 1994 (page 528), PPA is a subclass of TFNP. It is a class of search problems that can be shown to be total by an application of the handshaking lemma: ''any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number''. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist (so, we have a total search problem). Definition PPA is defined as follows. Suppose we have a graph on whose vertices are n-bit binary strings, and the graph is represented by a polynomial-sized circuit that takes a vertex as input and outputs its neighbors. (Note that this allows us to represent an exponentially-large graph on which we can efficiently pe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algorithmic Game Theory
Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments. Typically, in Algorithmic Game Theory problems, the input to a given algorithm is distributed among many players who have a personal interest in the output. In those situations, the agents might not report the input truthfully because of their own personal interests. We can see Algorithmic Game Theory from two perspectives: * ''Analysis'': given the currently implemented algorithms, analyze them using Game Theory tools (e.g., calculate and prove properties on their Nash equilibria, price of anarchy, and best-response dynamics) * ''Design'': design games that have both good game-theoretical and algorithmic properties. This area is called algorithmic mechanism design. On top of the usual requirements in classical algorithm design (e.g., ''polynomial-time running time'', ''good approximation ratio), ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sperner's Lemma
In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring (described below) of a triangulation of an simplex contains a cell whose vertices all have different colors. The initial result of this kind was proved by Emanuel Sperner, in relation with proofs of invariance of domain. Sperner colorings have been used for effective computation of fixed points and in root-finding algorithms, and are applied in fair division (cake cutting) algorithms. Finding a Sperner coloring or equivalently a Brouwer fixed point is now believed to be an intractable computational problem, even in the plane, in the general case. The problem is PPAD-complete, a complexity class invented by Christos Papadimitriou. According to the Soviet ''Mathematical Encyclopaedia'' (ed. I.M. Vinogradov), a related 1929 theorem (of Knaster, Borsuk and Mazurkiewicz) had als ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
FNP (complexity)
In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is somewhat of a misnomer, since technically it is a class of binary relations, not functions, as the following formal definition explains: :A binary relation P(''x'',''y''), where ''y'' is at most polynomially longer than ''x'', is in FNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(''x'',''y'') holds given both ''x'' and ''y''. This definition does not involve nondeterminism and is analogous to the verifier definition of NP. There is an NP language directly corresponding to every FNP relation, sometimes called the decision problem ''induced by'' or ''corresponding to'' said FNP relation. It is the language formed by taking all the ''x'' for which P(''x'',''y'') holds given some ''y''; however, there may be more than one FNP relation for a particular decision problem. Many problems in NP, in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-free Cake-cutting
An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation. When there are only two partners, the problem is easy and was solved in antiquity by the divide and choose protocol. When there are three or more partners, the problem becomes much more challenging. Two major variants of the problem have been studied: * Connected pieces, e.g. if the cake is a 1-dimensional interval then each partner must receive a single sub-interval. If there are n partners, only n-1 cuts are needed. * General pieces, e.g. if the cake is a 1-dimensional interval then each partner can receive a union of disjoint sub-intervals. Short history Modern research into the fair cake-cutting problem started in the 1940s. The first fairness criterion studied was proportional divi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Function Problem
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'. Formal definition A functional problem P is defined as a relation R over strings of an arbitrary alphabet \Sigma: : R \subseteq \Sigma^* \times \Sigma^*. An algorithm solves P if for every input x such that there exists a y satisfying (x, y) \in R, the algorithm produces one such y. Examples A well-known function problem is given by the Functional Boolean Satisfiability Problem, FSAT for short. The problem, which is closely related to the SAT decision problem, can be formulated as follows: :Given a boolean formula \varphi with variables x_1, \ldots, x_n, find an assignment x_i \rightarrow \ such that \varphi evaluates to \text or decide that no such assignment exists. In this case the relation R ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nash Equilibria
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs. If each player has chosen a strategy an action plan based on what has happened so far in the game and no one can increase one's own expected payoff by changing one's strategy while the other players keep their's unchanged, then the current set of strategy choices constitutes a Nash equilibrium. If two players Alice and Bob choose strategies A and B, (A, B) is a Nash equilibrium if Alice has no other strategy available that does better than A at maximizing her payoff in response to Bob choosing B, and Bob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Xi Chen
Xi Chen (Chinese: 陈汐) is a computer scientist. He is an associate professor of computer science at Columbia University. Chen won the 2021 Gödel Prize and Fulkerson Prize for his co-authored paper "Complexity of Counting CSP with Complex Weights" with Jin-Yi Cai. Biography Chen received his B.S. and Ph.D. from Tsinghua University. He was a postdoctoral fellow at Institute for Advanced Study, Princeton University, University of Southern California, and joined the Columbia faculty in 2011. Chen's research focuses on computational complexity theory. He also received a Presburger Award from the European Association for Theoretical Computer Science in 2015 and a Sloan Research Fellowship The Sloan Research Fellowships are awarded annually by the Alfred P. Sloan Foundation since 1955 to "provide support and recognition to early-career scientists and scholars". This program is one of the oldest of its kind in the United States. ... in 2012. References Living peo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Christos Papadimitriou
Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University. Education Papadimitriou studied at the National Technical University of Athens, where in 1972 he received his Bachelor of Arts degree in electrical engineering. He then pursued graduate studies at Princeton University, where he received his Ph.D. in electrical engineering and computer science in 1976 after completing a doctoral dissertation titled "The complexity of combinatorial optimization problems." Career Papadimitriou has taught at Harvard, MIT, the National Technical University of Athens, Stanford, UCSD, University of California, Berkeley and is currently the Donovan Family Professor of Computer Science at Columbia University. Papadimitriou co-authored a paper on pancake sorting with Bill Gates, then a Harvard undergra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SICOMP
The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ''SIAM J. Comput.'', its publisher and contributors frequently use the shorter abbreviation ''SICOMP''. SICOMP typically hosts the special issues of the IEEE Annual Symposium on Foundations of Computer Science (FOCS) and the Annual ACM Symposium on Theory of Computing (STOC), where about 15% of papers published in FOCS and STOC each year are invited to these special issues. For example, Volume 48 contains 11 out of 85 papers published in FOCS 2016. References * External linksSIAM Journal on Computing on |
