Titles and Abstracts

CSE Building

Petros Drineas, RPI
Randomized algorithms for the least-squares approximation problem

L2 regression, also known as the least squares approximation problem, is a fundamental problem that has numerous applications in mathematics and statistical data analysis. Recall that the over-constrained L2 regression problem takes as input an n-by-d matrix A, where n > d, and an n-vector b, and it returns as output a d-vector x such that the sum of the squares of the vector Ax-b is minimized. Randomized algorithms for this problem, each of which provides a relative-error approximation to the exact solution, will be described. The first algorithm applies novel ``subspace sampling'' probabilities to randomly sample constraints and thus construct a coreset for the L2 regression problem. The second algorithm uses the Fast Johnson-Lindenstrauss Transform to obtain an efficient approximation to the L2 regression problem. We will conclude with extensions of the above ideas to general Lp regression, for all $p\in[1,\infty)$. Applications of these random projection and random sampling algorithms to data analysis will be briefly discussed.

slides

Kevin Compton, Michigan
A Probabilistic Transform for Algorithms on Random Permutations with a Specified Number of Inversions

(Joint work Jonathan Brown)

Adaptive algorithms take into account statistical characteristics of a data set in order to achieve greater efficiency. For example, adaptive sorting algorithms may first sample the data to estimate the number of inversions (pairs of out-of-order elements); this estimate determines which classical sorting algorithm should be applied. This approach leads to the problem of expected case analysis on sets of random permutations with a specified number of inversions. An analogous situation arises in the expected case analysis of hashing algorithms where we consider random functions from a set of a specified size into a set of table locations. Solutions to problems in this area use the so-called Poisson transform and its inverse (notions due to Gonnet and Munro). We briefly describe the Poisson transform, then show how a new transform and its inverse offer similar solutions to analysis of algoritms on random permutations with a specified number of inversions.

Varsha Dani, Chicago
Stochastic Linear Optimization under Bandit Feedback

In the classical stochastic k-armed bandit problem, in each of a sequence of T rounds, a decision maker chooses one of k arms (of a slot machine) and receives a reward chosen from an unknown distribution associated with the chosen arm. The goal is to minimize regret, i.e. the difference between the optimal reward and the reward obtained by the algorithm.

We study the linear optimization version of this problem where the "arms" are vectors in R^n , and require that the rewards be linear functions of the chosen vector. The reward functions are sampled independently from an unknown distribution. In this setting, the goal is to find algorithms whose running time and regret behave well as functions of the number of rounds T and the dimensionality n (rather than the number of arms, k, which may be exponential in n or even infinite). We give a nearly complete characterization of this problem in terms of both upper and lower bounds for the regret.

Joint work with Tom Hayes and Sham Kakade.

Ye Du, Michigan
The Computation of Approximate Competitive Equilibrium is PPAD-hard

Arrow and Debreu showed in 1954 that, under mild conditions, a competitive economy always has an equilibrium. In this paper, we show that, given a competitive economy that fully respects all the conditions of Arrow-Debreu's existence theorem, for any positive constant $h>0$, it is PPAD-hard to compute a $\frac{1}{n^{h}}$-approximate competitive equilibrium.

This is a joint work with Xiaotie Deng.

Ran Duan, Michigan
Bounded-leg distance and reachability oracles

In a weighted, directed graph an L-bounded leg path is one whose constituent edges have length at most L. For any fixed L, computing L-bounded leg shortest paths is just as easy as the standard shortest path algorithm. We study approximate distance oracles (and reachability oracles) for bounded-leg path problems, where the leg bound L is not known in advance, but forms part of the query. Bounded-leg path problems are more complicated than standard shortest path problems because the number of distinct shortest paths between two vertices (over all leg bounds) could be as large as the number of edges in the graph. We also consider bounded leg reachability oracles in other situations. In the context of planar directed graphs we give a time-space tradeoff for answering bounded leg reachability queries.

Anna Gilbert, Michigan
Combining geometry and combinatorics: a unified approach to sparse signal recovery

There are two main algorithmic approaches to sparse signal recovery: geometric and combinatorial. The geometric approach starts with a geometric constraint on the measurement matrix Phi and then uses linear programming to decode information about x from Phi x. The combinatorial approach constructs Phi and a combinatorial decoding algorithm to match. We present a unified approach to these two classes of sparse signal recovery algorithms. The unifying elements are the adjacency matrices of high-quality unbalanced expanders. We generalize the notion of Restricted Isometry Property (RIP), crucial to compressed sensing results for signal recovery, from the Euclidean norm to the l_p norm for p >= 1, and then show that unbalanced expanders are essentially equivalent to RIP-p matrices. From known deterministic constructions for such matrices, we obtain new deterministic measurement matrix constructions and algorithms for signal recovery which, compared to previous deterministic algorithms, are superior in either the number of measurements or in noise tolerance.

Joint work with R. Berinde, P. Indyk, H. Karloff, and M. Strauss

Joshua Grochow, Chicago
Complexity Classes of Equivalence Problems

Equivalence problems -- like graph isomorphism (GI) or circuit equivalence -- play a nearly unique role in complexity theory as some of the few candidates for natural problems of intermediate complexity (e.g. in NP, not in P, but not NP-complete either). Almost all algorithmic techniques for these problems are one of two types: canonical forms and complete invariants. A complete invariant for, say, graph isomorphism is a function f such that G is isomorphic to H iff f(G)=f(H). A canonical form for GI is a complete invariant with the further caveat that for every G, f(G) is a graph isomorphic to G. We ask whether such techniques are essentially necessary to place an equivalence problem in P. (For GI the answer is known to be yes: if GI is in P then GI has a canonical form in FP.)

To study this question we introduce three new complexity classes and study the relationships between them:

PEq is the class of equivalence problems in P; Ker(FP) is the class of equivalence problems with a polynomial-time complete invariant; CF(FP) is the class of equivalence problems with a polynomial-time canonical form.

It is clear that CF \subseteq Ker \subseteq PEq. In this preliminary work, our main results are:

1. Oracles relative to which a) all three classes are distinct, b) all three classes are the same, and c) CF = Ker \neq PEq.
2. If CF=Ker then factoring can be done in probabilistic polynomial time.
3. If Ker=PEq then UP \subseteq BQP. If CF=PEq then UP \subseteq RP.

We also pose several open problems regarding generalizations of these classes beyond polynomial time, reductions between equivalence problems, and sufficient conditions to strengthen the the above result (3) from UP to NP.

Joint work with Lance Fortnow.