ELC Workshop on Inapproximability

Information

Registration for Reception (on January 25; fee: approx. 3,500 JPY)

Program

Abstracts

Nisheeth Vishnoi (Microsoft Research India)
Title: Inapproximability
Abstract: Many optimization problems of theoretical and practical interest are NP-hard, meaning it is impossible to compute exact solutions to these problems in polynomial time unless P=NP. A natural way to cope with NP-hardness is to sacrifice exactness for efficiency and seek approximate solutions, i.e., design algorithms that find a solution which is guaranteed to be close to optimal for any given input. A bit more formally, an algorithm is said to have an approximation ratio C for an optimization problem if, for each of its instances, the algorithm outputs a solution whose cost is within a factor C of the optimum for that instance. NP-hard problems exhibit a wide range of behavior in how well they can be approximated and the areas of approximation algorithms and hardness of approximation address the two facets of the following question:
How close can polynomial-time algorithms come to finding optimal solutions for NP-hard problems?
One aspect is, naturally, designing such approximation algorithms. The other facet is proving inapproximability results; results that rule out the possibility of good approximation algorithms (under assumptions such as P!=NP). In this talk, I will give a bird's eye view of the deep, rich and vibrant area of inapproximability which combines tools from algebra, analysis and geometry to establish inapproximability of innocuous looking NP-hard problems.

Samuel Fiorini (Universite Libre de Bruxelles)
Title: Approximation Limits of Linear Programs (Beyond Hierarchies)
Abstract: We develop a framework for proving approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to *any* linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that $O(n^{1/2-\epsilon})$-approximations for CLIQUE require linear programs of size~$2^{n^{\Omega(\epsilon)}}$. This lower bound applies to linear programs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by linear programs.

Our main technical ingredient is a quantitative improvement of Razborov's rectangle corruption lemma (1992) for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.

This is joint work with Gábor Braun (Georgia Tech), Sebastian Pokutta (Georgia Tech) and David Steurer (Cornell).

Danupon Nanongkai (Nanyang Technological University)
Title: Graph Products and Hardnesses of Approximation
Abstract: I will present a simple framework for proving hardnesses of approximation based on graph products. In contrast to most of the hardness proofs nowadays which require heavy machineries, this framework requires one to simply prove some graph product inequalities in order to prove non-trivial approximation hardnesses. This simple technique has led to new, tight, hardness results for many problems, including Induced Matching, Poset Dimension, Hypergraph Pricing, Edge-Disjoint Paths, and Coloring Graph Powers. In this talk, I will explain this technique and some of its applications.

Results presented in this talk are based on joint papers with Bundit Laekhanukit (McGill University) and Parinya Chalermsook (Max-Planck-Institut fur Informatik) that appeared in FOCS 2013 and SODA 2013, and to appear in LATIN 2014. This talk will not assume any background of the audience except some basic knowledge in graph theory.

Kenya Ueno (Kyoto University)
Title: Inapproximability of Linear Programs for The Universal Relation
Abstract: We overview linear programming based approaches for proving formula size lower bounds with their limitations. In particular, we consider the universal relation which subsumes formula complexity of all Boolean functions. We can prove the limitations of lower bound methods by proving the upper bound for the universal relation. We interpret the limitations from the viewpoint of inapproximability and discuss possible research directions.

Michael Lampis (Kyoto University)
Title: Baby steps towards TSP inapproximability
Abstract: Although the Traveling Salesman Problem is one of the most intensely studied problems in combinatorics, the best currently known hardness of approximation bounds are a long way off the guarantee provided by the best approximation algorithms. In this talk we will discuss two recent hardness proofs which slightly improve the inapproximability bounds for both TSP and ATSP, after more than a decade. Though the gap between upper and lower bounds remains huge, our approach will emphasize simplicity and modularity, leaving some reasonable hope that further improvements are still possible. The main ingredients used will be Constraint Satisfaction Problems where each variable appears a bounded number of times, some special classes of expander-like graphs called amplifiers, and a healthy dose of gadgeteering.

Sevag Gharibian (University of California at Berkeley)
Title: Quantum constraint satisfaction and approximation
Abstract: Over the last decade, the quantum computing and information community has devoted much effort to the study of Quantum Constraint Satisfaction Problems (Quantum CSPs). There are two reasons for this: First, Quantum CSPs naturally generalize well-studied classical problems such as 3SAT. Second, and potentially more importantly, Quantum CSPs are extremely well-motivated, in that they encode the behavior of the quantum world around us. In this talk, we define what a Quantum CSP is, and discuss recent results regarding the potential for classical approximation algorithms for such problems. In particular, we show the first known hardness of approximation results for a quantum complexity class.

This talk is based on joint work with Julia Kempe. No background in quantum mechanics is assumed.

Kiyohito Nagano (Future University Hakodate)
Title: Information-theoretic lower bounds on the approximability of submodular optimization problems
Abstract: In this talk, we will explain some techniques that allow us to give information-theoretic lower bounds on the approximability of NP-hard submodular optimization problems.

Organizers