The answer to the title question seems to be “Not much”. Even sorting n items takes n log(n) swaps. Actually, quite a bit can be done in linear time. In the first part of the talk we illustrate some known linear-time techniques (and pave the way to the second part).
Working on access control at Microsoft, we noticed that the most basic and useful access-control queries could be executed blazingly fast in practice. We wondered whether there was a theoretical foundation for the phenomenon. Eventually we came up with a logic calculus and an algorithm that, given a set of hypothesis and a set of queries, decides – in linear time – which of the queries follow from the hypotheses and which don’t. In the second part of the talk, we explain how this is at all possible.
The presentation builds on joint work with Itay Neeman (UCLA Prof.), Carlos Cotrini and Ori Lahav (students at the time), and Artem Melentyev (a Microsoft intern at the time).
This video is part of the New York Group Theory Cooperative‘s group theory seminar series.
