Tags » Hardness Of Approximation

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… 1,227 more words


Hardness of Approximating MAX-3SAT and MAX-E3LIN

In this post, I will start proving that MAX-3SAT is NP-hard to approximate within a factor better than . Instead of showing directly that the MAX-3SAT problem is NP-hard to approximate, I will show that another problem, called MAX-E3LIN, reduces to it and that any polynomial time -approximation for the MAX-3SAT problem would give a -approximation algorithm to MAX-E3LIN for all and some depending on . 1,585 more words


The MAX-3SAT Problem and the Method of Conditional Expectation

In this post, I will discuss the MAX-3SAT problem. Over the course of the next few posts, I will give an optimal approximation algorithm for the problem. 522 more words


Probabilistically Checkable Proofs (PCPs) and Hardness of Approximation

In the previous blog post, I introduced the idea of hardness amplification and used it to prove that the Maximum Independent Set problem is NP-hard to approximate within any constant factor on general graphs. 1,370 more words


Hardness of approximating independent set

I will start my blog by illustrating that NP-completeness has more implications than just exact hardness of computational problems. Through clever “hardness amplification” techniques, one can extend assumptions about the difficulty of exactly solving NP-hard problems like… 1,315 more words


Hypercontractivity and its Applications

My student Punya Biswal just completed this great survey on hypercontractivity and its application in computer science. There is a PDF version from his home page, and… 4,293 more words


Lecture P1. From Integrality Gaps to Dictatorship Tests

Here are Prasad Raghavendra‘s notes on one of two guest lectures he gave for CSE 599S. Prasad will be a faculty member at Georgia Tech after he finishes his postdoc at MSR New England. 3,702 more words

CSE 599S