- talks - lists.cs.princeton.edu

talk today 2/27
by Ginny Hogan 27 Feb '08

27 Feb '08

Christiane Fellbaum, Princeton, will present her talk "A lexical resource for Natural Language Processing" at 4:15pm today - Computer Science Room 105 -

1 0

E Chlamtac preFPO
by Melissa M Lawson 26 Feb '08

26 Feb '08

Eden Chlamtac will present his preFPO on Tuesday, March 4, at 4:30PM in Room 402. The members of his committee are Sanjeev Arora (advisor), Moses Charikar and Bernard Chazelle (readers), and Boaz Barak and Ken Steiglitz (non-readers). Everyone is invited to attend his talk. His abstract follows below. ------------------------------------------------- Title: Non-Local Analysis of SDP-Based Approximation Algorithms Abstract: Semidefinite Programming (SDP) has been at the core of many approximation algorithms since the seminal work of Goemans and Williamson on MAX-CUT. Analysis of the approximation guarantee afforded by SDP-based approximation algorithms has traditionally relied on a comparison of local random events to corresponding local structures in the input. A marked departure from this approach was demonstrated recently in the work of Arora, Rao, and Vazirani on SPARSEST CUT, where a more nuanced probabilistic argument was used to combine local random events, thus yielding an improved approximation guarantee. I will describe a number of SDP-based algorithms which admit a non-local analysis of their approximation guarantee. In one case, the analysis is inspired by the approach of Arora-Rao-Vazirani, while in other cases, both the algorithm and the analysis make novel use of SDP hierarchies. These hierarchies give progressively tighter relaxations of combinatorial problems. Previously they had been shown not to yield any significant improvement in the approximation of various important problems, thus the results I will discuss mark a first positive use of these hierarchies. In particular, I will describe the following results: 1. A proof that the algorithm of Blum and Karger for coloring 3-colorable graphs yields a legal coloring using at most O(n^0.2130) colors (as opposed to the original guarantee of O(n^0.2142)). 2. An algorithm for coloring 3-colorable graphs which yields a legal coloring using at most O(n^0.2072) colors. This algorithm extends that of Blum-Karger, and uses the third level of the Lasserre SDP hierarchy. 3. An approximation algorithm which finds an independent set of size n^poly(gamma) in any 3-uniform hypergraph which contains an independent set of size gamma*n (previous algorithms were known only for gamma>1/2). This algorithm uses n^(1/poly(gamma)) levels of the Lasserre SDP hierarchy.

1 0

Speaker Wed 2/27 -
by Ginny Hogan 25 Feb '08

25 Feb '08

Christiane Fellbaum, Princeton, will present her talk "WordNet: A lexical resource for Natural Language Processing" at 4:15pm Computer Science Room 105 -

1 0

Friday Feb 22 noon: Ian Buck->John Danskin, nVidia, "GPU Computing"
by Adam Finkelstein 22 Feb '08

22 Feb '08

The talk is as planned at noon; however, due to a canceled flight we have a change of speaker and slight change in emphasis: Speaker: John Danskin Title: NVIDIA GeForce 8800 Graphics Processor: development and direction Time/Place: Today, noon, Computer Science Bldg, room 302 Abstract: The GeForce 8800 and its derivative architectures are the fastest available graphics processors. In an architectural departure, they are significantly more flexible than previouos processors. In this talk Dr. Danskin will discuss our goals for the 8800, the decision making process, new architectural features, performance, and some challenges for the future. Dr. Danskin is Vice President of GPU Architecture at NVIDIA, Chief Architect for the GeForce 8800 GPU, and holds a PhD in Computer Science from Princeton University. On Wed, Feb 20, 2008 at 10:58 PM, Adam Finkelstein <af(a)cs.princeton.edu> wrote: > Talk announcement: > > Speaker: Ian Buck, nVidia > Title: GPU Computing > Time/Place: Friday, noon, Computer Science Bldg, room 302 > > Abstract: > > Many researchers have observed that general purpose computing with > programmable graphics hardware (GPUs) has shown promise to solve many of > the world's compute intensive problems, many orders of magnitude faster > the conventional CPUs. The challenge has been working within the > constraints of a graphics programming environment to leverage this huge > performance potential. GPU computing with CUDA is a new approach to > computing where hundreds of on-chip processor cores simultaneously > communicate and cooperate to solve complex computing problems, > transforming the GPU into a massively parallel processor. The NVIDIA > C-compiler for the GPU provides a complete development environment gives > developers the tools they need to solve new problems in > computation-intensive applications such as product design, data > analysis, technical computing, and game physics. In this talk, I will > provide a brief history of computing with GPUs, how CUDA can solve > compute intensive problems, and where GPU computing will be going in the > future. > > Bio: > > Ian Buck completed his Ph.D. at the Stanford Graphics Lab in 2004. His > thesis was titled "Stream Computing on Graphics Hardware," researching > programming models and computing strategies for using graphics hardware > as a general purpose computing platform. His work included developing > the "Brook" software toolchain for abstracting the GPU as a general > purpose streaming coprocessor. Ian received is B.S.E from Princeton and > was a proud member of the Princeton CS Graphics Group. He currently > works for NVIDIA as the GPU-Compute software manager. >

