|
Small Set Expansion Hypothesis
The small set expansion hypothesis or small set expansion conjecture in computational complexity theory is an unproven computational hardness assumption. Under the small set expansion hypothesis it is assumed to be computationally infeasible to distinguish between a certain class of expander graphs called "small set expanders" and other graphs that are very far from being small set expanders. This assumption implies the hardness of several other computational problems, and the optimality of certain known approximation algorithms. The small set expansion hypothesis is related to the unique games conjecture, another unproven computational hardness assumption according to which accurately approximating the value of certain games is computationally infeasible. If the small set expansion hypothesis is true, then so is the unique games conjecture. Background The ''edge expansion'' of a set X of vertices in a graph G is defined as \frac, where the vertical bars denote the number of el ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Complexity Theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. 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 also used, such as the amount of communication (used in communication complexity), the number of logic gate, gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). O ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Boaz Barak
Boaz Barak (Hebrew: בועז ברק, born 1974) is an Israeli-American professor of computer science at Harvard University. Early life and education He graduated in 1999 with a B.Sc. in mathematics and computer science from Tel Aviv University. In 2004, he received his Ph.D. from the Weizmann Institute of Science with thesis ''Non-Black-Box Techniques in Cryptography'' under the supervision of Oded Goldreich. Barak was at the Institute for Advanced Study for two years from 2003 to 2005. He was an assistant professor in the computer science department of Princeton University from 2005 to 2010 and an associate professor from 2010 to 2011. From 2010 to 2016, he was a researcher at Microsoft's New England research laboratory. Since 2016, he is the Gordon McKay Professor of Computer Science in the Harvard John A. Paulson School of Engineering and Applied Sciences. He is a citizen of both Israel and the United States. Career He co-authored, with Sanjeev Arora, ''Computational Complexi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete Applied Mathematics
''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split off from another Elsevier journal, ''Discrete Mathematics'', in 1979, with that journal's founder Peter Ladislaw Hammer as its founding editor-in-chief. Abstracting and indexing The journal is abstracted and indexing in: According to the ''Journal Citation Reports'', the journal has a 2020 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a type of journal ranking. Journals with higher impact factor values are considered more prestigious or important within their field. The Impact Factor of a journa ... of 1.139. References External links *{{official website, http://www.journals.elsevier.com/discrete-applied-mathematics/ Discrete mathematics journals Academic journals established in ... [...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 |
National Academy Of Sciences
The National Academy of Sciences (NAS) is a United States nonprofit, NGO, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the National Academy of Medicine (NAM). As a national academy, new members of the organization are elected annually by current members, based on their distinguished and continuing achievements in original research. Election to the National Academy is one of the highest honors in the scientific field in the United States. Member of the National Academy of Sciences, Members of the National Academy of Sciences serve ''pro bono'' as "advisers to the nation" on science, engineering, and medicine. The group holds a congressional charter under Title 36 of the United States Code. Congress legislated and President Abraham Lincoln signed an Act of Congress (1863) establishing the National Academy of Sciences as an independent, trusted nongovernmen ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
David Steurer
David Steurer is a German theoretical computer scientist, working in approximation algorithms, hardness of approximation, sum of squares, and high-dimensional statistics. He is an associate professor of computer science at ETH Zurich. Biography David Steurer studied for bachelor's and master's degrees at the University of Saarland (2003–2006), and went on to study at Princeton University, where he obtained his PhD under the supervision of Sanjeev Arora in 2010. He then spent two years as a postdoc at Microsoft Research New England, before joining Cornell University. In 2017 he moved to ETH Zurich ETH Zurich (; ) is a public university in Zurich, Switzerland. Founded in 1854 with the stated mission to educate engineers and scientists, the university focuses primarily on science, technology, engineering, and mathematics. ETH Zurich ran ..., where he became an associate professor in 2020. Work Steurer's work focuses on optimization using the Sum-of-squares optimization, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prasad Raghavendra
Prasad Raghavendra is an Indian-American theoretical computer scientist and mathematician, working in optimization, complexity theory, approximation algorithms, hardness of approximation and statistics. He is a professor of computer science at the University of California at Berkeley. Education After completing a BTech at IIT Madras in 2005, he obtained an MSc (2007) and PhD (2009) at the University of Washington under the supervision of Venkatesan Guruswami. After a postdoctoral position at Microsoft Research New England, he became faculty at the University of California at Berkeley. Career Raghavendra showed that assuming the unique games conjecture, semidefinite programming is the optimal algorithm for solving constraint satisfaction problems. Together with David Steurer, he developed the small set expansion hypothesis, for which they won the Michael and Shiela Held Prize in 2018. He developed sum of squares as a versatile algorithmic technique. Together with David Steu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Edge Cover
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is an endpoint of at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time. Definition Formally, an edge cover of a graph is a set of edges such that each vertex in is incident with at least one edge in . The set is said to ''cover'' the vertices of . The following figure shows examples of edge coverings in two graphs (the set is marked with red). : A minimum edge covering is an edge covering of smallest possible size. The edge covering number is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings (again, the set is marked with red). : Note that the figure on the right is not only an edge cover but also a matching. In particular, i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Bipartite Graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher. Llull himself had made similar drawings of complete graphs three centuries earlier.. Definition A complete bipartite graph is a graph whose vertices can be partitioned into two subsets and such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a bipartite graph such that for every two vertices and, is an edge in . A complete bipartite graph w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Approximation Ratio
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests A forest is an ecosystem characterized by a dense community of trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological functio .... An example of graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly are called '' -trees'', and the graphs with treewidth at most are called '' partial -trees''. Many other well-studied graph families also have bounded treewidth. Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sum-of-squares Optimization
A sum-of-squares optimization program is an optimization problem with a linear cost function and a particular type of constraint on the decision variables. These constraints are of the form that when the decision variables are used as coefficients in certain polynomials, those polynomials should have the polynomial SOS property. When fixing the maximum degree of the polynomials involved, sum-of-squares optimization is also known as the Lasserre hierarchy of relaxations in semidefinite programming. Sum-of-squares optimization techniques have been applied across a variety of areas, including control theory (in particular, for searching for polynomial Lyapunov functions for dynamical systems described by polynomial vector fields), statistics, finance and machine learning. Optimization problem Given a vector c\in \R^n and polynomials a_ for k=1, \dots N_s, j = 0, 1, \dots, n, a sum-of-squares optimization problem is written as \begin \underset \quad & c^T u \\ \text \quad & a_ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
