Category Archives: Computer Science and Optimization

Some Mathematical Puzzles that I encountered during my career

Recently, I gave some general-audience personal tour across four (plus one) mathematical puzzles that I encountered during my career. Here is a paper which is meant for a very wide audience (in English) Puzzles on trees, high dimensions, elections, computation … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Quantum | Tagged | Leave a comment

Updates (belated) Between New Haven, Jerusalem, and Tel-Aviv

This is a (very much) belated update post from the beginning of March (2016). New Haven I spent six weeks in February (2016) in New Haven. It was very nice to get back to Yale after more than two years. Here … Continue reading

Posted in Art, Combinatorics, Computer Science and Optimization, Number theory, Updates | Leave a comment

Oded Goldreich Fest

Update (April 17): Outcomes of the poll for the coolest title are in. (See the end of the post) Oded Goldreich’s 60 birthday meeting, April 19-20 at the Weitzmann Institute promises to be a great event. Here is the webpage … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Conferences | Tagged | 1 Comment

The Race to Quantum Technologies and Quantum Computers (Useful Links)

One of my main research directions in the last decade is  quantum information theory and quantum computers. (See this post and this one.) It is therefore a pleasure to report and give many links on the massive efforts carried out these … Continue reading

Posted in Computer Science and Optimization, Physics, Quantum | Tagged , , , , , | 13 Comments

My Answer to TYI- 28

The fifteen remarkable individuals in the previous post are all the recipients of the  SIGACT Distinguished Service Prize since it was established in 1997. The most striking common feature to all of them is, in my view, that they are all … Continue reading

Posted in Computer Science and Optimization, Women in science | Tagged , | 2 Comments

Test your intuition 28: What is the most striking common feature to all these remarkable individuals

Test your intuition: What is the most striking common feature to all these fifteen remarkable individuals László Babai; Avi Wigderson; Lance Fortnow; Lane Hemaspaandra; Sampath Kannan; Hal Gabow; Richard Karp; Tom Leighton; Rockford J. Ross; Alan Selman; Michael Langston; S. … Continue reading

Posted in Computer Science and Optimization, Test your intuition | 1 Comment

Boolean Functions: Influence, Threshold, and Noise

Here is the written version of my address at the 7ECM last July in Berlin. Boolean functions, Influence, threshold, and Noise Trying to follow an example of a 1925 lecture by Landau (mentioned in the lecture), the writing style is very … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability | Tagged | 7 Comments

Laci Babai Visits Israel!

  I am sure that every one of the readers of this blog heard about Laci Babai’s quasi-polynomial algorithm for graph isomorphism and also the recent drama about it: A mistake pointed out by Harald Helfgott,  a new sub-exponential but … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , | 2 Comments

Is Heads-Up Poker in P?

Five years ago I wrote a post entitled Is Backgammon in P? It was based on conversations with Peter Bro Miltersen and Uri Zwick (shown together in the above picture) about the computational complexity of computing the values (and equilibrium … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Games | Tagged , , , , | 3 Comments

The US Elections and Nate Silver: Informtion Aggregation, Noise Sensitivity, HEX, and Quantum Elections.

Being again near general  elections is  an opportunity to look at some topics we talked about over the years. I am quite fond of (and a bit addicted to) Nate Silver’s site FiveThirtyEight. Silver’s models tell us what is the probability that … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability, Quantum | Tagged , , | 14 Comments