- talks - lists.cs.princeton.edu

W Mulzer preFPO
by Melissa Lawson 05 Oct '09

05 Oct '09

Wolfgang Mulzer will present his preFPO on Thursday October 8 at 10:30 AM in Room 402. The members of his committee are: Bernard Chazelle, advisor; David Dobkin and Bob Tarjan, readers; Sanjeev Arora and Boaz Barak, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------------------- Low-Entropy Computational Geometry The worst-case model for algorithm design does not always reflect the real world: inputs may have additional structure to be exploited, and sometimes data can be imprecise or become available only gradually. To better understand these situations, we examine several scenarios where additional information can affect the design and analysis of geometric algorithms. First, we consider hereditary convex hulls: given a three-dimensional convex polytope and a two-coloring of its vertices, we can find the individual monochromatic polytopes in linear expected time. This can be generalized in many ways, eg, to more than two colors, and to the offline-problem where we wish to preprocess a polytope so that any large-enough subpolytope can be found quickly. Next, we assume that the point coordinates have a bounded number of bits, and that we can do standard bit manipulations in constant time. Then Delaunay triangulations can be found in expected time O(n(log log n)^(1/2)). Our result is based on a new connection between quadtrees and Delaunay triangulations, which also lets us generalize a recent result by Loeffler and Snoeyink about Delaunay triangulations for imprecise points. Finally, we consider randomized incremental constructions when the input permutation is generated by a bounded-degree Markov chain, and show that the resulting running time is almost optimal for chains with a constant eigenvalue gap.

1 0

Wednesday, October 7th-Colloquium--
by Michele J. Brown 01 Oct '09

01 Oct '09

Title: On the Internet Someone Knows You Are a Dog Balachander Krishnamurthy, AT&T Labs - Research We have been examining the leakage of privacy on the Internet: how information related to individual users is aggregated as they browse seemingly unrelated Web sites. Thousands of Web sites across numerous categories, countries, and languages are studied to generate a "privacy footprint". I report on a longitudal study consisting of multiple snapshots of examination of such diffusion over five years. I'll talk about the technical ways by which third-party aggregators acquire data, the depth of user-related information acquired, the techniques for protecting privacy diffusion and limitations of such techniques. Such increasing aggregation of user-related data is carried out by a steadily decreasing number of entities: a handful are able to track users' movement across almost all of the popular web sites. Virtually all the protection techniques have significant limitations highlighting the seriousness of the problem and the need for alternate solutions. I will also talk about a recent discovery of large-scale leakage of personally identifiable information (PII) via Online Social Networks (OSN). Third-parties can link PII with user actions both within OSN sites and elsewhere on non-OSN sites. 4:30 PM Computer Science Small Auditorium (Room 105) Host: Jennifer Rexford

1 0

Wednesday, October 7th-Colloquium
by Michele J. Brown 01 Oct '09

01 Oct '09

Princeton University | Princeton Engineering >Academics Course Schedule Course Catalog Graduate Program Undergraduate Programs Interdisciplinary Programs >Research Research Areas Research Projects Public Lectures and Colloquia Technical Reports >People Faculty Research Scholars Research and Technical Staff Administrative Staff Graduate Students Undergraduate Students Alumni/ae >Connect Collaborations Industrial Affiliates Libraries >About Contact Us News and Events Department Information Visit Us Home :: Department Events -------------------------------------------------------------------------------- Department Events -------------------------------------------------------------------------------- [ View Current Schedule ] [ Browse the archives ] [ To submit an event for consideration, or sign up a speaker, please see this page. ] -------------------------------------------------------------------------------- Title: On the Internet Someone Knows You Are a Dog Balachander Krishnamurthy, AT&T Labs - Research We have been examining the leakage of privacy on the Internet: how information related to individual users is aggregated as they browse seemingly unrelated Web sites. Thousands of Web sites across numerous categories, countries, and languages are studied to generate a "privacy footprint". I report on a longitudal study consisting of multiple snapshots of examination of such diffusion over five years. I'll talk about the technical ways by which third-party aggregators acquire data, the depth of user-related information acquired, the techniques for protecting privacy diffusion and limitations of such techniques. Such increasing aggregation of user-related data is carried out by a steadily decreasing number of entities: a handful are able to track users' movement across almost all of the popular web sites. Virtually all the protection techniques have significant limitations highlighting the seriousness of the problem and the need for alternate solutions. I will also talk about a recent discovery of large-scale leakage of personally identifiable information (PII) via Online Social Networks (OSN). Third-parties can link PII with user actions both within OSN sites and elsewhere on non-OSN sites. 4:30 PM Computer Science Small Auditorium (Room 105) Host: Jennifer Rexford

1 0

