The SPAMS Schedule - Fall 2014

Abstract: Semidefinite programming (SDP) is a form of convex optimization that generalizes linear programming. I'll be talking about its applications to designing approximation algorithms for NP-hard problems. The first such application was the famous Goemans-Williamson algorithm for MAX-CUT which improved the trivial (1/2)-approximation to a (~0.878)-approximation. This inspired a number of other SDP-based algorithms for various problems. However, for many of these problems it remains open whether the SDP-based algorithm is optimal or whether a better approximation ratio can be achieved (assuming P is not equal to NP). The Unique Games Conjecture is a conjecture which, if true, would imply that SDP-based algorithms are in fact optimal for a wide class of problems. However, experts are still in debate over whether the conjecture is likely to be true or not.

Abstract: The theoretical study of computer program obfuscation, or attempting to conceal implementation details of a program, seemed to be dead after a 2001 impossibility result by Barak et al. A recent candidate construction of a weak obfuscation primitive called "indistinguishability obfuscation" has enabled the solution of many open problems in cryptography. A current topic of research aims to base all of cryptography on just the existence of indistinguishability obfuscation (and one-way functions).

In my talk, I will define all these things and show how indistinguishability obfuscation is used to prove the security of constructions which we don't know how to otherwise achieve.

Abstract: Much like sorting is a primitive operation in computer science, search is a fundamental operation in computational biology and lies at the heart of many other problems. Note, though, that we refer not to the problem of exact search, but rather instead approximate, or similarity search, where we wish to find all entries in a database that are similar to some search query. Local alignment of sequences, for which BLAST or BLAT are the most popular approaches, is the most obvious manifestation of this problem in genomics. However, approximate search also plays a central role in many other algorithms, for example the quality score compression method I presented at SPAMs last fall.

Although this problem has been studied generically for years (e.g. approximate string matching for spell-checkers), we are able to exploit the additional structure (dataset redundancy, strictly limited search radii, etc.) present in biological data for greater gains. In this talk, I'll present a couple of data structures that have been used for accelerating specific instances of similarity search in computational biology. Additionally, time permitting, I'll discuss (in broad strokes) how we can take some of the insights gained from studying biological data to improve similarity search in other domain areas.

Abstract: A problem of classical physics asks: given a resistor network embedded in a disk with finitely many batteries at the boundary, what are the resulting currents near the batteries after certain voltages are imposed? This can be computed with linear algebra: you can write down a linear map that takes in voltages and spits out the currents. Conversely, if you know this map (i.e. you know everything about the boundary measurements), can you recover the resistor network? This "inverse boundary problem" was studied by Curtis-Ingerman-Morrow and de Verdiere-Gitler-Vertigan in the 1990s, and the answer is "sort of." I will explain some of this story, in addition to some more recent joint work with Alman and Tran suggesting connections to modern algebraic combinatorics.

Abstract: The planted clique problem asks whether or not we can find a k-clique which is planted in a random G(n,1/2) graph. Although the expected size of the largest clique in a random graph is only 2lg(n), we currently do not know of any polynomial time algorithm which can find a planted clique of size much smaller than n^(1/2). The sum of squares hierarchy is a hierarchy of approximation algorithms, each more powerful than the last. These algorithms are some of the most powerful approximation algorithms we know of and their performance on many problems is not well understood. In fact, until very recently there were no non-trivial bounds on the performance of the sum of squares hierarchy on the planted clique problem! In this talk, I will present the first non-trivial bounds for this question, describing the planted clique problem, the sum of squares hierarchy, and how we can show that the sum of squares hierarchy fails to find the planted clique if its size k is sufficiently small.

Abstract: In this talk we will explore the geometry of Gaussian space and its connections to the geometry of the hypercube. We will describe Borell's isoperimetric inequality and Bobkov's proof of it (in a special case) by reduction to the boolean case, and its discrete analogue, the Majority is stablest theorem, and their applications to theoretical computer science.