All Activities

New perspectives on distributed computing systems

A workshop in Honor of Barbara Liskov was held on April 6, 2016, titled “New Perspectives on Distributed Computing Systems”.

The workshop highlighted recent advances in the field of Distributed Computing Systems, via presentations by Prof. Barbara Liskov, a computer science professor at the Massachusetts Institute of Technology, and a number of leading young researchers in the field of distributed computing who joined the Israeli academia in recent years.

During the workshop, Prof. Liskov – one of the pioneers of computer science and a Turing Prize winner (2008) – also received the Weizmann Women & Science Award for her outstanding work as a role model for young female computer scientists.

Hidden irregularity versus hidden symmetry

The annual Chaim Leib Pekeris Memorial Lecture was held this year on January 29, 2017.
Prof. Laszlo Babai of the University of Chicago talked about Hidden irregularity versus hidden symmetry.

Full abstract:

Symmetry is defined in terms of structure-preserving transformations (automorphisms); regularity in terms of numerical invariants. Symmetry always implies regularity but there are many highly regular combinatorial objects (such as "strongly regular graphs") with no symmetry. The opposite of irregularity is regularity, not symmetry. Yet we show that in a well-defined sense, the opposite of hidden irregularity is hidden symmetry, and in fact hidden symmetry of a particularly robust kind.

The symmetry of a circle is easily destroyed: just "individualize" two non-opposite points -- color one of them red, the other blue -- and all the symmetry is gone. In fact, the resulting structure is completely irregular: every point is uniquely identified by a pair of numerical invariants, namely, its pair of distances to the two individualized points. We shall say that the circle has a high degree of hidden irregularity. In contrast, Johnson graphs are objects with robust symmetry: individualizing a small number of vertices of a Johnson graph hardly makes a dent in its symmetry.

Recent work on the algorithmic problem of Graph Isomorphism has revealed that Johnson graphs are unique in this regard: Every finite relational structure of small arity either has a measurable (say 10%) hidden irregularity (revealed by individualizing a polylogarithmic number of elements) or has a large degree of hidden symmetry, manifested in a canonically embedded Johnson graph on more than 90% of the underlying set.

This dichotomy is the key Divide-and-Conquer tool in recent progress on the worst-case complexity of the Graph Isomorphism problem.

Read More about Hidden irregularity versus hidden symmetry

Randomness, complexity and cryptography

This workshop, held on April 19-20, 2017, was a tribute to the prolific and highly influential academic career of Professor Oded Goldreich, on the occasion of his 60th birthday. Oded made key contributions to a number of foundational topics within computer science, predominantly cryptography, pseudorandomness, computational complexity, sublinear algorithms, property testing, and many other areas involving the interplay between computational complexity and randomness.

The workshop consisted of technical sessions and, on both days, evening social events. The technical sessions consisted of tutorials and survey talks, as well as reports on new research.

Conference homepage

List of Speakers:

Benny Applebaum, Tel Aviv University
Boaz Barak, Harvard University
Ran Canetti, Tel Aviv University and Boston University
Benny Chor, Tel Aviv University
Irit Dinur, Weizmann Institute of Science
Shafi Goldwasser, Weizmann Institute of Science & MIT
Shai Halevi, IBM
Johan Hastad, KTH
Iftach Haitner, Tel Aviv University
Hugo Krawczyk, IBM
Yehuda Lindell, Bar-Ilan University
Or Meir, Haifa University
Silvio Micali, MIT
Omer Reingold, Stanford University
Dana Ron, Tel Aviv University
Alon Rosen, Interdisciplinary Center Herzliya
Guy Rothblum, Weizmann Institute of Science
Ronitt Rubinfeld, Tel Aviv University & MIT
Madhu Sudan, Harvard University
Salil Vadhan, Harvard UniversityAvi Wigderson, IAS

Read More about Randomness, complexity and cryptography

Math olympics

The Joseph Gillis National Math Olympiad took place in March,2017, with the participation of 200 high school students from across Israel. The competition, held annually at the Weizmann Institute of Science, was initiated by the late Prof. Joseph Gillis, an Israeli mathematician who was one of the founders of the Faculty of Mathematics.

First place winners are awarded a full scholarship from participating Israeli universities that covers their first year of studies, and the second and third-place winners receive a partial scholarship.



The 2017 Lee A. Segel prize for mathematical biology

The Lee Segel Prize was established to honor the contribution of Lee Segel to the Bulletin of Mathematical Biology and the field of mathematical biology in general.
Since 2008, the prize has been awarded every two years in two main categories: best paper and best student paper.
Other prizes may be awarded in additional categories, as determined by the prize committee and the Society for Mathematical Biology.


