|
Ryan O'Donnell (computer Scientist)
Ryan O'Donnell is a Canadian theoretical computer scientist and a professor at Carnegie Mellon University. He is known for his work on the analysis of Boolean functions and for authoring the textbook on this subject. He is also known for his work on computational learning theory, hardness of approximation, property testing, quantum computation and quantum information. O'Donnell completed his B.Sc. in Mathematics and Computer Science at the University of Toronto. He then completed his Ph.D. at the Massachusetts Institute of Technology (MIT) in 2003, advised by Madhu Sudan. Research O'Donnell proved that the Goemans–Williamson approximation algorithm for MAX-CUT is optimal, assuming the unique games conjecture. The proof follows from two papers, one in 2004 with Subhash Khot, Guy Kindler, and Elchanan Mossel which reduced this statement to proving the Majority Is Stablest conjecture in analysis of Boolean functions, and one in 2005 with Elchanan Mossel and Krzysztof ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Analysis Of Boolean Functions
In mathematics and theoretical computer science, analysis of Boolean functions is the study of real-valued functions on \^n or \^n (such functions are sometimes known as pseudo-Boolean functions) from a spectral perspective. The functions studied are often, but not always, Boolean-valued, making them Boolean functions. The area has found many applications in combinatorics, social choice theory, random graphs, and theoretical computer science, especially in hardness of approximation, property testing, and PAC learning. Basic concepts We will mostly consider functions defined on the domain \^n. Sometimes it is more convenient to work with the domain \^n instead. If f is defined on \^n, then the corresponding function defined on \^n is :f_(x_1,\ldots,x_n) = f((-1)^,\ldots,(-1)^). Similarly, for us a Boolean function is a \-valued function, though often it is more convenient to consider \-valued functions instead. Fourier expansion Every real-valued function f\colon \^n \to \mathbb ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Semidefinite Programming
Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron. Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled or approximated as semidefinite programming problems. In automatic control theory, SDPs are used in the context of linear matrix inequalities. SDPs are in fact a special case of cone programming and can be efficiently solved by interior point methods. All linear programs and (convex) quadratic programs can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Semidefinite programming has been use ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Electronic Colloquium On Computational Complexity
The Electronic Colloquium on Computational Complexity (ECCC) is an electronic archive of research papers in computational complexity theory, a branch of computer science.... The intention of the ECCC is to provide a fast publication service intermediate in its level of peer review between preprint servers such as authors' web sites or arXiv (which release papers with little or no delay and filtering) and journals (which subject papers to a heavy editing process but, in computer science, may take months or years to publish a paper). Papers submitted to ECCC are screened by a board of experts, who review the submissions to ensure that they are on-topic, novel, interesting, and written according to the standards of the field. Any panelist may accept or reject any of the submissions; if no decision is made within two months, the submission is automatically rejected. In order to ensure the long-term stability of the archive, its contents are backed up by electronic media that are sent to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Simons Institute For The Theory Of Computing
The Simons Institute for the Theory of Computing at the University of California, Berkeley is an institute for collaborative research in theoretical computer science. History Established on July 1, 2012 with a grant of $60 million from the Simons Foundation, the Institute is housed in Calvin Lab, a dedicated building on the Berkeley campus. The Simons Institute brings together the leading researchers in theoretical computer science and related fields, as well as the next generation of outstanding young scholars, to explore deep unsolved problems about the nature and limits of computation. Richard M. Karp was Founding Director of the Institute, and fellow Turing Award winner Shafi Goldwasser took over as Director on January 1, 2018. Mission The Institute aims to promote fundamental research on the foundations of computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIAM Journal On Discrete Mathematics
'' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was established in 1988, along with the ''SIAM Journal on Matrix Analysis and Applications'', to replace the ''SIAM Journal on Algebraic and Discrete Methods''. The journal is indexed by ''Mathematical Reviews'' and Zentralblatt MATH. Its 2009 MCQ was 0.57. According to the ''Journal Citation Reports'', the journal has a 2016 impact factor of 0.755. Although its official ISO abbreviation is ''SIAM J. Discrete Math.'', its publisher and contributors frequently use the shorter abbreviation ''SIDMA''. References External links * Combinatorics journals Publications established in 1988 English-language journals Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way ana ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
List Of International Congresses Of Mathematicians Plenary And Invited Speakers
This is a list of International Congresses of Mathematicians Plenary and Invited Speakers. Being invited to talk at an International Congress of Mathematicians has been called "the equivalent, in this community, of an induction to a hall of fame." The current list of Plenary and Invited Speakers presented here is based on the ICM's post-WW II terminology, in which the one-hour speakers in the morning sessions are called "Plenary Speakers" and the other speakers (in the afternoon sessions) whose talks are included in the ICM published proceedings are called "Invited Speakers". In the pre-WW II congresses the Plenary Speakers were called "Invited Speakers". By congress year 1897, Zürich * Jules Andrade * Léon Autonne *Émile Borel * N. V. Bougaïev *Francesco Brioschi *Hermann Brunn *Cesare Burali-Forti *Charles Jean de la Vallée Poussin *Gustaf Eneström *Federigo Enriques *Gino Fano * Zoel García de Galdeano * Francesco Gerbaldi *Paul Gordan *Jacques Hadamard * Adolf Hurwitz ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. Fellowships were initially awarded in physics, chemistry, and mathematics. Awards were later added in neuroscience (1972), economics (1980), computer science (1993), computational and evolutionary molecular biology (2002), and ocean sciences or earth systems sciences (2012). Winners of these two-year fellowships are awarded $75,000, which may be spent on any expense supporting their research. From 2012 through 2020, the foundation awarded 126 research fellowship each year; in 2021, 128 were awarded, and 118 were awarded in 2022. Eligibility and selection To be eligible, a candidate must hold a Ph.D. or equivalent degree and must be a member of the faculty of a college, university, or other degree-granting institution in the United Stat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
National Science Foundation CAREER Award
The National Science Foundation CAREER awards, presented by the National Science Foundation (NSF), are in support of junior faculty who exemplify the role of teacher-scholars through research and education, and the integration of these endeavors in the context of their organizations' missions. The awards, presented once each year, include a federal grant for research and education activities for five consecutive years. History The Presidential Young Investigators (PYI) program was initiated in 1983, and remained active until the NSF New Young Investigators (NYI) program replaced it in 1992. Both programs were research-oriented, and funded an average of 200 faculty members per year. Another, more selective program began in 1992, when the White House asked NSF to institute the Presidential Faculty Fellows (PFF) program. It awarded young faculty up to $100,000 per year for five years, with no matching-fund option, and put more emphasis on education and outreach. In 1994, the Faculty ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quantum Tomography
Quantum tomography or quantum state tomography is the process by which a quantum state is reconstructed using measurements on an ensemble of identical quantum states. The source of these states may be any device or system which prepares quantum states either consistently into quantum pure states or otherwise into general mixed states. To be able to uniquely identify the state, the measurements must be tomographically complete. That is, the measured operators must form an operator basis on the Hilbert space of the system, providing all the information about the state. Such a set of observations is sometimes called a quorum. In quantum process tomography on the other hand, known quantum states are used to probe a quantum process to find out how the process can be described. Similarly, quantum measurement tomography works to find out what measurement is being performed. Whereas, randomized benchmarking scalably obtains a figure of merit of the overlap between the error prone ph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hales–Jewett Theorem
In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to be "completely random". An informal geometric statement of the theorem is that for any positive integers ''n'' and ''c'' there is a number ''H'' such that if the cells of a ''H''-dimensional ''n''×''n''×''n''×...×''n'' cube are colored with ''c'' colors, there must be one row, column, or certain diagonal (more details below) of length ''n'' all of whose cells are the same color. In other words, the higher-dimensional, multi-player, ''n''-in-a-row generalization of a game of tic-tac-toe cannot end in a draw, no matter how large ''n'' is, no matter how many people ''c'' are playing, and no matter which player plays each turn, provided only that it is played on a board of sufficiently high ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Elchanan Mossel
Elchanan Mossel ( he, אלחנן מוסל) is a professor of mathematics at the Massachusetts Institute of Technology. His primary research fields are probability theory, combinatorics, and statistical inference. Research Mossel's research spans a number of topics across mathematics, statistics, economics, and computer science, including combinatorial statistics, discrete function inequalities, isoperimetry, game theory, social choice, computational complexity, and computational evolutionary biology. His work on discrete Fourier analysis and functions with low influence includes important contributions such as the proof of the " Majority is Stablest" conjecture, together with Ryan O’Donnell and Krzysztof Oleszkiewicz, and the proof of the optimality of the Goemans–Williamson MAX-CUT algorithm (assuming the Unique Games Conjecture), with Subhash Khot, Guy Kindler and Ryan O’Donnell. Mossel has worked on the reconstruction problem on trees. He connected it to Steel's con ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
