Recent Comments

Recent Posts
 Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes
 Happy Birthday Ervin, János, Péter, and Zoli!
 My Mathematical Dialogue with Jürgen Eckhoff
 Test Your Intuition (23): How Many Women?
 Happy Birthday Richard Stanley!
 Influence, Threshold, and Noise
 Erdős Lectures 2014 – Dan Spielman
 Answer to Test Your Intuition (22)
 Test your intuition (22): Selling Two Items in a Bundle.
Top Posts & Pages
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 Why Quantum Computers Cannot Work: The Movie!
 Polymath 8  a Success!
 Believing that the Earth is Round When it Matters
 Emmanuel Abbe: Erdal Arıkan's Polar Codes
 Analysis of Boolean Functions
 Another Forgotten Bet: Is Don Zagier About to Owe Me 1000 Shekels For The Proof of the ABC Conjecture?
 About
 Test Your Intuition (23): How Many Women?
RSS
Category Archives: Computer Science and Optimization
To Life, to Science and to Innovations
ICS2011 at ITCS, Tsinghua University, Beijing, China The title of this post “To life, to Science and to Innovations” was Silvio Micali’s toast at the second conference on Innovations in Computer Science and Silvio’s words have a good chance of becomeing the official toast of … 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
Aaronson and Arkhipov’s Result on Hierarchy Collapse
Scott Aaronson gave a thoughtprovoking 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 JeanPierre Tillich’s Octonionbased 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
IPAM Workshop – Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?
Workshop at IPAM: January 18 – 21, 2011 Here is the link to the IPAM conference.
Drunken Time and Drunken Computation
The problem We are used to computer programs or models for computations that perform at time step , . Suppose that time is drunk, so instead of running these steps in their correct order, we apply at time step , where … Continue reading
Posted in Computer Science and Optimization
10 Comments
Noise Stability and Threshold Circuits
The purpose of this post is to describe an old conjecture (or guesses, see this post) by Itai Benjamini, Oded Schramm and myself (taken from this paper) on noise stability of threshold functions. I will start by formulating the conjectures and … Continue reading
Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design II
This post is authored by Michael Schapira. (It is the second in a series of two posts.) In thse two post, I outline work on Internet routing and sketch important areas for future work, both on routing itself and, more broadly, on mechanism … Continue reading
Translation, Machine Translation, and a Crowded Seminar
I gave in several places a talk entitled “Analytic and Probabilistic Properties of Boolean Functions.” This is a fairly large area so the talks can differ quite a bit. The lecture at the NYU CS theory seminar was described over a Chinese blog entitled … Continue reading
Posted in Computer Science and Optimization
Tagged Googletranslation, Hanoch Kalai, Machine translation, Tovna
7 Comments