Solving the Hilbert's 16th

Like most theoretical mathematicians, Dr. Gal Binyamini of the Department of Mathematics is most interested in the type of problems that can't be answered, like the 23 then-unsolved problems posed by German mathematician David Hilbert at the Paris conference of the International Congress of Mathematicians in 1900. In the last 116 years, mathematicians have resolved, or partially solved, most of the challenges proposed by Hilbert.

Dr. Binyamini is particularly interested in Hilbert's 16th, one of the few problems that still defy solution. He does not expect to solve it, but is fascinated by the pure mathematics that it entails and in the interplay of algebra and algebraic geometry with the geometry and complexity of differential equations. Differential equations in math and physics define much of the known world. Non-linear equations begin to enter the realm of the unsolvable, and the concept of transcendental numbers and objects leave the world of rational numbers far behind.

Much of the theoretical work in this realm of mathematics involves finding realistic estimates of just how complex especially difficult problems are—in terms of the orders of magnitude of possible outcomes - and the computing power needed to calculate them. Reasonable estimates of these parameters can simplify tough problems just enough to bring them into the realm of solvable equations.

The Belfer Institute aims to promote outstanding mathematicians and computer scientists and support their innovative research. This support is part of the agenda of the Weizmann Institute of providing principal investigators with the best possible conditions to pursue their research.

Read More about Solving the Hilbert's 16th

The quantum computer puzzle

Each year, the Faculty of Mathematics and Computer Science and the Belfer Institute hold an annual lecture in memory of the Faculty’s founder, Prof. Chaim Leib Pekeris. This year, the The Chaim Leib Pekeris Memorial Lecture was delivered on June 14, 2016, by Prof. Gil Kalai of the Hebrew University of Jerusalem. The lecture was titled: "The Quantum Computer Puzzle".

Quantum computers are hypothetical devices, based on quantum physics, which would be able to perform certain computations hundreds of orders of magnitude faster than digital computers. This feature is coined as "quantum supremacy," and one aspect or another of such quantum computational supremacy might be brought about in experiments in the near future: by implementing quantum error-correction, systems of non-interacting bosons, exotic new phases of matter called anyons, quantum annealing, or in various other ways.

A main concern regarding the feasibility of quantum computers is that quantum systems are inherently noisy: scientists can neither accurately control them nor describe them. Prof. Kalai describes two hypotheses: An optimistic hypothesis of quantum noise that would allow quantum computing; and a pessimistic hypothesis that wouldn't. The quantum computer puzzle is deciding between these two hypotheses.

To the lecture's photo gallery

Read More about The quantum computer puzzle

The 2016 Lee A. Segel prize for mathematical biology

The Lee A. Segel for Mathematical Prize Biology event was held on February 11, 2016.
The Prize, in loving memory of Prof. Lee A. Segel – a world-renowned mathematician and theoretical biologist who spent over 30 years of his career at the Weizmann Institute – was awarded to Tal Korem, a PhD student in the lab of Prof. Eran Segal

The Shimon Even memorial prize

The Shimon Even Memorial Prize in Theoretical Computer Science was awarded this year to Tom Gur, a PhD student in the research group of Prof. Oded Goldreich of the Department of Computer Science and Applied Mathematics. The ceremony was held on February 11, 2016. 

The complexity of composed functions

Prof. Irit Dinur studies questions regarding computational complexity. For example, given two numbers a and b, which is easier: computing A+B or AxB? Every child senses that multiplication is harder, in that it requires more “elementary steps.” Indeed, the naïve algorithm that we learned in elementary school requires more elementary steps, but is it the fastest algorithm?

About 50 years ago this was posed as a conjecture, which was soon refuted. It turns out that there are much faster ways to multiply two numbers than the textbook method. It also turns out that proving “lower bounds,” i.e. that something is complicated and requires many steps, is extremely hard. To this day, we still do not know if multiplication is harder than addition.

In recent work, Prof. Dinur focused on the complexity of so-called composed functions, which are functions defined by a sequence of steps. She showed that for many such functions, there are no shortcuts: the naïve algorithm that computes one step at a time is the best possible path to the solution. She hopes to obtain a better understanding of which functions are more like the naïve ones—and which ones have shortcuts. This could have major implications on the world of cryptography, as naïve algorithms that are hard to bypass could prove to be good cryptographic tools.

The Belfer Institute aims to promote outstanding mathematicians and computer scientists and support their innovative research. This support is part of the agenda of the Weizmann Institute of providing principal investigators with the best possible conditions to pursue their research.

Read More about The complexity of composed functions