[Fwd: Theoretical CS talk at Princeton Civitas Finance seminar Wed Sept 30]
by Sanjeev Arora 28 Sep '09

28 Sep '09

1 0

3pm talk today on network measurement by Morley Mao in room CS 402
by Jennifer Rexford 25 Sep '09

25 Sep '09

Speaker: Professor Z. Morley Mao, U. Michigan Title: Intelligent Network Measurement for Diagnosis and Attack Defenses Date/time: 3:00-4:00pm on Friday September 25 Location: CS 402 Please let me know if you would like to meet with Professor Mao during her visit... Abstract: Measurement is a powerful and indispensable technique for discovering the state of the network and for assisting operational management of networked systems to ensure good performance and security properties. Designing the effective measurement technique depending on the problem context is especially challenging for Internet-based systems due to issues such as a lack of access, overhead concerns, and measurement noise. In this talk, I present our experience in designing and deploying measurement systems for several important applications, e.g., diagnosing routing performance disruptions and prefix hijacking attacks from end systems, uncovering spammer behavior through campaign-based analysis, and detecting network neutrality violation in backbone ISPs. I will summarize lessons learned and discuss our future work on applying intelligent measurement to relatively new application domains such as data cellular networks and data center systems. Z. Morley Mao is an assistant professor of Computer Science and Engineering at the University of Michigan. Morley received most of her degrees (Ph.D., M.S., and B.S.) from the University of California at Berkeley. She is a recipient of the NSF CAREER award in 2007, an IBM Faculty Award in 2008, Sloan Research Fellowship in 2009, and was recently named the Morris Wellman Faculty Development Professor at Michigan. Her research interests encompass network measurements, routing protocols, distributed systems, and network security.

1 0

time and room change for Friday talk on network measurement (now 3pm in CS 402)
by Jennifer Rexford 21 Sep '09

21 Sep '09

*** NOTE: ROOM AND TIME HAVE CHANGED *** Speaker: Professor Z. Morley Mao, U. Michigan Title: Intelligent Network Measurement for Diagnosis and Attack Defenses Date/time: 3:00-4:00pm on Friday September 25 Location: CS 402 Please let me know if you would like to meet with Professor Mao during her visit... Abstract: Measurement is a powerful and indispensable technique for discovering the state of the network and for assisting operational management of networked systems to ensure good performance and security properties. Designing the effective measurement technique depending on the problem context is especially challenging for Internet-based systems due to issues such as a lack of access, overhead concerns, and measurement noise. In this talk, I present our experience in designing and deploying measurement systems for several important applications, e.g., diagnosing routing performance disruptions and prefix hijacking attacks from end systems, uncovering spammer behavior through campaign-based analysis, and detecting network neutrality violation in backbone ISPs. I will summarize lessons learned and discuss our future work on applying intelligent measurement to relatively new application domains such as data cellular networks and data center systems. Z. Morley Mao is an assistant professor of Computer Science and Engineering at the University of Michigan. Morley received most of her degrees (Ph.D., M.S., and B.S.) from the University of California at Berkeley. She is a recipient of the NSF CAREER award in 2007, an IBM Faculty Award in 2008, Sloan Research Fellowship in 2009, and was recently named the Morris Wellman Faculty Development Professor at Michigan. Her research interests encompass network measurements, routing protocols, distributed systems, and network security.

1 0

4:30pm Wed Oct 7 colloquium on Internet privacy
by Jennifer Rexford 20 Sep '09

20 Sep '09

Speaker: Balachander Krishnamurthy, AT&T Labs--Research Title: On the Internet Someone Knows You Are a Dog Date/time: 4:30pm Wed Oct 7 (tea at 4pm in tea room) Location: CS 105 (small auditorium) Abstract: We have been examining the leakage of privacy on the Internet: how information related to individual users is aggregated as they browse seemingly unrelated Web sites. Thousands of Web sites across numerous categories, countries, and languages are studied to generate a "privacy footprint". I report on a longitudal study consisting of multiple snapshots of examination of such diffusion over five years. I'll talk about the technical ways by which third-party aggregators acquire data, the depth of user-related information acquired, the techniques for protecting privacy diffusion and limitations of such techniques. Such increasing aggregation of user-related data is carried out by a steadily decreasing number of entities: a handful are able to track users' movement across almost all of the popular web sites. Virtually all the protection techniques have significant limitations highlighting the seriousness of the problem and the need for alternate solutions. I will also talk about a recent discovery of large-scale leakage of personally identifiable information (PII) via Online Social Networks (OSN). Third-parties can link PII with user actions both within OSN sites and elsewhere on non-OSN sites. http://www.cs.princeton.edu/events/event/219

1 0

Colloquium-Tuesday, September 22
by Michele J. Brown 18 Sep '09

