[CSDM] CCI meeting - Friday, Sept. 13

[Andrew Drucker]

The Center for Computational Intractability (CCI) will have its first
meeting of the academic year this Friday, featuring talks by some of our
new postdoctoral members---welcome!  The abstracts appear below the
schedule.

All talks are open to the public. Please note the slightly nonstandard
times.
*
*
*
*
*Location:*  Room 402, Princeton Computer Science building, 35 Olden St.
*
*
*Schedule:*

10:00-10:45am:  PI meeting  (PIs only)

10:45-11:15:  Pranjal Awasthi:  Approximation Algorithms and New Models for
Clustering and Learning

11:15-11:45:  Edinah K. Gnang:  Computational aspects of the Combinatorial
Nullstellensatz method via a polynomial approach to matrix and hypermatrix
algebra

11:45-2:00:  Lunch break (Princeton CS department picnic; CCI meeting
attendees are invited)

2:00-2:30:  Alina Ene:   Routing on Disjoint Paths and Related Problems

2:30-3:00:  Mark Lewko:  Finite field restriction estimates

3:00-3:30:  Siu Man Chan:  Deeper Combinatorial Lower Bounds



*Talk abstracts:*


*Approximation Algorithms and New Models for Clustering and Learning
*
Speaker: Pranjal Awasthi

Abstract: In this talk I will first describe my work on the study of
clustering
problems, specifically the k-means and the k-median clustering objectives.
To study these problems we take a different approach than the traditional
worst case analysis models. We show that by looking at certain well
motivated stable instances, one can design much better
approximation algorithms for these problems. Our algorithms achieve
arbitrarily good approximation factors on stable instances, something which
is provably hard on worst case instances.

In the second part of the talk I will describe some recent work on the
study of new theoretical models both for learning and clustering. I will
motivate the need for these new models and will present open problems and
directions for future work.



*****


*Computational aspects of the Combinatorial Nullstellensatz method via a
polynomial approach to matrix and hypermatrix algebra *

Speaker:  Edinah K. Gnang

Abstract: In this talk we discuss a polynomial encoding which provides a
unified framework for discussing the algebra and the spectral analysis of
matrices and hypermatrices. In addition to describing some algorithms for
performing orthogonalization and spectral analysis of hypermatrices, we
discuss some computational aspects, more specifically the important role of
symmetries in Alon's Combinatorial Nullstellensatz method for solving
combinatorial problems.


*****


*Routing on Disjoint Paths and Related Problems
*
Speaker:  Alina Ene

Abstract: In this talk, we consider some fundamental maximum throughput
routing problems in undirected and directed graphs. In this setting, we are
given a capacitated undirected or directed graph. We are also given
source-destination pairs of nodes (s_1, t_1), (s_2, t_2), …, (s_k,
t_k).  The goal is to select a largest subset of the pairs that are
simultaneously routable subject to the capacities; a set of pairs is
routable if there is a multicommodity flow for the pairs satisfying
certain constraints that vary from problem to problem (e.g.,
integrality, unsplittability, edge or node capacities). Two
well-studied optimization problems in this context are the Maximum
Edge Disjoint Paths (MEDP) and its node-capacitated counterpart, the
Maximum Node Disjoint Paths (MNDP) problem. In MEDP and MNDP, a set
of pairs is routable if the pairs can be connected using
edge-disjoint and node-disjoint paths, respectively.

MEDP and MNDP are both NP-hard and their approximability has
attracted substantial attention over the years. Over the last decade,
several breakthrough results on both upper bounds and lower bounds
have led to a much better understanding of these problems. At a high
level, one can summarize this progress as follows.  MEDP and MNDP
admit poly-logarithmic approximations in undirected graphs if one
allows constant congestion, i.e., the routing violates the capacities
by a constant factor. Moreover, these problems are hard to
approximate within a poly-logarithmic factor in undirected graphs
even if one allows constant congestion. In sharp contrast, both
problems are hard to approximate to within a polynomial factor in
directed graphs even if a constant congestion is allowed and the
graph is acyclic. If we are not allowed any congestion, the best
approximation known are polynomial and it is a long-standing open
problem to improve these guarantees in undirected graphs.

In this talk, we give a brief overview of some of the challenges in
routing on disjoint paths in both undirected and directed graphs,
with a focus on open problems and directions for future research. In
undirected graphs, we consider the setting in which we are not
allowed any congestion, and we highlight some ongoing efforts to get
improved approximations for restricted graph classes. In directed
graphs, we consider the setting in which the demand pairs are
symmetric and we are allowed congestion. The strong lower bounds that
are known for routing in directed graphs rely on the asymmetry of the
demands and we give some evidence that the symmetric setting is much
more tractable than the asymmetric setting.

This talk is based on joint work with Julia Chuzhoy (TTI-C) and
Chandra Chekuri (UIUC).


******


*Finite field restriction estimates*

Speaker:  Mark Lewko

Abstract:  The Kakeya and restriction conjectures are two central open
problems in Euclidean Fourier analysis (with the second logically implying
the first, and progress on the first typically implying progress on the
second). Both of these have formulations over finite fields. In 2008 Dvir
completely settled the finite field Kakeya conjecture, however neither this
result nor the proof method have yet yielded any progress on the finite
field restriction conjecture. In this talk I will describe some recent
progress on the finite field restriction conjecture, improving the
exponents of Mockenhaupt and Tao. The key new ingredient is the use of
incidence / sum-product estimates. [A longer talk on this topic will be
given in the IAS CSDM seminar on 9/24/2013


*****


*Deeper* *Combinatorial Lower Bounds*

Speaker: Siu Man Chan

Abstract: We will discuss some classical and recent results on space
and parallel complexity, in particular the study of combinatorial
lower bounds in restricted settings, and highlight some of their
connections to boolean complexity, proof complexity, and algebraic
complexity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20130909/1a42f5cf/attachment-0001.html>