Category Archives: Computer Science and Optimization

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

Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design I

This post is authored by Michael Schapira. (It is the first in a series of two posts.) In this post, I’ll outline work on Internet routing and sketch important areas for future work, both on routing itself and, more broadly, on … Continue reading

Posted in Computer Science and Optimization, Economics, Guest blogger | Tagged , , , | 4 Comments

When Noise Accumulates

I wrote a short paper entitled “when noise accumulates” that contains the main conceptual points (described rather formally) of my work regarding noisy quantum computers.  Here is the paper. (Update: Here is a new version, Dec 2010.) The new exciting innovation in computer … Continue reading

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