Category Archives: Computer Science and Optimization

Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes

Special Quantum PCP and/or Quantum Codes: Simplicial Complexes and Locally Testable CodesDay בי”ס להנדסה ולמדעי המחשב 24 Jul 2014 - 09:30 to 17:00 room B-220, 2nd floor, Rothberg B Building On Thursday, the 24th of July we will host a SC-LTC (simplicial complexes … Continue reading

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

Influence, Threshold, and Noise

  My dear friend Itai Benjamini told me that he won’t be able to make it to my Tuesday talk on influence, threshold, and noise, and asked if I already have  the slides. So it occurred to me that perhaps … Continue reading

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

Navier-Stokes Fluid Computers

Smart fluid Terry Tao posted a very intriguing post on the Navier-Stokes equation, based on a recently uploaded paper Finite time blowup for an averaged three-dimensional Navier-Stokes equation. The paper proved a remarkable negative answer for the regularity conjecture for a certain … Continue reading

Posted in Analysis, Applied mathematics, Computer Science and Optimization, Open problems | Tagged , , , , , | 11 Comments

NatiFest is Coming

The conference Poster as designed by Rotem Linial A conference celebrating Nati Linial’s 60th birthday will take place in Jerusalem December 16-18. Here is the conference’s web-page. To celebrate the event, I will reblog my very early 2008 post “Nati’s … Continue reading

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

Analysis of Boolean Functions – Week 7

Lecture 11 The Cap Set problem We presented Meshulam’s  bound for the maximum number of elements in a subset A of not containing a triple x,y,x of distinct elements whose sum is 0. The theorem is analogous to Roth’s theorem … Continue reading

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

Analysis of Boolean Functions week 5 and 6

Lecture 7 First passage percolation 1)  Models of percolation. We talked about percolation introduced by Broadbent and Hammersley in 1957. The basic model is a model of random subgraphs of a grid in n-dimensional space. (Other graphs were considered later as … Continue reading

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

Real Analysis Introductory Mini-courses at Simons Institute

The Real Analysis ‘Boot Camp’ included three excellent mini-courses. Inapproximability of Constraint Satisfaction Problems (5 lectures) Johan Håstad (KTH Royal Institute of Technology) (Lecture I, Lecture II, Lecture III, Lecture IV, Lecture V) Unlike more traditional ‘boot camps’ Johan rewarded answers and questions … Continue reading

Posted in Analysis, Computer Science and Optimization, Conferences | Tagged , , | Leave a comment

Analysis of Boolean Functions – week 4

Lecture 6 Last week we discussed two applications of the Fourier-Walsh plus hypercontractivity method and in this lecture we will discuss one additional application: The lecture was based on a 5-pages paper by Ehud Friedgut and Jeff Kahn: On the number … Continue reading

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

Analysis of Boolean Functions – Week 3

Lecture 4 In the third week we moved directly to the course’s “punchline” – the use of Fourier-Walsh expansion of Boolean functions and the use of Hypercontractivity. Before that we  started with  a very nice discrete isoperimetric question on a … Continue reading

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

Analysis of Boolean functions – week 2

Post on week 1; home page of the course analysis of Boolean functions Lecture II: We discussed two important examples that were introduced by Ben-Or and Linial: Recursive majority and  tribes. Recursive majority (RM): is a Boolean function with variables … Continue reading

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