### Recent Comments

Eli_B on זה הזמן לשינוי Michael Elkin on זה הזמן לשינוי Gil Kalai on זה הזמן לשינוי Eli_B on זה הזמן לשינוי Gil Kalai on זה הזמן לשינוי Gil Kalai on זה הזמן לשינוי Eli_B on זה הזמן לשינוי Gil Kalai on זה הזמן לשינוי Michael Elkin on זה הזמן לשינוי Eli_B on זה הזמן לשינוי Jon Awbrey on Influence, Threshold, and… Combinatorics and Mo… on Four Derandomization Problems -
### Recent Posts

- זה הזמן לשינוי
- Combinatorics and More – Greatest Hits
- Ilan and me
- The Simplex, the Cyclic polytope, the Positroidron, the Amplituhedron, and Beyond
- From Oberwolfach: The Topological Tverberg Conjecture is False
- Midrasha Mathematicae #18: In And Around Combinatorics
- Quantum computing: achievable reality or unrealistic dream
- A Historical Picture Taken by Nimrod Megiddo
- Scott Triumphs* at the Shtetl

### Top Posts & Pages

- זה הזמן לשינוי
- Combinatorics and More - Greatest Hits
- Believing that the Earth is Round When it Matters
- Extremal Combinatorics I: Extremal Problems on Set Systems
- Academic Degrees and Sex
- The Simplex, the Cyclic polytope, the Positroidron, the Amplituhedron, and Beyond
- The Ultimate Riddle
- Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
- Helly's Theorem, "Hypertrees", and Strange Enumeration I

### RSS

# Monthly Archives: November 2010

## Polynomial Hirsch Conjecture 5: Abstractions and Counterexamples.

This is the 5th research thread of polymath3 studying the polynomial Hirsch conjecture. As you may remember, we are mainly interested in an abstract form of the problem about families of sets. (And a related version about families of multisets.) The … Continue reading

## Analysis of Boolean Functions

I discovered a vidiotaped lecture I gave at the Open University on the 3rd Israeli Theory Day. Enjoy! http://www.youtube.com/watch?v=xbJe7ioCISM Posts related to this lecture: Noise Stability and threshold circuits; Noise stability lecture and tales; Nati’s influence.

Posted in Computer Science and Optimization
3 Comments

## Emmanuel Abbe: Erdal Arıkan’s Polar Codes

Click here for the most recent polymath3 research thread. A new thread is comming soon. Emmanuel Abbe and Erdal Arıkan This post is authored by Emmanuel Abbe A new class of codes, called polar codes, recently made a breakthrough in … Continue reading

## Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier

Click here for the most recent polymath3 research thread. I missed Tom by a few minutes at Mittag-Leffler Institute a year and a half ago Suppose that is a subset of of maximum cardinality not containing an arithmetic progression of length 3. Let . … Continue reading

Posted in Combinatorics, Open problems
Tagged Endre Szemeredi, Jean Bourgain, Klaus Roth, Roger Heath-Brown, Roth's theorem, Tom Sanders
9 Comments

## János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem

Click here for the most recent polymath3 research thread. Erdős and Pach celebrating another November day many years ago. The Wolf disguised as Little Red Riding Hood. Pach disguised as another Pach. This post is authored by János Pach A … Continue reading

Posted in Combinatorics, Geometry, Guest blogger, Open problems
Tagged Larry Guth, Nets Hawk Katz
13 Comments

## Aaronson and Arkhipov’s Result on Hierarchy Collapse

Scott Aaronson gave a thought-provoking lecture in our Theory seminar three weeks ago. (Actually, this was eleven months ago.) The slides are here . The lecture discussed two results regarding the computational power of quantum computers. One result from this paper gives an … Continue reading

## Octonions to the Rescue

Xavier Dahan and Jean-Pierre Tillich’s Octonion-based Ramanujan Graphs with High Girth. Update (February 2012): Non associative computations can be trickier than we expect. Unfortunately, the paper by Dahan and Tillich turned out to be incorrect. Update: There is more to … Continue reading

## Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding … Continue reading