Category Archives: Computer Science and Optimization

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

Avifest live streaming

Live streaming for Avifest is available here. The program is here. Following the first two lectures I can witness that the technical quality of the broadcast is very good and the scientific quality of the lectures is superb. As this is … Continue reading

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

Jirka

The Mathematics of Jiří Matoušek is a conference taking place this week at Prague in memory of Jirka Matoušek.  Here are the slides of my planned talk on Maestro Jirka Matoušek. This post presents the opening slides for the conference … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Conferences, Geometry, Obituary | Tagged | 4 Comments

AviFest, AviStories and Amazing Cash Prizes.

  Ladies and gentlemen,  a workshop in Princeton in honor of Avi Wigderson’s 60th birthday  is coming on October. It will take place at Princeton on October 5-8 2016 right before FOCS 2016.  Don’t miss the event ! Attendance is free but … Continue reading

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

More Reasons for Small Influence

Readers of the big-league ToC blogs have already heard about the breakthrough paper An average-case depth hierarchy theorem for Boolean circuits by Benjamin Rossman, Rocco Servedio, and Li-Yang Tan. Here are blog reports on Computational complexity, on the Shtetl Optimized, and of Godel … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Open problems, Probability | 12 Comments

New Isoperimetric Results for Testing Monotonicity

Muli, Dor and Subash, Jerusalem May 21 2015.   Michel Talagrand            Gregory Margulis Property testing In this post I will tell you about a new paper by Subhash Khot, Dor Minzer and Muli Safra  entitled: On … Continue reading

Posted in Combinatorics, Computer Science and Optimization | 1 Comment