SPEAKER: Don Sheehy
TIME: Wednesday 12-1pm, May 2, 2007.
PLACE: NSH 1507
TITLE: A Competitive Algorithm for No-Large-Angle Triangulation
ABSTRACT:
In this talk, I will present Overlay Stitch Meshing, a novel new algorithm that simultaneously solves two different problems in the field of triangulating planar straight-line graphs in the plane for scientific computing applications:
1. It is the first Delaunay Refinement-type triangulation algorithm that terminates with a full complement of guarantees even on degenerate inputs and with no dependence on the size of the smallest input angle.
2. It is the first algorithm that gives a log n competitive output size for the problem of no-large-angle triangulation with Steiner points.
The workings of the algorithm are very easy to state and understand. The brunt of the talk will focus on new analytic techniques that allow us to prove strong guarantees.
May 3, 2007
Ioannis Koutis
3:30 PM, 3305 Newell-Simon Hall
Thesis Oral
Title: Combinatorial and Algebraic Tools for Optimal Multilevel Algorithms
Abstract:
This dissertation presents combinatorial and algebraic tools that enable the design of the first linear work parallel iterative algorithm for solving linear systems involving Laplacian matrices of planar graphs. The major departure of this work from prior suboptimal and inherently sequential approaches is centered around: (i)the partitioning of planar graphs into fixed size pieces that share small boundaries, by means of a local “bottom-up” approach that improves the customary “top-down” approach of recursive bisection, (ii) the replacement of monolithic global preconditioners by graph approximations that are built as aggregates of miniature preconditioners.
In addition, we present extensions to the theory and analysis of Steiner tree preconditioners and we construct more general Steiner graphs that lead to natural linear time solvers for classes of graphs that are known a priori to have certain structural properties. We also present a graph-theoretic approach to classical algebraic multigrid algorithms. We show that their design can be recast as the construction of Steiner graph preconditioners. This observation makes the analysis of multigrid amenable to support theory tools and leads to the design of linear work parallel algorithms that can be as fast as currently used heuristics, but also provide strict guarantees.
Thesis Committee:
Gary Miller, Chair
Alan Frieze
John Lafferty
Daniel Spielman, Yale University
Title : Misere quotients for impartial games
Speaker : Aaron Siegel, Institute for Advanced Study
When : 4:30 – 5:30pm, April 26
Where : PPB 300
Abstract:
In 1935, T. R. Dawson, the prolific composer of fairy chess problems, invented a little game now known as Dawson’s Chess, involving only pawns on a 3xN chessboard. He invested considerable effort trying to find a perfect winning strategy, but was ultimately unsuccessful.
We now know that much of Dawson’s difficulty arose from the winning condition he imposed on the game: whoever makes the last move loses. This is known as the misere play condition. The normal-play counterpart of Dawson’s Chess—in which the player who makes the last move wins—was solved in 1956, but the original misere-play formulation remains an open problem, after more than seventy years.
This is no accident: games with the misere play condition tend to be vastly more difficult than games with the normal play condition (even when the rules are otherwise identical). As a result, many authors have dismissed the misere theory as essentially intractable.
However, a recent breakthrough, due to Thane Plambeck, has sparked renewed interest. Plambeck showed that much of the misere-play theory for a specific game G can be localized to a certain commutative monoid, the misere quotient of G. I will describe Plambeck’s construction, and show how the misere quotient contains exactly enough information to recover a perfect winning strategy for G. Then I’ll present misere quotients for several previously unsolved games and discuss what little we know about the general structure theory of misere quotients. Finally, I’ll (hopefully) shed some light on just why no one has yet solved Dawson’s Chess.
SPEAKER: Moritz Hardt
TIME: Wednesday 12-1pm, April 25, 2007
PLACE: NSH 1507
TITLE: Arithmetic Circuit Identity Testing for Sparse Polynomials
ABSTRACT:
We give a deterministic identity test for multivariate polynomials represented by arithmetic circuits. The runtime of our algorithm is polynomial in $s$ and $m$, where $s$ is the size of the circuit and $m$ the number of monomials of the given polynomial. Our technique applies to arbitrary polynomial rings. We can improve the runtime significantly with few random bits.
Title : Random Cubic Sum Graphs
Speaker : Andrew Beveridge
When : 4:30-5:30pm April 19
Where : PPB 300
Abstract:
Consider set of all graphs whose nodes are labeled with non-identity elements of the n-dimensional hypercube so that there is an edge between nodes with labels $a$ and $b$ if and only if the node $a+b$ is also in the graph (where $a+b$ is the group operation).
A random cubic sum graph is a randomly chosen element from this set where each vertex is included independently with probability $p$. As $p$ increases from $0$ to $1$, the expected structure undergoes radical changes. As with classical random graphs, we obtain thresholds functions for graph properties. In this talk, we characterize the threshold for the appearance of the first triangle, the threshold for isolated triangles and the threshold for connectivity.
Friday April 20th, 2007
3:30pm, WEH 7220
Robust Reductions from Ranking to Classification
Alina Beygelzimer, IBM Watson
We show how to convert any binary classifier learning algorithm into a ranking algorithm. The reduction is robust in the sense that it transforms classification regret R into AUC regret at most 2R. We show that this bound is tight and that the reduction provides the same regret transform as an optimal solution to the (NP-hard) feedback arc set problem. (Regret of an algorithm on a given problem is the difference between the loss incurred by the algorithm and the loss of the best predictor on the same problem.) This is a large improvement over commonly used approaches such as ordering according to regressed scores, which have a regret transform of R->NR, where N is the number of elements.
Joint work with Nina Balcan, Nikhil Bansal, Don Coppersmith, John Langford, and Greg Sorkin. To appear in COLT-07.
SPEAKER: Doru Balcan
TIME: Wednesday 12-1pm, April 18, 2007
PLACE: NSH 1507
TITLE: Characterization of Robust Linear Coding Solutions
ABSTRACT:
Many linear encoding approaches focus on representing information by approximating the underlying statistical density of the data, like PCA or ICA, or by developing encoding/decoding algorithms with desirable computational and representational properties, such as Fourier and wavelet-based codes. However, if the coefficients’ precision is limited, optimality of the representation cannot be guaranteed. The issue of optimality under limited precision is a common practical concern, and it is also relevant to biological neural representations, where the coding precision of individual neurons has been reported to be as low as a few bits per spike. In this talk, I will present a new coding scheme called Robust (Linear) Coding, that makes use of arbitrarily many coding units to minimize reconstruction error. One characteristic of Robust Coding is that it can introduce redundancy in the code to compensate for channel noise, unlike PCA or ICA, which aim to reduce redundancy. We can completely analyze the under- and overcomplete cases, and identify necessary and sufficient conditions of the optimal encoder/decoder pair in each case. In the process, we find an exact formula for the lower bound of the error function, as well as an efficient procedure for computing the optima.
Joint work with Eizaburo Doi and Mike Lewicki.
Friday, April 13th, 2007
Wean Hall 7220
3:30pm
Title: Smooth Sensitivity and Sampling in Private Data Analysis
Speaker: Adam Smith, Penn State University
Abstract:
The goal of private data analysis is to release aggregate information about a data set while protecting the privacy of the individuals whose information the data set contains. The problem has received attention from several areas of computer science and statistics. I’ll sketch, and briefly motivate, a definition of privacy developed recently in the cryptography and theory literature, and spend the bulk of the time looking at protocols for “output perturbation” which satisfy the definition. These protocols compute correct answers to a user’s queries about the data set, but perturb the answers before releasing them by adding noise. Determining the right amount and type of noise to add, however, is delicate.
I’ll discuss a new, generic framework for output perturbation. If a user asks to learn the value of a function F, our framework calibrates the noise magnitude to the *smooth sensitivity* of F on the database X — a measure of variability of F in the neighborhood of the instance X. The new framework greatly expands the applicability of output perturbation. It also raises many interesting algorithmic questions. Namely, to apply the framework one must compute or approximate the smooth sensitivity of F on X. We show how to do this efficiently for several different functions. We also give a generic procedure based on sampling that allows one to release F(X) accurately on many databases X. This procedure is applicable even when no efficient algorithm for approximating smooth sensitivity of F is known or when F is given as a black box. We illustrate the procedure byapplying it to k-S.E.D. (k-means) clustering and learning mixtures of Gaussians.
Based on joint work with Kobbi Nissim and Sofya Raskhodnikova, to appear at STOC 2007.
Title : Analysis of the Random-Surfer Web-Graph model
Speaker : Pall Melsted
When : 4:30-5:30pm, April 12th
Where : Physical Plant Building(PPB) Room #300
Abstract:
We analyze the Random-Surfer Web-Graph Model introduced by Blum et al. In this model a new vertex picks a random vertex, performs a short random walk and connects to the end of the walk. We give the expected degree of a vertex and show that it follows a power law for early vertices thus showing a First Mover Advantage in the graph. We also show that for certain values of the parameters the first vertex will be connected to a considerable fraction of the vertices and give evidence of a phase transition for this behavior.
This is joint work with Prasad Chebolu.
SPEAKER: Elaine Shi
TIME: Wednesday 12-1pm, April 11, 2007
PLACE: NSH 1507
TITLE: Multi-Dimensional Range Query over Encrypted Data
ABSTRACT:
We design an encryption scheme called Multi-dimensional Range Query over Encrypted Data (MRQED), to address the privacy concerns related to the sharing of network audit logs and various other applications. Our scheme allows a network gateway to encrypt summaries of network flows before submitting them to an untrusted repository. When network intrusions are suspected, an authority can release a key to an auditor, allowing the auditor to decrypt flows whose attributes (e.g., source and destination addresses, port numbers, etc.) fall within specific ranges. However, the privacy of all irrelevant flows are still preserved. We formally define the security for MRQED and prove the security of our construction under the decision bilinear Diffie-Hellman and decision linear assumptions in certain bilinear groups. We study the practical performance of our construction in the context of network audit logs. Apart from network audit logs, our scheme also has interesting applications for financial audit logs, medical privacy, untrusted remote storage, etc. In particular, we show that MRQED implies a solution to its dual problem, which enables investors to trade stocks through a broker in a privacy-preserving manner.
Joint work with John Bethencourt, T-H. Hubert Chan, Dawn Song, and Adrian Perrig.
(A legend has been passed to me in verbal form, and it just occurs to me that I have read it before, except I have completely forgotten about it until this morning. The exact quantities below do not matter.)
A student Alice is finally finishing her very long thesis. Her advisor is, of course, Bob.
On page 50 of her thesis, in the middle of a very technical proof, Alice writes, “Bob, if you get to here, I owe you a case of beer.”
And on page 100, Alice similarly writes, “Bob, if you get to here, I owe you two cases of beer.”
On the day of her defense, Bob walks in to the room and proudly announce to Alice…
“You owe me a case of beer, ha ha ha, gotcha!”
P.S. In this electronic age, care must be taken if there is an electronic copy available. After all, if Bob has the PDF, imagine what terms he may search for… 
Title: Proof Producing Algorithms
Speaker: Sean McLaughlin, CSD
Location: NSH 1507
Time: 12-1 pm
Date: Friday, April 06, 2007
Abstract:
The design and implementation of algorithms is a fundamental task in computer science. But the process is error-prone, and historically many important programs and algorithms have contained serious errors.# While
often we can live with the bugs lurking in our algorithms and code, in some domains it is essential that the programs we write be error-free.
In this talk I will survey strategies for designing algorithms that, in addition to computing a result, produce a proof of the correctness of that result. I will then focus on the application of these strategies to a number of areas, such as automated reasoning, programming language semantics, and formalized mathematics.
Friday, April 6th, 2007
3:30pm
Wean Hall 7220
Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1
Piotr Indyk (MIT)
The area of geometric functional analysis is concerned with studying properties of geometric (normed) spaces. A typical question in the area is: given two geometric spaces X, Y, is there an embedding F of X into Y so that F distorts the distances between any pair of points by only a constant factor? One of the classic results of this type is a constant-distortion embedding of an n-dimensional space equipped with L2 norm, into an O(n)-dimensional space equipped with L1 norm (also known as Dvoretzky’s theorem for L1). Embeddings have many interesting applications, in computer science and beyond.
A ubiquitous tool for constructing such embeddings is the probabilistic method: the mapping is chosen at random, and one shows that it “works” with high probability. Unfortunately, this approach does not yield a concrete (or explicit) construction of an embedding. A folklore open problem has been to obtain explicit constructions with parameters that (almost) match the non-constructive bounds. However, the progress on this front has been somewhat limited. For example, the best known explicit construction of an embedding of an n-dimensional L2 space into an m-dimensional L1 space guarantees only m=O(n^2).
In this talk I will show an explicit construction of an embedding of an n-dimensional L2 space into L1 space of dimension n^{1+o(1)}. The construction utilizes two tools: discrete uncertainty principles (introduced by Donoho and Stark in the area of digital signal processing) and randomness extractors. If time allows, I will also show some related constructions, with application to signal sketching and compressed sensing.
Title : Integer Sets Having the Maximum Number of Distinct Differences
Speaker : Oleg Pikhurko
When : 4:30-5:30pm, April 5th
Where : Physical Plant Building(PPB) Room #300
Abstract:
We consider the function $D(k,n)$ which is the maximum of $ |A-A|=|\{a-b \mid a,b\in A\}| $ over all $k$-subsets $A$ of $[n]=\{0,\ldots,n\}$. In other words, we want to maximize the number of distinct differences that a $k$-subset of $[n]$ can have. The range of interest is when $k$ is of order $\sqrt n$. A few well-known problems from additive number theory can be restated in terms of the function $D(k,n)$.
We show that for any fixed real $c\ge 0$ and any function $k(n)=(c+o(1))\sqrt n$ the limit $ d(c)=\lim_{n\to\infty} \frac{D(k(n),n)}n $ exists. We present upper and lower bounds on $d(c)$, outlining (mostly combinatorial) proofs. A few other versions of the problem, such as maximizing the number of distinct sums, will be considered as well.
Some of the presented results are joint work with B\’ela Bollob\’as and with Tomasz Schoen.