1 0

Z Barutcuoglu preFPO
by Melissa M Lawson 21 Feb '08

21 Feb '08

Zafer Barutcuoglu will present his preFPO on Thursday February 28 at 1:30 PM in Room 402. The members of his committee are: Rob Schapire (advisor); Olga Troyanskaya and David Blei (readers); Mona Singh and Fei-Fei Li (non-readers). Everyone is invited to attend his talk. His abstract follows below. ---------------------------------- Classification problems encountered in real-life applications often have domain-specific structural information available on the measured data, which cannot be readily accommodated by conventional machine learning algorithms. Ignoring the structure and blindly running a conventional algorithm on the numerical data can compromise the quality of solutions. This thesis provides answers to two such complementary settings; one where there is a hierarchy among multiple class labels (output structure), and one where the input features are known to be sequentially correlated (input structure). Probabilistic graphical models are used to encode the dependencies, and efficient Bayesian inference algorithms are used for parameter estimation. While both scenarios are motivated by real bioinformatics problems, namely gene function prediction and aneuploidy-based cancer classification, they have applications in other domains as well, such as computer graphics, music, and text classification.

1 0

Friday Feb 22 noon: Ian Buck, nVidia, "GPU Computing"
by Adam Finkelstein 20 Feb '08

20 Feb '08

Talk announcement: Speaker: Ian Buck, nVidia Title: GPU Computing Time/Place: Friday, noon, Computer Science Bldg, room 302 Abstract: Many researchers have observed that general purpose computing with programmable graphics hardware (GPUs) has shown promise to solve many of the world's compute intensive problems, many orders of magnitude faster the conventional CPUs. The challenge has been working within the constraints of a graphics programming environment to leverage this huge performance potential. GPU computing with CUDA is a new approach to computing where hundreds of on-chip processor cores simultaneously communicate and cooperate to solve complex computing problems, transforming the GPU into a massively parallel processor. The NVIDIA C-compiler for the GPU provides a complete development environment gives developers the tools they need to solve new problems in computation-intensive applications such as product design, data analysis, technical computing, and game physics. In this talk, I will provide a brief history of computing with GPUs, how CUDA can solve compute intensive problems, and where GPU computing will be going in the future. Bio: Ian Buck completed his Ph.D. at the Stanford Graphics Lab in 2004. His thesis was titled "Stream Computing on Graphics Hardware," researching programming models and computing strategies for using graphics hardware as a general purpose computing platform. His work included developing the "Brook" software toolchain for abstracting the GPU as a general purpose streaming coprocessor. Ian received is B.S.E from Princeton and was a proud member of the Princeton CS Graphics Group. He currently works for NVIDIA as the GPU-Compute software manager.

1 0

Speaker Today - 4:15pm
by Ginny Hogan 19 Feb '08

19 Feb '08

Christos Papadimitriou, UC Berkeley will present his talk "The Algorithmic Lens: How the Computational Perspective is Transforming the Sciences" today at 4:15pm Computer Science Room 105.

1 0

/@rts: Tuesday, 2/19 - David Stork - "When Computers Look at Art: Computer Vision and Image Analysis in Humanistic Studies of the Visual Arts"
by Perry R Cook 18 Feb '08

18 Feb '08

