Colloquium Details
New York Area Theory Day
Speaker: IBM/NYU/Columbia
Location: Warren Weaver Hall Auditorium 109
Date: December 6, 2019, 9:30 a.m.
Host: New York University, New York (Sponsors: DIMACS*)
Synopsis:
The Theory Day will be held at Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, Auditorium 109, New York.
Organizers:
To subscribe to our mailing list, follow instructions here.
For Directions please go here.
*Some travel support is provided by DIMACS/Simons Collaboration in Lower Bounds in Computational Complexity through NSF grant #CCF-1836666.
Program
| 9:30 - 10:00 | Coffee and bagels |
| 10:00 - 10:55 | Rafael Pass (Cornell University) Average-case Complexity through the Lens \ of Interactive Arguments (or TFNP is Hard in Pessiland). |
| 10:55 - 11:15 | Coffee break |
| 11:15 - 12:10 | Tim Roughgarden (Columbia University) Data-Driven Algorithm Design |
| 12:10 - 2:00 | Lunch break |
| 2:00 - 2:55 | Anupam Gupta (CMU) Finding and Counting K-cuts in graphs |
| 2:55 - 3:15 | Coffee break |
| 3:15 - 4:10 | Dana Ron (Tel Aviv University and Columbia University) Some faster sublinear algorithms for approximate counting and sampling on low-arboricity graphs |
Speakers
Rafael Pass (Cornell University) (Yale)
Average-case Complexity through the Lens of Interactive Arguments (or TFNP is Hard in Pessiland).
Abstract: Consider the following two fundamental open problems in complexity theory: * Does a hard-on-average language in NP imply the existence of one-way functions? * Does a hard-on-average language in NP imply a hard problem in TFNP (i.e., the class of *total* NP search problems)?
We show that the answer to (at least) one of these questions is yes. In other words, in Impagliazzo's Pessiland (where NP is hard-on-average, but one-way functions do not exist), TFNP is hard (on average).
This result follows from a more general theory of *interactive average-case complexity*, and in particular, a novel round-collapse theorem for computationally-sound interactive arguments, analogous to Babai-Moran's celebrated round-collapse theorem for interactive proofs.
Based on joint work the Muthuramakrishnan Venkitasubramaniam.
Tim Roughgarden (Columbia University)
Data-Driven Algorithm Design
Abstract: The best algorithm for a computational problem generally depends on the “relevant inputs”, a concept that depends on the application domain and often defies formal articulation. While there is a large literature on empirical approaches to selecting the best algorithm for a given application domain, there has been surprisingly little theoretical analysis of the problem.
We adapt concepts from statistical and online learning theory to reason about application-specific algorithm design. Our models are straightforward to understand, but also expressive enough to capture several existing approaches in the theoretical computer science and AI communities, ranging from self-improving algorithms to empirical performance models. We present one framework that models algorithm design as a statistical learning problem, and our work here shows that dimension notions from statistical learning theory, historically used to measure the complexity of classes of binary- and real-valued functions, are relevant in a much broader algorithmic context. We also study the online version of the algorithm selection problem, and give possibility and impossibility results for the existence of no-regret learning algorithms.
Anupam Gupta (CMU)
Finding and Counting K-cuts in graphs
Abstract: For an undirected graph, a k-way cut is a set of edges whose deletion breaks the graph into at least k pieces. How fast can we find a minimum-weight k-way cut? And how many minimum k-way cuts can a graph have? The two problems are closely linked. In 1996 Karger and Stein showed how to find a minimum k-cut in time approximately n^{2k-2}, and also that the number of minimum k-way cuts is at most n^{2k-2}. Both these results are not known to be tight, except for the case of k=2, that of finding graph min-cuts. In this talk, we report on recent progress beating these bounds. We discuss how extremal bounds for set systems, when combined with other ideas, can give near-optimal bounds for the problem.
This is joint work with Euiwoong Lee (NYU) and Jason Li (CMU)
Dana Ron (Tel Aviv University and Columbia University)
Some faster sublinear algorithms for approximate counting and sampling on low-arboricity graphs
Abstract: The arboricity of a graph is a measure of its “everywhere sparseness”. In this talk I will present several sublinear algorithms that exploit bounded arboricity to obtain faster (and tight) algorithms for approximately counting the number of edges, stars and cliques, as well as for sampling edges almost uniformly. For example, if the graph is planar (and hence has constant arboricity), then it is possible to obtain a (1+/-\epsilon)-estimate of the number of edges in expected time poly(log(n),1/\epsilon), while for general graphs the complexity is \Omega(n^{1/2}).