Events Archive: Winter 2010

For some would-be graphics programmers, the biggest barrier-to-entry is getting data to render. This is why there exist so many terrain renderers: by virtue of the fact that rendering height-fields tends to give pretty pictures from next to no "created" information. However, it becomes more difficult when programmers want to do indoor rendering (in the style of the Quake and Unreal games). Ripping map information from the Quake games is possible (and fairly simple), but their tool-chain is fairly clumsy from the point of view of adding a conversion utility.

My talk is about Constructive Solid Geometry from a Brush-based perspective (nearly identical to Unreal's and still very similar to Quake's). The basic idea is that there are brushes (convex volumes in 3-space) and they can either be additive (solid brushes) or subtractive (hollow, or air brushes). The entire world starts off as an infinite solid lump and you can start removing sections of it then adding them back in. The talk pertains to fast methods of taking the list of brushes and generating world geometry. I may touch on interface problems with the editor, but the primary content will be the different ways I generated the geometry and what I found to be best.

Bill Gates in his article “A Robot in every home” in the Scientific American describes how the current robotics industry resembles the 1970’s of the Personal Computer Industry. In fact it is not just Microsoft which has already taken a step forward by starting the Microsoft Robotics studio, but robotics researchers around the world believe that robotics and automation systems are going to be ubiquitous in the next 10-20 years (similar to Mark Weiser’s analogy of Personal Computers 20 years ago). Natural User Interfaces (NUIs) are going to revolutionize the way we interact with computers, cellular phones, household appliances, automated systems in our daily lives. Just like the GUI made personal computing a reality, I believe natural user interfaces will do the same for robotics.

During the presentation I will be presenting my ongoing software project on natural user interfaces as well as sharing my goals for the future, one of which is to provide an NUI SDK and the other to provide a common Robotics OS for every hardware vendor that will enable people to make applications without worrying about underlying functionality. If time permits I would like to present a demo of my software prototype.

Despite it being 2010, code is still being exploited due to stack overflows, a 40+ year old class of security vulnerabilities. In this talk, I will go over several common methods of program exploitation, both on the stack and on the heap, as well as going over some of the current mitigation techniques (i.e. stack canaries, ASLR, etc.) for these holes, and similarly, how some of these can be bypassed as well.

The theory of NP-completeness suggests that some problems in CS are inherently hard—that is, there is likely no possible algorithm that can efficiently solve them. Unfortunately, many of these problems are ones that people in the real world genuinely want to solve! How depressing! What can one do when faced with a real-life industrial optimization problem whose solution may save millions of dollars but is probably impossible to determine without trillions of years of computation time?

One strategy is to be content with an approximate (but provably "almost ideal") solution, and from here arises the theory of approximation algorithms. However, this theory also has a depressing side, as many well-known optimization problems have been shown to be provably hard to approximate well.

This talk shall focus on the depressing. We will prove that various optimization problems (such as traveling salesman and max directed disjoint paths) are impossible to approximate well unless P=NP. These proofs are easy to understand and are REALLY COOL thanks to their use of very slick reductions.

We shall explore many NP-hard optimization problems and state the performance of the best known approximation algorithms and best known hardness results. Tons of open problems will be mentioned, including the unique games conjecture, which, if proven true, implies the optimality of many of the best known approximation algorithms for NP-complete problems like MAX-CUT and INDEPENDENT SET.

I promise fun times and no gruesome math. Basic knowledge of graph theory and computational complexity might help but is not required.

Concurrency is hard. Well maybe not hard, but it sure is annoying to get right. Even the simplest of synchronization tasks are hard to implement correctly when using synchronization primitives such as locks and semaphores.

In this talk we explore what Software Transactional Memory (STM) is, what problems STM solves, and how to use STM in Haskell. We explore a number of examples that show how easy STM is to use and how expressive Haskell can be. The goal of this talk is to convince attendees that STM is not only a viable synchronization solution, but superior to how synchronization is typically done today.

The interactive proof system model of computation is a cornerstone of complexity theory, and its quantum computational variant has been studied in quantum complexity theory for the past decade. In this talk I will discuss an exact characterization of the power of quantum interactive proof systems that I recently proved in collaboration with Rahul Jain, Zhengfeng Ji, and Sarvagya Upadhyay. The characterization states that the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable with an ordinary classical computer using a polynomial amount of memory (or QIP = PSPACE in complexity-theoretic terminology). This characterization implies the striking fact that quantum computing does not provide any increase in computational power over classical computing in the context of interactive proof systems.

I will not assume that the audience for this talk has any familiarity with either quantum computing or complexity theory; and to be true to the spirit of the interactive proof system model, I hope to make this talk as interactive as possible -- I will be happy to explain anything related to the talk that I can that people are interested in learning about.

Come to a town hall style meeting with the managers of CSCF to discuss how to improve the undergraduate (student.cs) computing environment. Have gripes? Suggestions? Requests? Now is the time to voice them.

CSCF management (Bill Ince, Associate Director; Dave Gawley, Infrastructure Support; Dawn Keenan, User Support; Lawrence Folland, Research Support) will be at the meeting to listen to student concerns and suggestions. Information gathered from the meeting will be summarized and taken to the CSCF advisory committee for discussion and planning.

New to Unix? No problem, we'll teach you to power use circles around your friends! The popular tutorial returns for a second session, in case you missed the first one.

This first tutorial is an introduction to the Unix shell environment, both on the student servers and on other Unix environments. Topics covered include: using the shell, both basic interaction and advanced topics like scripting and job control, the filesystem and manipulating it, and ssh. If you feel you're already familiar with these topics don't hesitate to come to Unix 102 to learn about documents, editing, and other related tasks, or watch out for Unix 103 and 104 that get much more in depth into power programming tools on Unix.

Cairo is an open source, cross platform, vector graphics library with the ability to output to many kinds of surfaces, including PDF, SVG and PNG surfaces, as well as X-Window, Win32 and Quartz 2D backends. Unlike the raster graphics used with programmes and libraries such as The Gimp and ImageMagick, vector graphics are not defined by grids of pixels, but rather by a collection of drawing operations. These operations detail how to draw lines, fill shapes, and even set text to create the desired image. This has the advantages of being infinitely scalable, smaller in file size, and simpler to express within a computer programme. This talk will be an introduction to the concepts and metaphors used by vector graphics libraries in general and Cairo in particular.

Paul Lutus describes his early Apple II software development days, conducted from the far end of a 1200-foot power cord, in a tiny Oregon cabin. Paul describes how he wrote a best-seller (Apple Writer) in assembly language, while dealing with power outages, lightning storms and the occasional curious bear.

Paul also describes his subsequent four-year solo around-the-world sail in a 31-foot boat. And be ready with your inquiries -- Paul will answer your questions.

Paul Lutus has a wide background in science and technology. He designed spacecraft components for the NASA Space Shuttle and created a mathematical model of the solar system used during the Viking Mars lander program. Then, at the beginning of the personal computer revolution, Lutus switched career paths and took up computer science. His best-known program is "Apple Writer," an internationally successful word processing program for the early Apple computers.