What’s the simplest nontrivial algorithm for Max-2AND?

September 12, 2022

I’m writing this post to describe some very simple approximation algorithms for the \(\mtwoand\) problem. These are based on recent joint work with Joanna Boyland, Michael Hwang, Tarun Prasad, and Santhoshini Velusamy [cite:BHP+22].1 I’d like to stress that these algorithms aren’t exactly “new”: They are simplified versions of recent algorithms by Chou, Golovnev, and Velusamy [cite:CGV20], and do not quantitatively improve the performance. Instead, the main contribution of our paper [cite:BHP+22] is showing that this...

tcs streaming-csps

The minimum circuit size problem: DIMACS REU Blog

August 23, 2021

July 2022 update: Below is the blog I kept for my project on the minimum circuit size problem at the DIMACS REU at Rutgers over Summer 2021, advised by Eric Allender, and in collaboration with Vishal Ramesh and Sasha Sami. The original project page is hosted on the REU site. The project ran from May 23 to July 24, 2021. In this version, I’ve slightly changed the MathJax formatting and reformatted the references. I should...