We show improved NP-hardness of approximating {Ordering Constraint Satisfaction Problems}~(OCSPs). For the two most well-studied OCSPs, \textproblem{Maximum Acyclic Subgraph} and \textproblem{Maximum Betweenness}, we prove inapproximability of $14/15+\epsilon$ and $1/2+\epsilon$.%, respectively. An OCSP is said to be approximation resistant if it is hard to approximate better than taking a uniformly random ordering. We prove that the Maximum Non-Betweenness Problem is approximation resistant and that there are width-m approximation-resistant OCSPs accepting only a fraction $1 / (m/2)!$ of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P \neq NP.

We show a testing procedure to verify an oracle that supposedly computes the permanent of most gaussian distributed matrices.

The thesis ascertains the approximability of classic combinatorial optimization problems using mathematical relaxations. The general flavor of results in the thesis is: a problem $P$ is hard to approximate to a factor better than one obtained from the $R$ relaxation, unless the Unique Games Conjecture is false.
Almost optimal inapproximability is shown for a wide set of problems including Metric Labeling, Max. Acyclic Subgraph, various packing and covering problems. The key new idea in this thesis is in coverting hard instances of relaxations (a.k.a integrality gap instances) into a proof of inapproximability (assuming the UGC). In most cases, the hard instances were discovered prior to this work; our results imply that these hard instances are possibly strong bottlenecks in designing approximation algorithms of better quality for these problems.
For ordering problems such as Max. Acyclic Subgraph, and Feedback Arc Set, such hard instances were previously unknown. For these problems, we construct such hard instance by using the reduction designed to prove the inapproximability. The hard instances show that all ordering problems are hard to approximate to a factor larger than the expected fraction satisfied by a random ordering: i.e., all ordering CSPs are approximation resistant.
Techniques involve using mathematical relaxations to obtain local distributions, converting them into low degree functions defined over the boolean cube and using the invariance principle to analyse such function.

We show that the Densest-k-Subgraph problem is hard to approximate to any constant, assuming either: random k-AND formulas are hard to distinguish from well-satisfiable ones; or random graphs (in the Erdos-Renyi G(n, 1/2) sense) are hard to distinguish from ones containing a large clique in it. Both the results involve a simple "direct product" style result on density of size k subgraphs when the graph looks sufficiently random.

We show that for every positive epsilon, unless NP has randomized polynomial time algorithms, it is impossible to approximate the maximum quadratic assignment problem within a factor better than $2^{\log^{1-\varepsilon} n}$ by a reduction from the maximum label cover problem. Then, we present an $O(\sqrt{n})$-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms.

We prove that every permutation CSP of constant arity, k, is approximation resistant.

In this paper, we explain why the simple LP-based rounding algorithm for the Vertex Cover problem is optimal assuming the UGC. Complementing Raghavendra's result, our result generalizes to a class of strict, covering/packing type CSPs. We first write down a natural LP relaxation for this class of problems and present a simple rounding algorithm for it. The key ingredient, then, is a dictatorship test, which is parametrized by a rounding-gap example for this LP, whose completeness and soundness are the LP-value and the rounded value respectively.

Extending the results of the paper on the inapproximability of Max Acyclic Subgraph, we prove that every permutation CSP of arity 3 is approximation resistant.

We show that for $k$-way multicut, $0$-extension and metric labeling problems, a simple linear programming relaxation (known as the earthmover relaxation) provides the best approximation (upto an arbitrarily small additive error) to the optimum of a given instance of the above mentioned problems, assuming the UGC.

Maximum Acyclic Subgraph is the problem of identifying the largest subset of edges in a directed graph that do not contain a directed cycle. We prove that approximating the Maximum Acyclic Subgraph problem within a factor better than $1/2$ is Unique-Games hard. Our results also give a super-constant factor inapproximability result for the Feedback Arc Set problem. Using our reductions, we also obtain SDP integrality gaps for both the problems.

In this paper we focus on estimating the amount of information that can be embedded in the sequencing of packets in ordered channels.

We consider the task of efficiently relaying the dynamically changing data objects to the sinks from their sources of interest. We study the problem of choosing push sets and pull sets to minimize total global communication while satisfying all communication requirements.