18 Sep '09

*Distinguished Speaker Ivan Sutherland*, Portland State University * *Small Auditorium (105) Computer Science Building 4:30 pm *"Fleet, Infinity & Marina"* This talk describes a radically different architecture for computing called Fleet. Fleet accepts the limitations to computing imposed by physics: moving data costs more energy, more delay, and more chip area than the arithmetic and logical operations ordinarily called "computing." Fleet puts the programmer firmly in charge of the most costly resource: communication. Fleet treats arithmetic and logical operations as side effects of where the programmer sends data. Fleet achieves high performance through fine grain concurrency. Everything Fleet does is concurrent at the lowest level; programmers who wish sequential behavior must program it explicitly. Fleet presents a stark contrast to today's multi-core machines in which programmers seek concurrency in an inherently sequential environment. The Fleet architecture uses a uniform switch fabric to simplify chip design. A few thousand identical copies of a configurable interface will connect a thousand or so repetitions of basic arithmetic, logical, input-output, and storage units to the switch fabric. The uniform switch fabric and the identical configurable interfaces will simplify many of the hard parts of designing the computing elements themselves. Both software and FPGA simulators of a Fleet system are available at UC Berkeley. Berkeley students have written a variety of Fleet programs; their work helped to define what the configurable interface between computing and communication must do. A simple compiler configures both source and destination to provide flow-controlled communication. We expect work on a higher-level language for Fleet to appear soon as a Berkeley PhD dissertation. Last year we built a 90 nanometer TSMC test chip, called Infinity, at Sun Microsystems. Infinity demonstrated the switch fabric running at about 4 GHz. We now have a new test chip, called Marina, also in 90-nanometer TSMC sponsored by Sun. Marina shows correct operation of the configurable switch fabric interface. Together Infinity and Marina give us confidence to build a complete Fleet. We seek participation from sponsors, computer scientists, and hardware designers. *BIO:* Ivan Sutherland is a Visiting Scientist at Portland State University where he and Marly Roncken have recently established the "Asynchronous Research Center" (ARC). The ARC occupies both physical and intellectual space half way between the Computer Science (CS) and Electrical and Computer Engineering (ECE) departments at the university. The ARC seeks to free designers from the tyranny of the clock by developing better tools and teaching methods for design of self-timed systems. Prior to moving to Portland, Ivan spent 25 years as a Fellow at Sun Microsystems. A 1959 graduate of Carnegie Tech, Ivan got his PhD at MIT in 1963 and has taught at Harvard, The University of Utah, and Caltech. Ivan is a member of the National Academy of Engineering and the National Academy of Sciences.

1 0

1:30-2:30pm Fri Sep 25 talk on Internet measurement in CS 105
by Jennifer Rexford 14 Sep '09

14 Sep '09

Please let me know if you would like to meet with Professor Mao during her visit... Speaker: Professor Z. Morley Mao, U. Michigan Title: Intelligent Network Measurement for Diagnosis and Attack Defenses Date/time: 1:30-2:30pm on Friday September 25 Location: CS 105 (small auditorium) Abstract: Measurement is a powerful and indispensable technique for discovering the state of the network and for assisting operational management of networked systems to ensure good performance and security properties. Designing the effective measurement technique depending on the problem context is especially challenging for Internet-based systems due to issues such as a lack of access, overhead concerns, and measurement noise. In this talk, I present our experience in designing and deploying measurement systems for several important applications, e.g., diagnosing routing performance disruptions and prefix hijacking attacks from end systems, uncovering spammer behavior through campaign-based analysis, and detecting network neutrality violation in backbone ISPs. I will summarize lessons learned and discuss our future work on applying intelligent measurement to relatively new application domains such as data cellular networks and data center systems. Z. Morley Mao is an assistant professor of Computer Science and Engineering at the University of Michigan. Morley received most of her degrees (Ph.D., M.S., and B.S.) from the University of California at Berkeley. She is a recipient of the NSF CAREER award in 2007, an IBM Faculty Award in 2008, Sloan Research Fellowship in 2009, and was recently named the Morris Wellman Faculty Development Professor at Michigan. Her research interests encompass network measurements, routing protocols, distributed systems, and network security.

1 0

D Xiao FPO
by Melissa Lawson 18 Aug '09

18 Aug '09

David Xiao will present his FPO on Monday August 24 at 11AM in Room 402. The members of his committee are: Boaz Barak, advisor; Avi Wigderson, Russell Impagliazzo (IAS), Sanjeev Arora, and Rob Schapire. A copy of his thesis, "New Perspectives on the Complexity of Computational Learning and Other Problems in Theoretical Computer Science", is on display in room 310. Everyone is invited to attend his talk.

1 0