skyspace

"Stronger 3SUM lower bounds via Additive Combinatorics"

[12-25-23]

In this blog post I summarize "Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics" by Abboud Bringmann and Fischer and also discuss the very similar "Removing Additive Structure in 3sum based reductions" by Jin and Xu.

pairwise indep hashing 2bins

[08-03-23]

cycles

[12-09-23]

Some notes about algorithms for finding cycles in graphs.

min-cost circulation

[12-13-23]

I feel like I can never remember what min-cost circulation (MCC) is, or what the basic facts about it are. So here is a short blog post where I remind myself of what MCC is.

fine-grained complexity: 3sum

[12-26-23]

I was reading a couple of Virginia's https://people.csail.mit.edu/virgi/6.s078/ fine-grained complexity theory notes. Here I write down some of the cool things I learned while reading the notes.

FPT part 3

[01-08-24]

I read chapter 2 of the FPT book in a bit more detail. And try some more problems.

FPT part 6

[01-15-24]

tree width part 2

parallel graph algorithms

[01-15-23]

2-server on a circle

[07-26-23]

In the k-server problem you have k "servers" located in some topological space. You recieve a series of "requests", which are points in the topological space. You must respond to the request by moving some subset of your servers so that at least one server goes to the request. We will consider this problem in a metric space. You objective is to minimize the total distance travelled by all your servers. More precisely, our objective is to create a strategy that achieves bounded competitive ratio. We consider this problem with k=2 and set on a circle, where distance is measured along the circle.