|
Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory ( ACM SIGACT). The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time. The Gödel Prize has been awarded since 1993. The prize is awarded either at STOC (ACM Symposium on Theory of Computing, one of the main North American conferences in theoretical computer science) or ICALP ( International Colloquium on Automata, Languages and Programming, one of the main European conferences in the field). To be eligible for the prize, a paper must be published ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the theoretical areas precisely. The ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description: History While logical inference and mathematical proof had existed previously, in 1931 Kurt Gödel proved with his incompleteness theorem that there are fundamental limitations on what statements could be proved or disproved. Information theory was added to the field with a 1948 mathematical theory of communication by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of neural networks and parallel distributed processing were established. I ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Silvio Micali
Silvio Micali (born October 13, 1954) is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand. Micali's research centers on cryptography and information security. In 2012, he received the Turing Award for his work in cryptography. Personal life Micali graduated in mathematics at La Sapienza University of Rome in 1978 and earned a PhD degree in computer science from the University of California, Berkeley in 1982; for research supervised by Manuel Blum. Micali has been on the faculty at MIT, Electrical Engineering and Computer Science Department, since 1983. His research interests are cryptography, zero knowledge, pseudorandom generation, secure protocols, and mechanism design. Career Micali is best known for some of his fundamental early work on public-key cryptosystems, pseudorandom functions, digital signatures, oblivious transfer, secure multiparty computation, and is one of the co-inventors of zero-knowledge ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Immerman–Szelepcsényi Theorem
In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE(''s''(''n'')) = co-NSPACE(''s''(''n'')) for any function ''s''(''n'') ≥ log ''n''. The result is equivalently stated as NL = co-NL; although this is the special case when ''s''(''n'') = log ''n'', it implies the general theorem by a standard padding argument. The result solved the second LBA problem. In other words, if a nondeterministic machine can solve a problem, another machine with the same resource bounds can solve its complement problem (with the ''yes'' and ''no'' answers reversed) in the same asymptotic amount of space. No similar result is known for the time complexity classes, and indeed it is conjectured that NP is not equal t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Róbert Szelepcsényi
Róbert Szelepcsényi (; born 19 August 1966, Žilina) is a Slovak computer scientist of Hungarian descent and a member of the Faculty of Mathematics, Physics and Informatics of Comenius University in Bratislava. His results on the closure of non-deterministic space under complement, independently obtained in 1987 also by Neil Immerman (the result known as the Immerman–Szelepcsényi theorem), brought the Gödel Prize of ACM and EATCS to both of them in 1995. Scientific articles * Róbert Szelepcsényi: The Method of Forced Enumeration for Nondeterministic Automata. ''Acta Informatica ''Acta Informatica'' is a peer-reviewed scientific journal publishing original research papers in computer science. The journal is known mostly for publications in theoretical computer science. One of the two 1988 papers awarded the Gödel Prize ...'' 26(3): 279-284 (1988) References Slovak computer scientists Hungarian computer scientists 20th-century Hungarian mathematicians 21 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Neil Immerman
Neil Immerman (born 24 November 1953, Manhasset, New York) is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst.Faculty directory: Neil Immerman Computer Science Department, , retrieved 2010-01-23. He is one of the key developers of , an approach he is currently applying to research in model checking, database theory, and computational complexity theory. Professor Immerman is an ed ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Parity Function
In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function. The parity function is notable for its role in theoretical investigation of circuit complexity of Boolean functions. The output of the parity function is the parity bit. Definition The n-variable parity function is the Boolean function f:\^n\to\ with the property that f(x)=1 if and only if the number of ones in the vector x\in\^n is odd. In other words, f is defined as follows: :f(x)=x_1\oplus x_2 \oplus \dots \oplus x_n where \oplus denotes exclusive or. Properties Parity only depends on the number of ones and is therefore a symmetric Boolean function. The ''n''-variable parity function and its negation are the only Boolean functions for which all disjunctive normal forms have the maximal number of 2 ''n'' − 1 monomials of length ''n'' and all conjunc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Boolean Circuits
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model of computation, model for combinational logic, combinational digital electronics, digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length. Boolean circuits are defined in terms of the logic gates they contain. For example, a circuit might contain binary function, binary AND and OR gates and unary operation, unary NOT gates, or be entirely described by binary NAND gates. Each gate corresponds to some Boolean function that takes a fixed number of bits as input and outputs a single bit. Boolean circuits provide a model for many digital components used in computer engineering, including multiplexers, adder (electronics), adders, and arithmetic logic units, but they exclude sequential logic. They are an abstraction that omits many aspects relevant to designing real digital logic circuits, such as metastabilit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Circuit Complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits C_,C_,\ldots (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a prominent circuit class P/poly consists of Boolean functions computable by circuits of polynomial size. Proving that \mathsf\not\subseteq \mathsf would separate P and NP (see below). Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly. Size and depth A Boolean circuit with n input bits is a directed acyclic graph in which every node (usually called ''gates'' in this context) is either an input node of in-degree 0 lab ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lower Bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an element of that is less than or equal to every element of . A set with an upper (respectively, lower) bound is said to be bounded from above or majorized (respectively bounded from below or minorized) by that bound. The terms bounded above (bounded below) are also used in the mathematical literature for sets that have upper (respectively lower) bounds. Examples For example, is a lower bound for the set (as a subset of the integers or of the real numbers, etc.), and so is . On the other hand, is not a lower bound for since it is not smaller than every element in . The set has as both an upper bound and a lower bound; all other numbers are either an upper bound or a lower bound for that . Every subset of the natural numbers has a lo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Johan Håstad
Johan Torkel Håstad (; born 19 November 1960) is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation Award in 1986, among other prizes. He has been a professor in theoretical computer science at KTH Royal Institute of Technology in Stockholm, Sweden since 1988, becoming a full professor in 1992. He is a member of the Royal Swedish Academy of Sciences since 2001. He received his B.S. in Mathematics at Stockholm University in 1981, his M.S. in Mathematics at Uppsala University in 1984 and his Ph.D. in Mathematics from MIT in 1986. Håstad's thesis and 1994 Gödel Prize concerned his work on lower bounds on the size of constant-depth Boolean circuits for the parity function. After Andrew Yao proved that such circuits require exponential size, Håstad proved nearly optimal lower bounds on the necessary size through his switching lemma, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIAM Journal On Computing
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 DBLP [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Journal Of Computer And System Sciences
The ''Journal of Computer and System Sciences'' (JCSS) is a peer-reviewed scientific journal in the field of computer science. ''JCSS'' is published by Elsevier, and it was started in 1967. Many influential scientific articles have been published in ''JCSS''; these include five papers that have won the Gödel Prize. an 2014 Gödel Prize Its managing editor is |
