# Tag Info

## Hot answers tagged proof-techniques

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.

1

A paper of mine with Gupta and Kumar titled On a bidirected relaxation for the MULTIWAY CUT problem was also based on running experiments. In fact we were trying to prove the converse of what we ended up proving. Vazirani, in the first edition of his book on approximation algorithms, suggested that the bidirected relaxation was at least as good as the ...

1

My recent paper with Karthik Chandrasekharan titled Hypergraph $k$-cut in deterministic polynomial time was based on extensive computational experiments. We explored different conjectures and submodular functions and found counter examples to several different approaches. The truth of the main structural theorem was suggested by experiments and we then ...

1

Some recent results in state complexity were found with the help of systematic brute-force search for worst-case examples. This is doable because there are not too many deterministic finite automata with a small number of states, for example if we concentrate on binary or ternary alphabets. Also, in many cases there are families of worst-case examples for \$1,...

1

In 2018, Aubrey de Grey found a 1581-vertex, non-4-colourable unit-distance graph. This gives a lower bound of five for the famous Hadwiger-Nelson problem. He used a computer to verify that the graph indeed has chromatic number at least five. Gil Kalai's blogpost covers some facts and further developments. An article in the quanta magazine reports that he ...

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