January 2007 - talks - lists.cs.princeton.edu

D Dantas preFPO
by Melissa M Lawson 30 Jan '07

30 Jan '07

Daniel Dantas will present his preFPO at 10AM on Tuesday, February 6 in Room 402. The members of his committee are David Walker, advisor; Andrew Appel, Stephanie Weirich, readers; Ed Felten, and David August, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------------ My thesis extends functional programming languages with aspect-oriented features, primarily to explore aspect-oriented enforcement of security policies. First, my thesis examines an aspect-oriented implementation of the Java security mechanism, which requires the security advice to be triggered by functions with diverse argument and return types. My thesis presents a new language, AspectML, that allows a programmer to define type-safe polymorphic advice using pointcuts constructed from a collection of polymorphic join points. I then compare my AspectML implementation of the Java security mechanism against the existing Java implementation. Second, in ordinary aspect-oriented programming, security and other advice added after-the-fact to an existing codebase can disrupt important data invariants and prevent local reasoning. Instead, my thesis shows that many common aspects, including security advice, can be implemented as harmless advice. Harmless advice uses a novel type and effect system related to information-flow type systems to ensure that harmless advice cannot modify the behavior of mainline code. To demonstrate the usefulness of harmless advice for security, I implemented many of the security examples used by the Naccio execution monitoring system by Evans and Twyman as harmless advice. Finally, my thesis expands the harmless advice specification to allow programmers to create interference policies for system libraries to define how those libraries can be used by aspects. These policies use a selection of compile-time type checking and run-time monitoring to enforce the desired definition of harmlessness on the aspect-oriented program. My thesis formalizes an idealized file IO system and proves that an interference policy specified by our policy language can continue to enforce our original view of harmlessness for advice that uses file IO.

1 0

S Kale preFPO
by Melissa M Lawson 23 Jan '07

23 Jan '07

Satyen Kale will present his preFPO on Tuesday January 30 at 1PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Rob Schapire, readers; Bernard Chazelle and Boaz Barak, nonreaders. Everyone is invited to attend his talk. His abstract follows below. _____ Title: Efficient Algorithms using the Multiplicative Weights Update method Algorithms based on convex optimization, especially linear and semidefinite programming, are ubiquitous in Computer Science. While there are polynomial time algorithms known to solve such problems, quite often the running time of these algorithms is very high. Designing simpler and more efficient algorithms is important for practical impact. In my talk, I will describe applications of the Multiplicative Weights Update method in the design of efficient algorithms for various optimization problems. This method, which was repeatedly discovered in quite diverse fields, is an algorithmic technique which maintains a distribution on a certain set of interest, and updates it iteratively by multiplying the probability mass of elements by suitably chosen factors based on the distribution. The central result of my thesis is a generalization of the method to the setting of symmetric matrices rather than real numbers. I will describe the following applications of the resulting Matrix Multiplicative Weights algorithm: 1. The first truly general, combinatorial, primal-dual method for designing efficient algorithms for semidefinite programming. Using these techniques, we obtain significantly faster algorithms for obtaining O(sqrt{log n}) approximations to various graph partitioning problems, such as Sparsest Cut, Balanced Separator in both directed and undirected weighted graphs, and the Min UnCut problem. 2. An O*(n^3) time derandomization of the Alon-Roichman construction of expanders using Cayley graphs. 3. An O*(n^3) time deterministic O(log n) approximation algorithm for the quantum hypergraph covering problem. 4. A simpler proof of a result of Aaronson that the gamma-fat-shattering dimension of quantum states on n qubits is O(n/gamma^2). I will also briefly mention the following algorithmic applications of the classical Multiplicative Weights Update method: 1. Fast algorithms for approximately solving several families of semidefinite programs, which beat interior point methods. 2. O(sqrt{log n}) approximation to the Sparsest Cut in graphs in O*(n^2) time.

1 0

A Karagiozova preFPO
by Melissa M Lawson 18 Jan '07

18 Jan '07