Hey all, Please forward to any friends you might have that might be interested in art, art history, art fraud, etc. David is an old friend and collaborator, and always gives really entertaining talks. For the last couple of years he's been embroiled in the controversy about whether the masters used machines and optics to make their perspective drawings and paintings. David is the "Stork" in Duda, Hart and Stork, "Pattern Classification, 2nd edition" This talk is certain to have lots of computer vision, machine learning, and art in it. PRC 2/19 - David Stork - "When Computers Look at Art: Computer Vision and Image Analysis in Humanistic Studies of the Visual Arts" "When Computers Look at Art: Computer Vision and Image Analysis in Humanistic Studies of the Visual Arts" scientist David Stork - Tuesday, February 19, 4:30 pm 185 Nassau Street, James Stewart Theater New computer methods have been used to shed light on a number of recent controversies in the study of art. For example, computer fractal analysis has been used in authentication studies of paintings attributed to Jackson Pollock recently discovered by Alex Matter. Computer wavelet analysis has been used for attribution of the contributors in Perugino's Holy Family. An international group of computer and image scientists is studying the brushstrokes in paintings by van Gogh for detecting forgeries. Sophisticated computer analysis of perspective, shading, color and form has shed light on David Hockney's bold claim that as early as 1420, Renaissance artists employed optical devices such as concave mirrors to project images onto their canvases. How do these computer methods work? What can computers reveal about images that even the best-trained connoisseurs, art historians and artist cannot? How much more powerful and revealing will these methods become? In short, how is computer image analysis changing our understanding of art? This profusely illustrate lecture for non-scientists will include works by Jackson Pollock, Vincent van Gogh, Jan van Eyck, Hans Memling, Lorenzo Lotto, and others. You may never see paintings the same way again. Bio: Dr. David G. Stork is Chief Scientist of Ricoh Innovations and Visiting Scholar at Stanford University, where he has held appointments, taught, and sat on dissertation committees frequently over the last 17 years in the departments of Computer Science, Electrical Engineering, Statistics, Psychology and Art and Art History. He has published in optics and art for over two decades, including Seeing the Light: Optics in Nature, Photography, Color, vision and Holography (Wiley), the leading textbook on optics in the arts. A graduate in physics of the Massachusetts Institute of Technology and the University of Maryland at College Park, he also studied art history at Wellesley College and was Artist-in-Residence through the New York State Council of the Arts. His anamorphic photographs and graphics (based on late Renaissance methods) have appeared in small art journals as well as Optics and Photonics News and Scientific American magazine. He has taught courses such as ''Light, color and visual phenomena,'' ''The physics of aesthetics and perception,'' and ''Optics, perspective and Renaissance painting'' over the last quarter century variously at leading liberal arts and research universities such as Wellesley College, Swarthmore College, Clark University and Stanford University. He is a member of the International Foundation for Art Research and co-editor of Computer Image Analysis in the Study of Art (SPIE 2008), the first symposium volume on the topic. He holds 35 US patents and has published numerous technical papers on human and machine learning and perception of patterns, physiological optics, image understanding, concurrency theory, theoretical mechanics, optics, image processing, as well as five books, including Pattern Classification (2nd ed.), the world's all-time best-selling textbook in the field, translated into three languages and used in courses in over 250 universities worldwide. He has served on the editorial boards of five international journals and has delivered over 45 plenary, invited or distinguished lectures at universities and conferences (atop nearly 200 traditional invited colloquia and seminars). He created the PBS television documentary 2001: HAL's Legacy, based on his book HAL's Legacy: 2001's Computer as Dream and Reality (MIT). He was one of four scientists invited to comment on Mr. Hockney's theory at the December 2001 Art and Optics Symposium at the New York Institute for the Humanities and one of two scientists invited to present a lecture in the symposium exploring the possible use of optics by Renaissance painters at the Optical Society of America's Annual Meeting in Rochester, NY, October 2004. URLs: http://www.diatrope.com/stork/FAQs.html

1 0

Distinguished colloquium on Tues Feb 19: Christos Papadimitriou
by Sanjeev Arora 17 Feb '08

17 Feb '08

Christos Papadimitriou of UC Berkeley will speak in our Distinguished Colloquium series on Tues Feb 19 at 4:15pm. He gave this talk as a plenary speaker at FCRC and also at several depts around the country. I recommend it highly. Please let me know if you would like to meet with Christos on Mon or Tues afternoon. Sanjeev --- *The Algorithmic Lens: How the Computational Perspective is Transforming the Sciences * *Christos Papadimitriou* UC Berkeley Computational research transforms the sciences (physical, mathematical, life or social) not just by empowering them analytically, but mainly by providing a novel and powerful perspective which often leads to unforeseen insights. Examples abound: quantum computation provides the right forum for questioning and testing some of the most basic tenets of quantum physics, while statistical mechanics has found in the efficiency of randomized algorithms a powerful metaphor for phase transitions. In mathematics, the P vs. NP problem has joined the list of the most profound and consequential problems, and in economics considerations of computational complexity revise predictions of economic behavior and affect the design of economic mechanisms such as auctions. Finally, in biology some of the most fundamental problems, such as understanding the brain and evolution, can be productively recast in computational terms. My talk is structured around eight vignettes exemplifying this pattern.

1 0

Y Makarychev FPO
by Melissa M Lawson 06 Feb '08

06 Feb '08

Yury Makarychev will present his FPO on Tuesday February 12 at 1PM in room 302. The members of his committee are Moses Charikar, advisor; Bernard Chazelle and Assaf Naor (NYU), readers; Boaz Barak and Rob Schapire, nonreaders. A copy of his thesis, "Approximation Algorithms for Constraint Satisfaction Problems", is on display in room 310. Everyone is welcome to attend his talk.

1 0