|
EATCS-IPEC Nerode Prize
The EATCS–IPEC Nerode Prize is a theoretical computer science prize awarded for outstanding research in the area of multivariate algorithmics. It is awarded by the European Association for Theoretical Computer Science and the International Symposium on Parameterized and Exact Computation. The prize was offered for the first time in 2013.. Winners The prize winners so far have been: *2013: Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi, and Francis Zane, for their research formulating the exponential time hypothesis and using it to determine the exact parameterized complexity of several important variants of the Boolean satisfiability problem. *2014: Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin, Lance Fortnow, and Rahul Santhanam, for their work on kernelization, proving that several problems with fixed-parameter tractable algorithms do not have polynomial-size kernels unless the polynomial hierarchy collapses. *2015: Erik ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science
Theoretical 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 Association for Computing Machinery, ACM's ACM SIGACT, 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 Hebbian learning, learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mohammad Hajiaghayi
, birth_date = , birth_place = , death_place = , nationality = , fields = Computer science , workplaces = University of Maryland, College Park , alma_mater = Massachusetts Institute of Technology (PhD) , doctoral_advisor = Erik Demaine F. Thomson Leighton , doctoral_students = , awards = Guggenheim Fellowship (2019) Blavatnik National Awards for Young Scientists (2020) EATCS Fellow (2020) IEEE Fellow (2019) ACM Fellow (2018) EATCS Nerode Prize (2015) , website = Mohammad Taghi Hajiaghayi ( fa, محمد تقی حاجی آقائی) is a computer scientist known for his work in algorithms, game theory, social networks, network design, graph theory, and big data.. He has over 200 publications with over 185 collaborators and 10 issued patents. He is the Jack and Rita G. Minker Professor at the University of Maryland Department of Computer Science. Professional career Hajiaghayi received his PhD in applie ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
List Of Computer Science Awards
This list of computer science awards is an index to articles on notable awards related to computer science. It includes lists of awards by the Association for Computing Machinery, the Institute of Electrical and Electronics Engineers, other computer science and information science awards, and a list of computer science competitions. The top computer science award is the ACM Turing Award, generally regarded as the Nobel Prize equivalent for Computer Science. Other highly regarded top computer science awards include IEEE John von Neumann Medal awarded by the IEEE Board of Directors, and the Japan Kyoto Prize for Information Science. Association for Computing Machinery The Association for Computing Machinery (ACM) gives out many computer science awards, often run by one of their Special Interest Groups. IEEE A number of awards are given by the Institute of Electrical and Electronics Engineers (IEEE), the IEEE Computer Society or the IEEE Information Theory Society. Other comput ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Monadic Second-order Logic
In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's theorem, which provides algorithms for evaluating monadic second-order formulas over graphs of bounded treewidth. It is also of fundamental importance in automata theory, where the Büchi-Elgot-Trakhtenbrot theorem gives a logical characterization of the regular languages. Second-order logic allows quantification over predicates. However, MSO is the fragment in which second-order quantification is limited to monadic predicates (predicates having a single argument). This is often described as quantification over "sets" because monadic predicates are equivalent in expressive power to sets (the set of elements for which the predicate is true). Variants Monadic second-order logic comes in two variants. In the variant considered over str ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Parity Games
A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owner of the node that the token falls on selects the successor node, resulting in a (possibly infinite) path, called the play. The winner of a finite play is the player whose opponent is unable to move. The winner of an infinite play is determined by the priorities appearing in the play. Typically, player 0 wins an infinite play if the largest priority that occurs infinitely often in the play is even. Player 1 wins otherwise. This explains the word "parity" in the title. Parity games lie in the third level of the Borel hierarchy, and are consequently determined. Games related to parity games were implicitly used in Rabin's proof of decidability of the monadic second-order theory of ''n'' successors ( S2S for ''n'' = 2), where determinacy ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quasipolynomial Time Algorithm
In mathematics, a quasi-polynomial (pseudo-polynomial) is a generalization of polynomials. While the coefficients of a polynomial come from a ring, the coefficients of quasi-polynomials are instead periodic functions with integral period. Quasi-polynomials appear throughout much of combinatorics as the enumerators for various objects. A quasi-polynomial can be written as q(k) = c_d(k) k^d + c_(k) k^ + \cdots + c_0(k), where c_i(k) is a periodic function with integral period. If c_d(k) is not identically zero, then the degree of q is d. Equivalently, a function f \colon \mathbb \to \mathbb is a quasi-polynomial if there exist polynomials p_0, \dots, p_ such that f(n) = p_i(n) when i \equiv n \bmod s. The polynomials p_i are called the constituents of f. Examples * Given a d-dimensional polytope P with rational vertices v_1,\dots,v_n, define tP to be the convex hull of tv_1,\dots,tv_n. The function L(P,t) = \#(tP \cap \mathbb^d) is a quasi-polynomial in t of degree d. In this case, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Color-coding
In computer science and graph theory, the term color-coding refers to an algorithmic technique which is useful in the discovery of network motifs. For example, it can be used to detect a simple path of length in a given graph. The traditional color-coding algorithm is probabilistic, but it can be derandomized without much overhead in the running time. Color-coding also applies to the detection of cycles of a given length, and more generally it applies to the subgraph isomorphism problem (an NP-complete problem), where it yields polynomial time algorithms when the subgraph pattern that it is trying to detect has bounded treewidth. The color-coding method was proposed and analyzed in 1994 by Noga Alon, Raphael Yuster, and Uri Zwick.Alon, N., Yuster, R., and Zwick, U. 1995. Color-coding. J. ACM 42, 4 (Jul. 1995), 844–856. DOI= http://doi.acm.org/10.1145/210332.210337 Results The following results can be obtained through the method of color-coding: * For every fixed cons ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Uri Zwick
Uri Zwick is an Israeli computer scientist and mathematician known for his work on graph algorithms, in particular on distances in graphs and on the color-coding technique for subgraph isomorphism. With Howard Karloff, he is the namesake of the Karloff–Zwick algorithm for approximating the MAX-3SAT problem of Boolean satisfiability. He and his coauthors won the David P. Robbins Prize in 2011 for their work on the block-stacking problem. Zwick earned a bachelor's degree from the Technion – Israel Institute of Technology, and completed his doctorate at Tel Aviv University in 1989 under the supervision of Noga Alon Noga Alon ( he, נוגה אלון; born 17 February 1956) is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of .... He is currently a professor of computer science at Tel Aviv University. References External linksHome page* {{D ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Noga Alon
Noga Alon ( he, נוגה אלון; born 17 February 1956) is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers. Academic background Alon is a Professor of Mathematics at Princeton University and a Baumritter Professor Emeritus of Mathematics and Computer Science at Tel Aviv University, Israel. He graduated from the Hebrew Reali School in 1974 and received his Ph.D. in Mathematics at the Hebrew University of Jerusalem in 1983 and had visiting positions in various research institutes including MIT, The Institute for Advanced Study in Princeton, IBM Almaden Research Center, Bell Labs, Bellcore and Microsoft Research. He serves on the editorial boards of more than a dozen international journals; since 2008 he is the editor-in-chief of ''Random Structures and Algorithms''. He has given lectures in many conferences, including plenary addresses ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Odd Cycle Transversal
In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph. Relation to vertex cover A given n-vertex graph G has an odd cycle transversal of size k, if and only if the Cartesian product of graphs G\square K_2 (a graph consisting of two copies of G, with corresponding vertices of each copy connected by the edges of a perfect matching) has a vertex cover of size n+k. The odd cycle transversal can be transformed into a vertex cover by including both copies of each vertex from the transversal and one copy of each remaining vertex, selected from the two copies according to which side of the bipartition contains it. In the other direction, a vertex cover of G\square K_2 can be transformed into an odd cycle transversal by keeping only the vertices for which bot ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite matroid is equivalent to a geometric lattice. Matroid theory borrows extensively from the terminology of both linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications in geometry, topology, combinatorial optimization, network theory and coding theory. Definition There are many equivalent ( cryptomorphic) ways to define a (finite) matroid.A standard source for basic definitions and results about matroids is Oxley (1992). An older standard source is Welsh (1976). See Brylawsk ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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). Both problems are NP-complete. The Hamiltonian cycle problem is a special case of the travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to ''n'' (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer). Reduction between the path problem and the cycle problem The problems of finding a Hamiltonian path and a Hamiltonian cycle can be related as follows: * In one direction, the Hamiltonian path problem for graph ''G'' can be related to the Hamiltonian cycle problem in a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
