Sergio Rajsbaum (born March 3, 1962, in Mexico City, Mexico) is a Mexican computer scientist, working in the field of Theoretical Computer Science, specifically concurrent and distributed computing.
He is a Professor of the Instituto de Matemáticas of Universidad Nacional Autónoma de México, where he has been a member of the faculty since 1991.
He was a visiting researcher of Institut de recherche en informatique fondamentale (IRIF) on a Sabbatical academic year 2022 to 2023.. [1] [2]
Rajsbaum was educated at the Facultad de Ingeniería of UNAM, earning a B.S. in computer engineering in 1985.
Rajsbaum obtained his PhD from the Technion, Israel in 1991, with thesis Synchronization in Distributed Networks written under the direction of Shimon Even. His thesis introduced the unison problem . [2]
He did postdoctoral studies from 1993 to 1995 at the Massachusetts Institute of Technology under Nancy Lynch. The research resulted in contributions to three topics. A method to computing the achievable clock synchronization precision based on the communication and individual clock drift bounds of a given network. A simulation [3] for direct translations of algorithms and impossibility results from a model with some resiliency to a model with a different resiliency. The study of the deep connection between distributed computing and algebraic topology, [4] an example of the interplay between mathematics and computation [5]
The collaboration that started in 1994 with Maurice Herlihy was the beginning of a research project that has lasted over 30 years, and overviewed in the book "Distributed Computing Through Combinatorial Topology", which they wrote together with mathematician Dmitry Feichtner-Kozlov. The topological perspective has gone beyond distributed computing [6] leading to work in combinatorial topology [7] and directed topology, [8] and connections with logic, runtime verification, and social choice theory.
With his co-workers, Rajsbaum received Best Paper Awards at the following scientific conferences. DISC (2011) for his paper "Locality and Checkability in Wait-Free computing" and SSS (2019) for his paper "Synchronous t-Resilient Consensus in Arbitrary Graphs".
His work "New combinatorial topology bounds for renaming: the upper bound" with his PhD student Armando Castañeda was recognized in the ACM Notable Computing Books and Articles of 2012 and received the Best Student Paper Award at PODC (2008).
His book "Distributed Computing Through Combinatorial Topology" was selected as a Notable Book on the Best of Computing 2013 list by the Association for Computing Machinery.
Rajsbaum received the Premio Nacional de Computación 2022 by the Academia Mexicana de Computación.
His Erdös number is 2 because Rajsbaum is coauthor of Shlomo Moran, who is coauthor of Paul Erdös.
Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers.
In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.
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. 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.
Metaheuristic in computer science and mathematical optimization is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. Metaheuristics sample a subset of solutions which is otherwise too large to be completely enumerated or otherwise explored. Metaheuristics may make relatively few assumptions about the optimization problem being solved and so may be usable for a variety of problems. Their use is always of interest when exact or other (approximate) methods are not available or are not expedient, either because the calculation time is too long or because, for example, the solution provided is too imprecise.
In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the boolean satisfiability problem is NP-complete to show that there is a polynomial time many-one reduction from the boolean satisfiability problem to each of 21 combinatorial and graph theoretical computational problems, thereby showing that they are all NP-complete. This was one of the first demonstrations that many natural computational problems occurring throughout computer science are computationally intractable, and it drove interest in the study of NP-completeness and the P versus NP problem.
In computational complexity theory, the unique games conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP, then for many important problems it is not only impossible to get an exact solution in polynomial time, but also impossible to get a good polynomial-time approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.
Shlomi Dolev is a Rita Altura Trust Chair Professor in Computer Science at Ben-Gurion University of the Negev (BGU) and the head of the BGU Negev Hi-Tech Faculty Startup Accelerator.
Vijay Virkumar Vazirani is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine.
In mathematics, the unknotting problem is the problem of algorithmically recognizing the unknot, given some representation of a knot, e.g., a knot diagram. There are several types of unknotting algorithms. A major unresolved challenge is to determine if the problem admits a polynomial time algorithm; that is, whether the problem lies in the complexity class P.
A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.
Digital topology deals with properties and features of two-dimensional (2D) or three-dimensional (3D) digital images that correspond to topological properties or topological features of objects.
Maurice Peter Herlihy is an American computer scientist active in the field of multiprocessor synchronization. Herlihy has contributed to areas including theoretical foundations of wait-free synchronization, linearizable data structures, applications of combinatorial topology to distributed computing, as well as hardware and software transactional memory. He is the An Wang Professor of Computer Science at Brown University, where he has been a member of the faculty since 1994.
Kurt Mehlhorn is a German theoretical computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science.
Larry Joseph Stockmeyer was an American computer scientist. He was one of the pioneers in the field of computational complexity theory, and he also worked in the field of distributed computing. He died of pancreatic cancer.
Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.
Michel Raynal is a French informatics scientist, professor at IRISA, University of Rennes, France. He is known for his contributions in the fields of algorithms, computability, and fault-tolerance in the context of concurrent and distributed systems. Michel Raynal is also Distinguished Chair professor at the Hong Kong Polytechnic University and editor of the “Synthesis Lectures on Distributed Computing Theory” published by Morgan & Claypool. He is a senior member of Institut Universitaire de France and a member of Academia Europaea.
Roger Wattenhofer, born in 1969, is a Swiss computer scientist, active in the field of distributed computing, networking, and algorithms. He is a professor at ETH Zurich (Switzerland) since 2001. He has published numerous research articles in computer science and a book on Bitcoin.
Dmitry Feichtner-Kozlov is a Russian-German mathematician.
In economics, a budget-additive valuation is a kind of a utility function. It corresponds to a person that, when given a set of items, evaluates them in the following way:
In algorithmic game theory, a branch of both computer science and economics, a demand oracle is a function that, given a price-vector, returns the demand of an agent. It is used by many algorithms related to pricing and optimization in online market. It is usually contrasted with a value oracle, which is a function that, given a set of items, returns the value assigned to them by an agent.
| International | |
|---|---|
| National | |
| Academics | |
| People | |
| Other | |
 | This article needs additional or more specific categories .(May 2023) |
