Nati Linial

Last updated

Nathan (Nati) Linial (born 1953 in Haifa, Israel) [1] is an Israeli mathematician and computer scientist, a professor in the Rachel and Selim Benin School of Computer Science and Engineering at the Hebrew University of Jerusalem, [2] and an ISI highly cited researcher. [3]

Linial did his undergraduate studies at the Technion, and received his PhD in 1978 from the Hebrew University under the supervision of Micha Perles. [1] [4] He was a postgraduate researcher at the University of California, Los Angeles before returning to the Hebrew University as a faculty member. [1]

In 2012 he became a fellow of the American Mathematical Society. [5] In 2019 he won the FOCS Test of Time Award for the paper "Constant Depth Circuits, Fourier Transform, and Learnability", co-authored with Yishay Mansour and Noam Nisan. [6]

Selected publications

Related Research Articles

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. 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 distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another. Distributed computing is a field of computer science that studies distributed systems.

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

<span class="mw-page-title-main">Theoretical computer science</span> Subfield of computer science and mathematics

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, formal language theory, the lambda calculus and type theory.

Self-stabilization is a concept of fault-tolerance in distributed systems. Given any initial state, a self-stabilizing distributed system will end up in a correct state in a finite number of execution steps.

Nancy Ann Lynch is a computer scientist affiliated with the Massachusetts Institute of Technology. She is the NEC Professor of Software Science and Engineering in the EECS department and heads the "Theory of Distributed Systems" research group at MIT's Computer Science and Artificial Intelligence Laboratory.

In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.

ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.

<span class="mw-page-title-main">Noga Alon</span> Israeli mathematician

Noga Alon 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.

<span class="mw-page-title-main">Avi Wigderson</span> Israeli mathematician and computer scientist

Avi Wigderson is an Israeli mathematician and computer scientist. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States of America. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural networks. Wigderson received the Abel Prize in 2021 for his work in theoretical computer science.

Task systems are mathematical objects used to model the set of possible configuration of online algorithms. They were introduced by Borodin, Linial and Saks (1992) to model a variety of online problems. A task system determines a set of states and costs to change states. Task systems obtain as input a sequence of requests such that each request assigns processing times to the states. The objective of an online algorithm for task systems is to create a schedule that minimizes the overall cost incurred due to processing the tasks with respect to the states and due to the cost to change states.

David Peleg is an Israeli computer scientist. He is a professor at the Weizmann Institute of Science, holding the Norman D. Cohen Professorial Chair of Computer Sciences, and the present dean of the Faculty of Mathematics and Computer Science in Weizmann Institute. His main research interests are algorithms, computer networks, and distributed computing. Many of his papers deal with a combination of all three.

Manfred Klaus Warmuth is a computer scientist known for his pioneering research in computational learning theory. He is a Distinguished Professor emeritus at the University of California, Santa Cruz.

Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.

Michael Stewart Paterson, is a British computer scientist, who was the director of the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick until 2007, and chair of the department of computer science in 2005.

Michael Ezra Saks is an American mathematician. He is currently the Department Chair of the Mathematics Department at Rutgers University (2017–) and from 2006 until 2010 was director of the Mathematics Graduate Program at Rutgers University. Saks received his Ph.D. from the Massachusetts Institute of Technology in 1980 after completing his dissertation titled Duality Properties of Finite Set Systems under his advisor Daniel J. Kleitman.

In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits. It was first introduced by Johan Håstad to prove that AC0 Boolean circuits of depth k require size to compute the parity function on bits. He was later awarded the Gödel Prize for this work in 1994.

Stathis K. Zachos is a mathematician, logician and theoretical computer scientist.

<span class="mw-page-title-main">Noam Nisan</span> Israeli computer scientist

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.

<span class="mw-page-title-main">Michal Parnas</span> Israeli theoretical computer scientist

Michal Parnas is an Israeli theoretical computer scientist known for her work on property testing and sublinear-time algorithms. She is a professor of computer science at the Academic College of Tel Aviv-Yafo in Israel, where she was a founding faculty member and was also the dean of the school of computer science from 2011 to 2016. Since October 2022 she is the vice president of academic affairs of the college.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.