<div dir="ltr"><br><div><span class="Apple-style-span" style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><div class="im" style="color:rgb(80,0,80)"><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><div>
<font color="#000000">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. </font></div>
</span><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br></font></span></div></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><div class="im" style="color:rgb(80,0,80)">
<font color="#000000">All talks are open to the public. Please note the slightly nonstandard times.</font><div><font color="#000000"><u><br></u></font></div><div><font color="#000000"><u><br></u></font></div></div><div><font color="#000000"><u>Location:</u> Room 402, Princeton Computer Science building, </font><span class="Apple-style-span" style="color:rgb(0,0,0)">35 Olden St. </span></div>
<div><font color="#000000"><u><br></u></font></div><div><div><div><div><u><font color="#000000">Schedule:</font></u></div><div><font color="#000000"><br></font></div><div><font color="#000000">10:00-10:45am: PI meeting (PIs only)</font></div>
<div class="im" style="color:rgb(80,0,80)"><div><font color="#000000"><br></font></div><div><font color="#000000">10:45-11:15: Pranjal Awasthi: </font><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">Approximation Algorithms and New Models for Clustering and Learning</font></span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br></font></span></div></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">11:15-11:45: </font></span><span>Edinah K. Gnang: Computational aspects of the Combinatorial Nullstellensatz method via a polynomial approach to matrix and hypermatrix algebra</span></div>
<div><font color="#000000"><br></font></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><span style="font-size:13px"><div class="im" style="color:rgb(80,0,80)"><div><font color="#000000">11:45-2:00: Lunch break (Princeton CS department picnic; CCI meeting attendees are invited)</font></div>
<div><font color="#000000"><br></font></div></div><div><font color="#000000">2:00-2:30: </font><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">Alina Ene: </font></span><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"> Routing on Disjoint Paths and Related Problems</font></span></div>
<div class="im" style="color:rgb(80,0,80)"><div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><span style="font-size:13px"></span></span></font></div></div><div><span style="border-collapse:separate;font-family:arial;font-size:small"><div>
<span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br></font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">2:30-3:00: Mark Lewko: </font></span><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">Finite field restriction estimates</font></span></div>
</span></div></div></span></span></font></div><div class="im" style="color:rgb(80,0,80)"><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br></font></span></font></div><div>
<span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">3:00-3:30: Siu Man Chan: Deeper Combinatorial Lower Bounds</font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br>
</font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br></font></span></div></div><div><div><div class="im" style="color:rgb(80,0,80)"><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br>
</font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><u><font color="#000000">Talk abstracts:</font></u></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br>
</font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br></font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><b><font color="#000000">Approximation Algorithms and New Models for Clustering and Learning<br>
</font></b><font color="#000000"><br></font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">Speaker: Pranjal Awasthi<br><br>Abstract: In this talk I will first describe my work on the study of clustering<br>
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.<br>
<br>In the second part of the talk I will describe some recent work on the<br>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.<br>
</font></span></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br></font></span></font></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br>
</font></span></div><div><font color="#000000"><br></font></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><span style="border-collapse:separate;font-family:arial;font-size:small"><div>
<font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000">*****</font></span></font></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br>
</font></span></font></div></span></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br></font></span></div></div><div class="im" style="color:rgb(80,0,80)">
<div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><b><font color="#000000">Computational aspects of the Combinatorial Nullstellensatz method via a polynomial approach to matrix and hypermatrix algebra </font></b><font color="#000000"> </font></span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br></font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">Speaker: Edinah K. Gnang</font></span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br></font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">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. <br>
</font></span></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br></font></span></font></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br>
</font></span></div></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><span style="border-collapse:separate;font-family:arial;font-size:small"><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000">*****</font></span></font></div>
<div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br></font></span></font></div><div><font class="Apple-style-span" color="#000000" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse:collapse"><br>
</span></font></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><span style="font-size:13px;color:rgb(80,0,80)"><div><div class="im" style="color:rgb(80,0,80)"><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><b><font color="#000000">Routing on Disjoint Paths and Related Problems<br>
</font></b><font color="#000000"><br></font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">Speaker: Alina Ene</font></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000"><br>
Abstract: </font></span><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">In this talk, we consider some fundamental maximum throughput routing </font></span><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">problems in undirected and directed graphs. In this setting, we are</font></span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">given a capacitated undirected or directed graph. We are also given<br>source-destination pairs of nodes (s_1, t_1), (s_2, t_2), …, (s_k,<br>
t_k). The goal is to select a largest subset of the pairs that are<br>simultaneously routable subject to the capacities; a set of pairs is<br>routable if there is a multicommodity flow for the pairs satisfying<br>certain constraints that vary from problem to problem (e.g.,<br>
integrality, unsplittability, edge or node capacities). Two<br>well-studied optimization problems in this context are the Maximum<br>Edge Disjoint Paths (MEDP) and its node-capacitated counterpart, the<br>Maximum Node Disjoint Paths (MNDP) problem. In MEDP and MNDP, a set<br>
of pairs is routable if the pairs can be connected using<br>edge-disjoint and node-disjoint paths, respectively.<br><br>MEDP and MNDP are both NP-hard and their approximability has<br>attracted substantial attention over the years. Over the last decade,<br>
several breakthrough results on both upper bounds and lower bounds<br>have led to a much better understanding of these problems. At a high<br>level, one can summarize this progress as follows. MEDP and MNDP<br>admit poly-logarithmic approximations in undirected graphs if one<br>
allows constant congestion, i.e., the routing violates the capacities<br>by a constant factor. Moreover, these problems are hard to<br>approximate within a poly-logarithmic factor in undirected graphs<br>even if one allows constant congestion. In sharp contrast, both<br>
problems are hard to approximate to within a polynomial factor in<br>directed graphs even if a constant congestion is allowed and the<br>graph is acyclic. If we are not allowed any congestion, the best<br>approximation known are polynomial and it is a long-standing open<br>
problem to improve these guarantees in undirected graphs.<br><br>In this talk, we give a brief overview of some of the challenges in<br>routing on disjoint paths in both undirected and directed graphs,<br>with a focus on open problems and directions for future research. In<br>
undirected graphs, we consider the setting in which we are not<br>allowed any congestion, and we highlight some ongoing efforts to get<br>improved approximations for restricted graph classes. In directed<br>graphs, we consider the setting in which the demand pairs are<br>
symmetric and we are allowed congestion. The strong lower bounds that<br>are known for routing in directed graphs rely on the asymmetry of the<br>demands and we give some evidence that the symmetric setting is much<br>more tractable than the asymmetric setting.<br>
<br>This talk is based on joint work with Julia Chuzhoy (TTI-C) and<br>Chandra Chekuri (UIUC).</font></span></div></div></div></span></font></span></font></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br>
</font></span></font></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br></font></span></font></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000">******</font></span></font></div>
<div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br></font></span></font></div></span></span></div><div class="im" style="color:rgb(80,0,80)"><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br>
</font></span></font></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><div><b><font color="#000000">Finite field restriction estimates</font></b></div><div><font color="#000000"><br>
</font></div><div><span style="border-collapse:separate;font-family:arial;font-size:small"><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">Speaker: Mark Lewko</font></span></div>
<div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br></font></span></font></div></span></div><font color="#000000">Abstract: </font></span><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><font color="#000000">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 </font><span style="border-bottom-width:1px;border-bottom-style:solid;border-bottom-color:rgb(100,100,100)"><span><font color="#000000">9/24/2013</font></span></span></span></div>
</div></div></div></div></div></div><div class="im" style="color:rgb(80,0,80)"><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><span style="border-bottom-width:1px;border-bottom-style:solid;border-bottom-color:rgb(100,100,100)"><span><font color="#000000"><br>
</font></span></span></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><span style="border-bottom-width:1px;border-bottom-style:solid;border-bottom-color:rgb(100,100,100)"><span><font color="#000000"><br>
</font></span></span></span></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><span style="border-bottom-width:1px;border-bottom-style:solid;border-bottom-color:rgb(100,100,100)"><span><div>
<span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><span style="border-collapse:separate;font-family:arial;font-size:small"><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000">*****</font></span></font></div>
<div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br></font></span></font></div></span></span></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><br>
</font></span></font></div><div><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse"><div><b><font color="#000000">Deeper</font></b><font color="#000000"> </font><b><font color="#000000">Combinatorial Lower Bounds</font></b></div>
</span><div><font color="#000000"><br></font></div><div><font color="#000000">Speaker: Siu Man Chan</font></div><font color="#000000"><br>Abstract: We will discuss some classical and recent results on space<br>and parallel complexity, in particular the study of combinatorial<br>
lower bounds in restricted settings, and highlight some of their<br>connections to boolean complexity, proof complexity, and algebraic<br>complexity.</font></div></span></span></span></div></div></span></div></span></div>
</div>