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

## Tags » Hardness Of Approximation

#### 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