Adriana Karagiozova will present her preFPO on Thursday January 25 at 3PM in Room 402. The members of her committee are Moses Charikar, advisor; Bernard Chazelle, Bob Tarjan, readers; Boaz Barak, Bob Sedgewick, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. -------------------------------------- Aspects of Network Design and Metric Space Embeddings In this talk I will present results on several problems in network design and metric space embeddings: 1) Multicommodity buy-at-bulk network design We seek to design a cheap network that satisfies the demands between the terminals of multiple source-sink pairs, where the edge costs experience economies of scale. We give the first non-trivial approximation algorithm for the general case of the problem. 2) Terminal Backup Given a graph with terminals, non-terminals and edge costs we want to find a forest that connects each terminal to at least one other terminal. We give a simple polynomial time algorithm that finds the cheapest such forest. In the process we show that a version of 3D matching, useful for tasks that involve splitting into groups of at least two members, is solvable in polynomial time. 3) Metric Ramsey phenomena A Ramsey theorem on metric spaces asks if given an arbitrary metric space, what is the size of the largest subspace that embeds into $\ell_p$ with distortion at most some target $\alpha$. Previous work shows a phase transition at $\alpha = 2$ for $p > 2$. We show that such a phase transition occurs at $\alpha = 2$ for all $p \geq 1$. 4) Embedding series-parallel graphs into $\ell_1$ We give an embedding of any n-point series-parallel metrics into $\ell_1$ with distortion O(\sqrt{\log n / \log s}), where every coordinate of the embedding is s-Lipschitz. Using this embedding we obtain various other results, among which is matching the dimension-reduction lower bound of Brinkman and Charikar.

1 0

K Park FPO
by Melissa M Lawson 17 Jan '07

17 Jan '07

KyoungSoo Park will present his final public oral on Wednesday January 24 at 2PM in Room 402. The members of his committee are: Vivek Pai, advisor: Larry Peterson and Jennifer Rexford, readers; Brian Kernighan and Andrea LaPaugh, nonreaders. A copy of his thesis, "Towards Highly Reliable and Scalable Distributed Systems" is on display in Room 310. Everyone is invited to attend his talk.

1 0

PLOrk Winter Concert : Jan. 18th
by Ge Wang 09 Jan '07

09 Jan '07

----- http://plork.cs.princeton.edu/upcoming.html ----- The Princeton Laptop Orchestra (PLOrk) presents PLOrk Winter Concert 8pm, Thursday January 18th, 2007 Taplin Auditorium, Princeton University featuring works and performances by: Perry R. Cook | MR Daniel | Scott Elmegreen | Rebecca Fiebrink | John Fontein | Michael Hammond | Anne Hege | Matt Hoffman | Laurie Hollander | Andrea Mazzariello | Ananya Misra | Spencer Salazar | Scott Smallwood | Alan Tormey | Ge Wang | Samson Young directed by Perry Cook and Ge Wang The Princeton Laptop Orchestra (PLOrk) presents an evening of new music, composed and performed by members of the Fall 2006 PLOrk ensemble and seminar. The event is free and open to the public. http://plork.cs.princeton.edu/ ----

1 0

B Guo preFPO
by Melissa M Lawson 02 Jan '07

02 Jan '07

Bolei Guo will present her preFPO on Tuesday January 9 at 1PM in Room 402. The members of her committee are; David August, advisor; Andrew Appel and Michael Hind (IBM TJ Watson), readers; Brian Kernighan and David Walker, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ------------------------------------------- "Low-Level Shape Analysis with Inductive Recursion Synthesis" Aggressive memory disambiguation for low-level code can eliminate the problem of conservatively propagating high-level memory analysis results. It critically affects the effective-ness of back-end code optimizations. In particular, automatic loop parallelization relies on a type of memory analysis called shape analysis, which determines the shapes of data structures built by the program. We designed a separation-logic-based shape analysis for low-level code. Separation logic with recursively defined predicates allows for concise yet precise description of the shapes of data structures. However, inferring such predicates is a difficult task. Current uses of separation logic involve pre-defined built-in predicates and logic rules specificially written for these predicates, limiting the class of analyzable programs. We developed an inductive learning technique to automatically infer arbitrary recursive shape predicates. In addition, to facilitate the interaction between local reasoning and the global invariants given by the recursive predicates, a notion of "truncation points" is introduced in a predicate, which gives rise to generic algorithms for unfolding and folding arbitrary data structures. This shape analysis uses the alias information provided by a fast low-level pointer analysis to identify recursive data structures and to prune away code that does not affect the result of shape analysis. It has been implemented in the Velocity compiler and evaluated on benchmarks from the SPEC2000 and Olden benchmark suites.

1 0