Workshop Details

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.

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.

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)

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}).