| ELC Mini Workshop (C01)
Dec. 17th (Thu): 14:00 - 17:00
CELC Seminar Room (Tokyo Tech. CIC 4F)
Group C01 is going to organize a mini workshop having three imporatnt
visitors, Raghunath Tewari, Hubie Chen, and Luca Trevisan.
We are planning to go somewhere nearby for dinner welcoming the
visitors. Please let me know if any one wants to join us.
Osamu Watanabe, watanabe@is.titech.ac.jp
14:00-15:00
Speaker: Raghunath Tewari (IIT Kanpur)
Title: Simultaneous Time-Space Bounds for the Graph Reachability Problem
Abstract:
Graph reachability is a fundamental problem in computer science and
understanding it's computational complexity is of utmost importance.
There exists linear time algorithms for this problem such as BFS and
DFS however both these algorithms also require a linear amount of space.
In 1970 Savitch showed that directed graphs reachability can be
decided in $O(\log^2 n)$ space. However his algorithm requires
$\Omega(n^{\log n})$ time. This gave rise to the following question
-- can we decide reachability in polynomial time and polylogarithmic
space simultaneously? In 1992, Barnes, Buss, Ruzzo and Schieber
made some progress by giving a polynomial time and
$O(n/2^{\sqrt{\log n}})$ space algorithm for this problem.
In this talk, I will present some recent progress on this problem,
particularly for certain classes of topologically restrictive
graphs such as planar graphs, bounded genus graphs and
minor-free graphs.
15:15-15:45
Speaker: Hubie Chen (Univ. del Pai's Vasco & IKERBASQUE)
Title: Parameter Compilation
Abstract:
In resolving instances of a computational problem, if multiple
instances of interest share a feature in common, it may be
fruitful to compile this feature into a format that allows
for more efficient resolution, even if the compilation is
relatively expensive. In this article, we introduce a formal
framework for classifying problems according to their
compilability. The basic object in our framework is that of a
parameterized problem, which here is a language along with
a parameterization---a map which provides, for each instance,
a so-called parameter on which compilation may be performed.
Our framework is positioned within the paradigm of parameterized
complexity, and our notions are relatable to established concepts
in the theory of parameterized complexity. Indeed, we view
our framework as playing a unifying role, integrating
together parameterized complexity and compilability theory.
A version of the article is available on the arxiv:
http://arxiv.org/abs/1503.00260
16:00-17:00
Speaker: Luca Trevisan (UC Berkley)
Title: The Approximability of Non-Boolean Constraint Satisfaction Problem
Abstract:
We study constraint satisfaction problems in which we are given a set
of constraints such that each constraint involves at most k variables,
and each variable ranges over a finite set of R possible values, and
we want to find an assignment that satisfies the largest number of
constraints.
It was known that, for fixed k, the problem admits a polynomial time
algorithm that satisfies at least c/R^{k-1} times the optimum number
of constraints, where c is a constant, and that an approximation
better than c'/R^{k-2} is NP-hard, where c' is a different constant.
We give a polynomial time algorithm, based on semidefinite
programming, that achieves an approximation ratio of the order of (log
R)/R^{k-1}, and we show that approximation better than order of (log
R)^{k/2} / R^{k-1} is impossible in polynomial time, assuming the
unique games conjecture.
Based on joint work with Guy Kindler, Alexandra Kolla, Pasin
Manurangsi and Preetum Nakkiran
|