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

Posted in Computer Science and Optimization, Conferences | 7 Comments

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 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

Posted in Computer Science and Optimization, Physics | Tagged , , , , , | 11 Comments

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

Posted in Algebra and Number Theory, Combinatorics, Computer Science and Optimization, Open problems, Physics | Tagged , , , | 11 Comments

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

Posted in Computer Science and Optimization, Convex polytopes, Games | Tagged , | 11 Comments

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. 

Posted in Combinatorics, Computer Science and Optimization, Conferences, Convex polytopes | Leave a comment

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

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

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

Posted in Computer Science and Optimization, Economics | Leave a comment

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 , , , | 7 Comments