Tag Info

4

A recent result of Li, Nguyen, and Woodruff shows that for any streaming algorithm in the turnstile model (where the stream consists of insertions and deletions of elements) there exists an algorithm that works by only maintaining a linear sketch and uses only slightly more space. So to prove a space lower bound in the turnstile model it is (up to some ...

3

While not new, (and depending on what you consider to be "streaming algorithms"), a standard lower bound technique is picking a (as large as possible) set of inputs, and proving that each has to lead the algorithm to a distinct memory configuration. The implied lower bound is then the log of the number of such inputs. For example, Datar et al. showed (...

2

Let me clarify the setting, which has nothing to do with $\pi$-calculus or bisimulation. The first thing you have to realise that it does not make much sense to talk about a programming language without reference to the notion of program equivalence you intend to impose on the language. That's because We usually identify certain programs (e.g. f(x:int) = {...

1

In the same spirit of Sanjeev Arora's notes that @umar posted, I like Madhur Tulsiani's lecture notes and exercises for his "Mathematical Toolkit" class posted at the course webpage. In addition to Arora's excellent material his notes have a nice coverage of spectral graph theory as well as the multiplicative weights update method.

Only top voted, non community-wiki answers of a minimum length are eligible