Recent Comments
Category Archives: Computer Science and Optimization
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 Google-translation, Hanoch Kalai, Machine translation, Tovna
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 incentive compatibility, Internet, Routing, Security
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
Four Derandomization Problems
Polymath4 is devoted to a question about derandomization: To find a deterministic polynomial time algorithm for finding a k-digit prime. So I (belatedly) devote this post to derandomization and, in particular, the following four problems. 1) Find a deterministic algorithm for primality 2) Find … Continue reading
Posted in Computer Science and Optimization, Probability
Tagged derandomization, polymath4, Randomness
4 Comments
Impossibility Result for “Survivor”
Consider a set of agents and a directed graph where an edge means that agent supports or trusts agent . We wish to choose a subset of size of trustworthy agents. Each agent’s first priority is to be included in … Continue reading
Noise Sensitivity Lecture and Tales
A lecture about Noise sensitivity Several of my recent research projects are related to noise, and noise was also a topic of a recent somewhat philosophical post. My oldest and perhaps most respectable noise-related project was the work with Itai Benjamini and Oded … Continue reading
