Title: Hamilton cycles and perfect matchings in hypergraphs
Speaker: Andrzej Rucinski (Adam Mickiewicz University, Poznan)
When: September 27, 16:30-17:30pm
Where: Wean Hall 5302
Abstract:
A classic theorem of Dirac states that a sufficient condition for an n-vertex graph to be hamiltonian is that the minimum degree is at least n/2. In my talk I will present recent results on Dirac type problems for k-uniform hypergraphs, obtained jointly with V.Rodl and E.Szemeredi.
Who: Jeremiah Blocki
Where: NSH 1507
When: Noon 9/26
Title: A Complete Classification of the Computational Complexity of K-Anonymity
K-Anonymization is a technique used to publicly release a database, while ensuring both the privacy and the accuracy of the released information. One general model of the problem allows for cells in the database to be suppressed until each row is identical to at least k-1 other rows. In order to maximize the utility of the database we attempt to minimize the number of suppressed cells necessary to guarantee K-Anonymity. We show that optimal binary 3-Anonymity, where all of the attribute values are 0 or 1, is NP-Hard. This improves upon the result of Aggarwal et al., who showed that ternary 3-Anonymity is NP-Hard. We believe our proof that optimal 3-Anonymity is NP-Hard is simpler than the independent proof given by Bonizzoni et al (July, 2007). On the positive side we show that there is a polynomial time algorithm for optimal 2-Anonymity. This completes the classification of the computational complexity of k-anonymity.
From this New York Times article:
Algorithms, as closely guarded as state secrets, buy and sell stocks and mortgage-backed securities, sometimes with a dispassionate zeal that crashes markets. Algorithms promise to find the news that fits you, and even your perfect mate.
Perfect!
Title: PageRank and the Random Surfer Model
Speaker: Páll Melsted
When: September 20, 16:30-17:30pm
Where: Wean Hall 5302
Abstract:
In recent years there has been considerable interest in analyzing random graph models for the Web. We consider two such models - the Random Surfer model introduced by Blum et al. and the PageRank-based selection model proposed by Pandurangan et al. It has been observed that search engines influence the growth of the Web. The PageRank-based selection model tries to capture the effect that these search engines have on the growth of the Web by adding new links according to Pagerank. The PageRank algorithm is used in the Google search engine for ranking search results.
We show the equivalence of the two random graph models and carry out the analysis in the Random Surfer model, since it is easier to work with. We analyze the expected in-degree of vertices and show that it follows a powerlaw. We also analyze the expected PageRank of vertices and show that it also follows the same powerlaw as the expected degree.
We show that in both models the expected degree and the PageRank of the first vertex, the root of the graph, follow the same powerlaw. However the power undergoes a phase-transition as we vary the parameter of the model. This peculiar behavior of the root has not been observed in previous analysis and simulations of the two models.
This is joint work with Prasad Chebolu.
Who: Dan Golovin
Where: NSH 1507
When: 9/19/2007, Noon
Title: Stochastic Packing-Market Planning
Abstract:
In traditional mechanism design problems, the mechanism receives its inputs from various strategic players, and must select an outcome and payment scheme with the goal of providing the proper incentives to the selfish players to achieve an optimal outcome, for various objective functions. A well-studied special case of this problem is to design mechanisms for combinatorial auctions to maximize social welfare. We consider a variant of this problem in which there is probabilistic demand and participants associate some cost with participating (e.g., by waiting until their demand is sampled and then attending the auction, they incur some opportunity cost). We call this the Stochastic Packing-Market Planning problem (SPMP), which is a stochastic generalization of the Maximum k-Set Packing problem. We provide an approximation algorithm andmechanism for SPMP, and also give a linear programming based approximation for the expected weight of a maximum set packing in a random subhypergraph of a fixed hypergraph G, using techniques which may be of independent interest.
See this great post in Michael Trick’s OR Blog on a recent article in the Economist magazine titled “Business by numbers”.
Among other things, this is how the Economist article begins:
Algorithms sound scary, of interest only to dome-headed mathematicians.
Well, I have no idea what “dome-headed” means, but Google tells me that dome-headed creatures can be scary. Now, domed-head mathematicians… hmm, maybe it has to do with banging the head to the wall? 
Francois Margot, Associate Professor of Operations Research
Carnegie Mellon University
Date: Friday, September 28, 2007
Time: 1:30 to 3:00 pm
Location: Room 388 Posner Hall
Title: Testing Cut Generators for ILP
Abstract:
This talk describes recent work on the testing of cut generators for integer linear programming. The goal of this work is to build experiments that can be used for comparing slight variants of a cut generator. Cut generators should be compared along several dimensions, for example the precision (what is the likelihood of a feasible solution to be cut?), the strength (are the cuts obtained stronger or weaker?), the speed of the generator, and the speed of the reoptimization after cuts are added. While generation and reoptimization speeds are relatively easy to test, both precision and strength are more difficult to evaluate. Results for testing several variants of Gomory cut generators and several variants of Reduce-and-Split cut generators are presented.
The approach followed is in the spirit of the empirical analysis of algorithms advocated by Hooker and McGeoch, among others. The object of empirical analysis of algorithms is to use experiments to suggest hypotheses about the behavior of algorithms. Hypotheses are then tested using controlled experiments, well-grounded in statistical analysis.
Title: Quadruple systems with independent neighborhoods
Speaker: Dhruv Mubayi (CMU)
When: September 13, 16:30-17:30pm
Where: WEH 5302 (all future talks will be held here)
Abstract:
What is the maximum number of edges in a k-uniform hypergraph on n vertices whose neighborhoods are all independent sets? When $k=2$ the answer is $n^2/4$ proved by Mantel in 1907. This was the first result in extremal graph theory. The next case $k=3$ was solved by Furedi-Pikhurko-Simonovits in 2003. I will present a proof for the case $k=4$. This is joint work with Zoltan Furedi and Oleg Pikhurko.
Please see Developing for Developers by Derrick Coetzee.
Friday September 14th
WEH 7220, 3:30pm
TITLE: Expander codes and pseudorandom subspaces of R^n
James R. Lee
University of Washington
ABSTRACT:
Classical results in high-dimensional geometry state that on a random subspace of R^n of proportional dimension, the L_1 and L_2 norms are equivalent up to universal factors. Indeed, this is a particular example of the use of the probabilistic method, a technique which is now ubiquitous in asymptotic convex geometry.
Similar randomized geometric constructions arise in areas like high-dimensional nearest-neighbor search and compressed sensing, but it seems that such objects are very hard to come by explicitly.
I will show how constructions inspired by expander codes can be used to explicitly produce subspaces that are nearly as good as random for some of the problems discussed above. Guest appearances by: Ramanujan graphs, sum-product theorems in finite fields, and mutually unbiased bases.
[This is based on joint work with Venkat Guruswami and Sasha Razborov]
Convex Optimization
Stephen Boyd
Standford
4pm, Sept 13, 2007
Scaife 125
In this talk I will give an overview of general convex optimization, which can be thought of as an extension of linear programming, and some recently developed subfamilies such as second-order cone, semidefinite, and geometric programming. Like linear programming, we have a fairly complete duality theory, and very effective numerical methods for these problem classes; in addition, recently developed software tools considerably reduce the effort of specifying and solving convex optimization problems. There is a steadily expanding list of new applications of convex optimization, in areas such as circuit design, signal processing, statistics, machine learning, communications, control, finance, and other fields. Convex optimization is also emerging as an important tool for hard, non-convex problems, where it can be used to generate lower bounds on the optimal value, and as a heuristic method for generating suboptimal points.
* Joint work with Lieven Vandenberghe and Michael Grant
Title: Multi-Dimensional Range Query over Encrypted Data
Speaker: Elaine Shi, CSD
Location: NSH 1507
Time: 12-1 pm
Date: Friday, September 07, 2007
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.
Title: Two applications of Szemeredi’s Regularity Lemma
Speaker: Oleg Pikhurko
When: September 6, 15:30-16:20pm
Where: Wean Hall, Room 5310
Abstract:
I will present two (short and unrelated) applications of Szemeredi’s Regularity Lemma.
In one (joint work with Benny Sudakov) we prove, for all large $n$, the conjecture of Lazebnik (1989) that among all graphs with n vertices and $m < n^2/4$ edges the maximum number of $3$-colorings is achieved by a semi-complete biparite graph.
Another application proves the conjecture of Aigner, Triesch, and Tuza (1995) that one can find an unknown acyclic orientation of any given graph of order $n$ by quering at most $(1/4+o(1))n^2$ edges.
September 11, 2007
Benoît Hudson
10:00 AM, 3305 Newell-Simon Hall
Thesis Oral
Title: Dynamic Mesh Refinement
Abstract:
Mesh refinement is the problem to produce a triangulation (typically Delaunay) of an input set of points augmented by Steiner points, such that every triangle has good quality (no small angles). The requirement arises from the applications: in scientific computing and in graphics, meshes are often used to discretely represent the value of a function over space. In addition to the quality requirement, the user often has input segments or polygons (generally, a piecewise linear complex) they would like see retained in the mesh; the mesh must respect these constraints. Finally, the mesh should be size-conforming: the size of mesh elements should be related to a particular sizing function based on the distance between input features — in particular, elements should not be too small.
The static meshing problem is increasingly well-understood: one can download software with provable guarantees that on reasonable input, the meshes will have good quality, will respect the input, and will be size-conforming; more recently, these algorithms have started to come with optimal runtimes of O(n log(L/s) + m). As a first result, I present experimental results of the first time-optimal code.
Increasingly, static meshing is insufficient: users want to modify the mesh over time. Throwing away the old mesh and remeshing from scratch is a common approach, but that suffers from slow runtime, and from reinterpolation error because the old and new meshes may be almost unrelated. Mesh stability analyses the correspondence between meshes for two inputs. The main theoretical result of this thesis is an algorithm that has provable bounds on stability: upon inserting or removing a feature that in the final mesh is represented using k points, the mesh only modifies O(k log L/s) mesh simplices.
Finally, stability can be exploited to produce an efficient dynamic algorithm. Under the self-adjusting computation framework, with a small amount of additional effort, I show that the above algorithm can be dynamized to run in O(k log L/s) time per update, using O(n log L/s + m) space.
Thesis Committee:
Gary Miller, Chair
Anupam Gupta
Daniel Sleator
Umut A. Acar, Toyota Technological Institute at Chicago
Jonathan R. Shewchuk, University of California, Berkeley
Friday September 7th, 2007
WEH 7220
TITLE: Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
Kenneth L. Clarkson
IBM Research Labs, Almaden
ABSTRACT:
The problem of maximizing a concave function f(x) in a simplex S can be solved approximately by a simple greedy algorithm, that in k steps can find a point x_k such that f(x_k) ≥ f(x_*) - O(1/k), where f(x_*) is the maximum value of f in S. This algorithm and analysis were known before, and related to problems of statistics and machine learning, such as boosting, training support vector machines, regression, and density mixture estimation. In other work, coming from computational geometry, the existence of / ε-coresets/ was shown for the minimum enclosing ball problem, by means of a simple greedy algorithm. Similar greedy algorithms, that are special cases of the Frank-Wolfe algorithm, were described for other enclosure problems. I’ll tie these results together, review some stronger convergence results, and generalize or strengthen some coreset bounds.
September 7, 2007
Tsz Hong Hubert Chan
10:30 AM, 4623 Wean Hall
Thesis Oral
Title: Approximation Algorithms for Bounded Dimensional Metric Spaces
Abstract:
The study of finite metrics is an important area of research, because of its wide applications to many different problems. The input of many problems (for instance clustering, near-neighbor query and network routing) naturally involves sets of points on which a distance function has been defined. Hence, one would be motivated to store and process metrics in an efficient manner. The central idea in metric embedding is to represent a metric space by a “simpler'’ metric space so that the properties of the original metric space is well preserved.
More formally, given a target class C of metrics, an embedding of a finite metric space M = (V,d) into the class C is a new metric space M’ = (V,d’) such that M’ is in C. Most of the work on embeddings has used distortion as the fundamental measure of quality; the distortion of an embedding is the worst multiplicative factor by which distances are increased by the embedding. In the theoretical community, the popularity of the notion of distortion has been driven by its applicability to approximation algorithms: if the embedding f: (V,d) -> (V,d’) has a distortion of D, then the cost of solutions to some optimization problems on (V,d) and on (V,d’) can only differ by some function of D; this idea has led to numerous approximation algorithms. Seminal results include the O(log n) distortion embeddings of arbitrary metrics into Euclidean spaces with O(log n) dimensions, and the fact that any metric admits an O(log n) stretch spanner with O(n) edges.
The theoretical results mentioned above are optimal. However, it is pessimistic in the sense that such guarantees hold for any arbitrary metric. It is conceivable that better results can be obtained if the input metrics are “simple'’. The main theme of this work is to investigate notions of complexity for an abstract metric space and theoretical guarantees for problems in terms of the complexity of the input metric.
One popular notion for measuring the complexity of a metric is the doubling dimension, which restricts the local growth rate of a metric. We show that the results on spanners and embeddings can be improved if the given metrics have bounded doubling dimension. For instance, we give construction for constant stretch spanners with linear number of edges. Moreover, such metrics can be embedded into Euclidean space with O(log log n) dimensions and o(log n) distortion.
We also study a new notion of dimension that captures the global growth rate of a metric. Such a notion strictly generalizes doubling dimension in the sense that it places weaker restrictions on a given metric than those posed by doubling dimension. However, we can still obtain good guarantees for problems in which the objective depends on the global nature of the metric, an example of which is the Traveling Salesperson Problem (TSP). In particular, we give a sub-exponential time to solve TSP with approximation ratio arbitrarily close to 1 for such metrics.
Thesis Committee:
Anupam Gupta, Chair
Avrim Blum
R. Ravi
Kenneth L. Clarkson, IBM Research, Almaden