Blogs about: Hardness Of Approximation
Featured Blog
Why is discrete Fourier analysis useful in obtaining hardness of approximation results?
In my last post, I gave a PCP for the Label Cover problem that translated into a MAX-E3LIN instance. We analyzed everything but the soundness case, in which given a Label Cover instance with , the PCP… more →
A Spoonful of Complexity
Why is discrete Fourier analysis useful in obtaining hardness of approximation results?
wrote 4 months ago: In my last post, I gave a PCP for the Label Cover problem that translated into a MAX-E3LIN instance. … more →
Hardness of Approximating MAX-3SAT and MAX-E3LIN
wrote 5 months ago: In this post, I will start proving that MAX-3SAT is NP-hard to approximate within a factor better th … more →
The MAX-3SAT Problem and the Method of Conditional Expectation
wrote 5 months ago: In this post, I will discuss the MAX-3SAT problem. Over the course of the next few posts, I will giv … more →
Probabilistically Checkable Proofs (PCPs) and Hardness of Approximation
wrote 5 months ago: In the previous blog post, I introduced the idea of hardness amplification and used it to prove that … more →
Hardness of approximating independent set
wrote 5 months ago: I will start my blog by illustrating that NP-completeness has more implications than just exact hard … more →
Hypercontractivity and its Applications
— 8 comments
wrote 3 years ago: My student Punya Biswal just completed this great survey on hypercontractivity and its application i … more →
Lecture P1. From Integrality Gaps to Dictatorship Tests
— 2 comments
wrote 3 years ago: Here are Prasad Raghavendra‘s notes on one of two guest lectures he gave for CSE 599S. Prasad … more →
