Abstract: The Xbox kinect is one of the most commercially successful applications of computer vision research, with around 8 million units sold. In this pizza seminar, I'll introduce the problem of 3D human pose estimation from depth images, show some of the machine learning and computer vision algorithms behind the kinect's ability to track a user's skeleton in realtime, and talk about my work on a new method for pose estimation developed while I was an intern at Microsoft Research.

Abstract: Last quarter, I achieved a 285-fold speedup in a Python implementation of the 2D marching cubes algorithm by adopting a better algorithm and porting the inner loops to Cython, a Python-like language which compiles down to C. Today I will discuss my methods and try to comment more generally on optimization of Python.

Abstract: A "k-uniform hypergraph" H is a pair H = (V,E), where V is a set of elements, each called a "vertex", and E = {S_1, S_2, ..., S_m } is a collection of distinct k-subsets of V, each called a "hyperedge". The "degree" of a vertex v, denoted by deg(v), is equal to the number of (hyper)edges incident with the vertex v. The "degree sequence" of a (hyper)graph H with vertices v_1, v_2,..., v_n is defined as d(H)=(deg(v_1), deg(v_2), ..., deg(v_n) ). The problem of characterizing degree sequences of k-uniform hypergraphs, i.e. k-hypergraphic sequences, is a long standing open question in hypergraph theory. We investigate properties of degree sequences of k-hypergraphs as well as the properties of their convex hull polytopes. We introduce a set of necessary conditions on a non-negative integral sequence to be k-hypergraphic, dividing vertices and hyperedges into distinct classes. For properties of the convex hull polytopes of k-hypergraphic sequences, first we generalize some known properties of the polytopes of (simple) graphical sequences to the polytope of k-hypergraphic sequences, using our result for properties of k-hypergraphical sequences. Then we reduce an open problem concerning "holes" in the polytope of degree sequences to a well-known problem on lattice points.

Abstract: We'll discuss nonlinear dynamics and the impact of small perturbations on forecasts. We'll use simple experiments to demonstrate the ideas of stability, chaos, ensemble uncertainty quantification and, if there's time, adjoint sensitivity. We'll investigate the Lorenz oscillator and will draw parallels between it and numerical weather simulation.

Abstract: From the moment we set foot on grad school, most of us are plagued by a simple question: "What exactly is a dissertation?" Sure, we all know the textbook definition, but what *exactly* is the extent and breadth of work required to earn a ticket out of grad school? And how do you go about structuring a piece of work that is going to span several years? Having just completed my dissertation, I believe I have some insights to share about this. In this presentation, I will describe the thought process that led to my dissertation, interleaved with a description of some of my doctoral work. 1st, 2nd, and 3rd year PhD students are specially encouraged to attend.

Abstract: This talk looks at some theoretical aspects of obtaining reproducing kernels recursively via neural responses. I will give two natural properties that one can ask of neural responses in such a hierarchical framework (satisfied for example by the average and max neural responses), and show that any kernel obtained (over several layers) by neural responses with these properties (even max) can be written as a sum of kernels obtained by weighted averages (between two layers). I will comment on this in light of developing a learning theory for such kernels.

Abstract: Text mining applications typically involve statistical models that require accessing and updating the model parameters in an iterative fashion. With the growing size of the data, such models become extremely parameter rich, and naive parallel implementations fail to address the scalability problem of maintaining a distributed look-up table that maps model parameters to their values. We evaluate several existing alternatives to provide coordination among worker nodes in Hadoop clusters, and suggest a new multi layered look-up architecture that is specifically optimized for certain problem domains. Our solution exploits the power-law distribution characteristics of the phrase or n-gram counts in large corpora while utilizing a Bloom Filter, in-memory cache and an HBase cluster at varying levels of abstraction.

Abstract: In 1976, Berman and Hartmanis conjectured that no NP-complete set could have "low information content." One formalization of "low information content" is the notion of sparsity: a language is sparse if there is a polynomial p such that it has at most p(n) strings of length n, for all n. In 1982 Mahaney proved that this was essentially the case: if P is different from NP, then no NP-complete language is sparse. I will give some background on these conjectures, including the intuitive reason why Berman and Hartmanis made their initial conjecture. I will mention some related results, and then give a simplified proof of Mahaney's Theorem. The talk is aimed to be accessible to non-theorists, but still be interesting to theorists :). Especially interesting to all should be a delicious combination of cheese, dough, tomato sauce, and toppings.

Abstract: We study the behavior of the popular Laplacian Regularization method for Semi-Supervised Learning at the regime of a fixed number of labeled points but a large number of unlabeled points. We show that in Rd, d > =2, the method is actually not well-posed, and as the number of unlabeled points increases the solution degenerates to a noninformative function. We also contrast the method with the Laplacian Eigenvector method, and discuss the "smoothness" assumptions associated with this alternate method.

Abstract: I will discuss some topological/geometric aspects of routing in ad hoc networks. First I will give some background into how computational geometers got involved in the area about 10 years ago and go over the standard Face Routing algorithm ('99) which spurred interest in local geometric algorithms with logarithmic memory. I will discuss some results of Kranakis, Urrutia and mine from the last couple of years on extending Face Routing, and also go over related results by Durocher et al, and also by Wattenhofer. Finally I will show there exists a local routing algorithm transporting O(g log n) memory which is correct in any connected graph of order n embedded "reasonably" on a known oriented surface of genus g.

Abstract: The question of NP vs coNP can be neatly characterized as "Are there short proofs that a boolean formula is NOT satisfiable?" and is one of the biggest open questions in complexity theory; it can also be phrased as "Is nondeterministic polynomial time closed under complement?" In other words, if a language is in NP, must its complement also be in NP? I will not talk about this problem. I *will* talk about the related problem you get by replacing "time" with "space." In this setting, the answer is a surprising and resounding "YES," not just for polynomial space, but for (essentially) any space bound. This gem of complexity theory was proven in 1988, essentially by giving a clever algorithm, and, what's more, the whole algorithm can be presented in no more time than a pizza seminar! Before giving the proof, however, I'll discuss a bit about what this all actually means.

** This is a practise talk for my upcoming presentation at STACS 2010 ** (Keywords: Decision Tree Complexity, Group Actions, Simplicial Complex, Goldbach Conjecture) A boolean function f on N variables is called "evasive" if its decision tree complexity is N, i.e., one must query *all* the variables (in worst case) in order to decide if f(X) = 1. A graph property of n-vertex graphs is a boolean function on N = n \choose 2 variables which is invariant under the relabeling of vertices. A graph property is called monotone if it is closed under deletion of edges, e.g., planarity, 3-colorability etc. The following conjecture due Aanderaa-Rosenberg-Karp is a longstanding (35+ years) open question: "every non-trivial monotone graph property must be evasive." An important special case is the class of properties given by a "forbidden subgraph," i.e., all n vertex graphs which do not contain a fixed subgraph H. We confirm the evasiveness of several monotone graph properties under widely accepted number theoretic hypotheses (e.g. Generalized Riemann Hypothesis, Chowla's Conjecture on smallest Dirichlet primes etc). In particular, we show: (a) forbidden subgraph is evasive for all large enough n (b) any monotone property of sparse graphs (< n^{3/2 - \epsilon} edges) is evasive. Even our weaker unconditional results rely on some deep and interesting properties of the integers such as Vinogradov's theorem on Goldbach conjecture asserting that every odd integer can be expressed as the sum of three primes. Our main technical contribution here is in connecting the topological framework of Kahn, Saks and Sturtevant 84,(further developed by Chakrabarti, Khot and Shi 02), to analytic number theory via better analysis (e.g. using Weil's character sum estimates) of the orbital structure of permutation groups and their connection to the distribution of prime numbers. This is a joint work with Laci Babai, Anandam Banerjee and Vipul Naik.

Abstract: Stop consonants (/p/, /t/, /k/, /b/, /d/, /g/) differ by whether they are voiced (like /b/, /d/, /g/) and their place of articulation (e.g. the lips for /p/ and /b/). Voice onset time (VOT), the difference between the onset of a stop's burst and the onset of voicing in the following phone, is an important perceptual cue to stop voicing and place in human speech perception. VOT measurements are extensively used in phonetic research, and are usually taken by hand. Manual measurements are time-intensive, but there is currently no reliable algorithm for automatic measurement. To replace manual measurement, automatic measurement would need to be precise on the order of inter-transcriber reliability, about 5 ms (mean absolute difference). This is because VOT can differ by as little as 5--15 ms (depending on the speaker) for different consonants, and is extensively conditioned by speaking rate, speaker, phonetic environment, and word frequency. We describe a discriminative approach to VOT measurement, considered as a special case of predicting structured output from speech using Structured SVM. We use acoustic features, extracted with a low frame size, to detect the start and end of VOT with high time resolution. Applied to voiceless stops from two corpora, the algorithm achieves ITR-level precision, and compares favorably to related previous work.

Abstract: Python is slow, consistently quoted 10-20 times slower than C, so why do so many people use it for scientific computing? A trend that has been steadily increasing across the fields is using Python for everything from building prototypes, running large parallel jobs, to even replacing industry proven standards like Matlab. I will take you through a whirlwind tour of the possibilities in Python for scientific computing.

So-called "network science" has seen a tremendous surge in the past decade, mostly due to the increase in available datasets (from food webs and genetic networks to the web, the internet, and social networks) and the increase in computing power that makes it possible to analyze those datasets. Network motifs -- subgraphs that occur more frequently than would be expected based on a randomized model -- are supposedly the building blocks of these networks, in the way that, say, NAND gates or ALUs are the building blocks of microprocessors. I will talk about whether or not network motifs truly are the building blocks of real-world networks, and how we might be able to tell. Along the way, I'll discuss some of the similarities and differences between network science and classical graph theory that make network science so exciting, and I'll tell a story of how forcing a theorist (me) to actually implement an algorithm led to the discovery of a better algorithm and a new property of real-world networks.

Term-rewriting systems transform an input term by successively rewriting it according to a set of directed equations. Such systems have applications in automated theorem provers, computer algebra systems, and the semantics of programming languages. This talk introduces term-rewriting by building a model of the card game "war" in PLT Redex, a domain-specific language for specifying context-sensitive rewriting systems, highlighting Redex's support for visualization and randomized testing.

Graphics Processing Units (GPUs) are processors attached to video cards that are optimized for doing parallel floating-point computation. With the release of packages like NVidia's CUDA, it is possible to write C-like code that shifts some of your math-intensive code onto the video card to gain significant speedups. This talk will provide an overview of the programming model, a walkthrough of some sample code showing how to take advantage of the hardware, and anecdotal data on what types of problems will and will not benefit from migration to the GPU.

Cloud Computing has become another buzzword after Web 2.0. However, there are dozens of different definitions for Cloud Computing and there seems to be no consensus on what a Cloud is. On the other hand, Cloud Computing is not a completely new concept; it has intricate connection to the relatively new but thirteen-year established Grid Computing paradigm, and other relevant technologies such as utility computing, cluster computing, and distributed systems in general. This talk strives to compare and contrast Cloud Computing with Grid Computing from various angles and give insights into the essential characteristics of both.

Object recognition is the task of locating and labeling object classes (e.g., bicycle or person) in images. It remains as one of the most challenging problems in computer vision. While the problem is far from solved, in recent years deformable part models have achieved excellent results on challenging data sets. This talk provides an introduction to deformable part models by first introducing object recognition with a rigid template. We will discuss a broad range of issues including how to represent image data, templates as linear classifiers, composing templates into part models, efficient object detection when the part model's graph is a tree, and finally learning deformable part models with the Latent SVM algorithm. We will conclude with experimental results from the 2008 PASCAL VOC Challenge.

Abstract: ML is an excellent language for writing concise, high-level programs. As a case study, we will consider the design and implementation of an abstract game-playing system such that the specification of the game is kept entirely separate from that of the decision strategy; thus games and strategies are able to be mixed and matched freely in particular programs. We will incidentally see how an ML program can match a mathematical specification of an algorithm very closely.

Time permitting, we will also consider some combinatorics problems whose solutions are nicely expressed in ML, in the domains of music theory and/or the card game Set.

This seminar will include live demonstrations of building software with ML. The intended audience is students and enthusiasts of computer science who have heard of, say, ML, algebraic datatypes, module systems, Hindley-Milner typechecking, functional programming, and so on, but have little or no direct experience reaping the multifarious benefits of these technologies.

Abstract: In theoretical computer science, issues of encoding are usually swept under the rug. Do you write your number in unary, binary, or ternary? Well, as long as we stay away from unary we don't care. Do you store your graphs as adjacency matrices, or as edge lists? Well, it won't affect whether or not a problem has a polynomial-time solution, so we don't really care. But if one computational problem is just a re-encoding of another problem, then they're really the same problem. So maybe we should care a little bit.

The ubiquity of NP-complete problems is well-known to anyone who's taken an introductory course in theoretical computer science. By now over 3000 problems have been proved NP-complete. But what they don't tell you -- sometimes even in upper level theory courses -- is an observation made in 1976, just a few years after NP-completeness was first defined, that all known NP-complete problems are just re-encodings of one another. They're not just reducible to one another, they are the same problem.

In this talk, I'll discuss a formal notion of re-encoding, give a hint of why the above statement is true, and discuss what this potentially deep observation might mean.

Abstract: Expander graphs are one of the most powerful general tools in theoretical computer science. In this talk, we will sketch several roughly equivalent definitions of expansion, and try to give some intuition for why they are so important. Expander graphs are "quasi-random"--in many ways, they "look random". They can be used to simulate randomness, allowing us to decrease the amount of randomness we use in a randomized algorithm. We will also see a simple example of an infinite family of expander graphs, and discuss their connection to random walks.

Abstract: Having interviewed several hundred job candidates from ages 18 to 60, mid-college to Ph.D. and heavily published researchers, I've seen just about every terrible mistake that keeps an otherwise potentially qualified candidate from making a good impression. Come learn about what interviewers and companies are really doing and looking for during an interview, how to avoid "instant no-hire" actions, and what you should do to prepare. Shocking interviewee anecdotes guaranteed!

Abstract: Grid Computing enables computational resources (clusters, supercomputers, workstation pools, storage, etc.) to be shared across administrative domains, allowing researchers from a variety of fields (such as high energy physics, bioinformatics, climate research, astrophysics, etc.) to easily tap into the resources of multiple sites. Many research projects benefit from using grids, from large-scale projects like CERN's Large Hadron Collider to a variety of smaller projects served by general-purpose grids such as the Open Science Grid.

This talk provides a gentle introduction to Grid Computing, and does not require a background in computer science (although some parts will be slightly technical).

Abstract: We will show how to assign small (log n bits long) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching is unique. The procedure to assign the weights works in deterministic Logspace whereas a randomized weighing scheme is known for long time for arbitrary bipartite graphs (Mulmuley, Vazirani and Vazirani, isolation lemma). As a consequence we improve the parallel complexity of bipartite planar matching. Deterministic parallel complexity of constructing a perfect matching in (not necessarily bipartite) planar graph is still open.

Joint work with Samir Datta and Sambuddha Roy.

Abstract: The final stage of solving a partial differential equation is almost always solving some system of linear equations. Some of the most popular approaches to solving linear systems are iterative; they converge to an answer, usually within some tolerance, after a number of steps. The class of iterative methods known as relaxation methods are very simple to implement and fairly robust, but have convergence rates highly dependent upon the eigenspectrum of the system being solved. Multigrid methods are a class of iterative solvers where coarser versions of the linear system are used to decimate lower frequency parts of the error which decay very slowly if the whole system is considered. The allure of these methods is that under the right conditions they take only O(n) work to solve a system of n unknowns, making it possible to solve very large problems very quickly. Several classes of multigrid methods and their applications will be briefly discussed.

Abstract: This talk concerns the implementation of Manticore's parallel constructs. Data parallel programs are compiled into a language that can be thought of as core ML plus the primitives future, touch, and cancel. We use ropes as an important internal representation and a good fit for parallel computations. We will also discuss the mixture of exceptions and exception handlers with data parallelism, a novel feature of the Manticore design.

Abstract: Simulation has become a cornerstone of scientific advancement in all fields, but often large scale projects use limited methods and techniques due to choices of data management at the beginning of the project. Furthermore, small projects do not allow for a robust testing of new methods because of the small problem sizes and scopes. By automating the writing of simulations we are able to take advantage of new methods that would otherwise take too long to develop in a large scale project and small projects would be able to generate large problems very easily. I present several mathematical interfaces that are being studied here in Chicago and applied to partial differential equation solvers using finite element methods.

Abstract: In this talk I will present an algorithm to analyze digital image sequences made by total internal reflection fluorescence microscopy (TIRFM). The problem is to track tens or hundreds of vesicles moving near the surface membrane of a cell and identify the time and place of exocytosis.

I will describe the physics and the biology behind the problem. Then, I will show a statistical model for the video data that allows us to properly weight various hypotheses online. Finally, I will describe the algorithm: a sequence of coarse-to-fine tests, derived from the statistical model, that are used to detect and track the objects of interest.

Abstract: Mahdian and Saberi studied the problem of multi-unit auctions for perishable goods, in a setting where supplies arrive in an online fashion. This problem is motivated by an application in advertisement auctions on the internet. They gave a $1/4$-competitive algorithm for the problem with single-price auctions and truthful bidding.

We have got a better algorithm. In the talk I will introduce the problem and state the results.

Abstract: One hope of software engineering is that by organizing a large program well, it can be written as if it were a collection of small programs. In object-oriented languages, which dominate industrial application programming, classes are the main unit of organization. But it is increasingly recognized that classes are not enough: it would often be helpful to write code that applies across, through, between, within, or outside of classes. The result is a thriving ecosystem of language constructs, including mixins, traits, aspects, and many others. I will briefly review some of these constructs, and the problems they solve. Then I will present my own research, a simple extension to traits that costs little but buys much. To demonstrate the approach, I will show how to, with a minimal amount of fairy dust, shrink a class from several pages to a few lines of code. Finally, for the PL nerds, I will (very briefly) discuss the mixture of nominal and structural subtyping needed to support the proposal in the context of a language like Java.

Abstract: Graph Isomorphism is one of the most well-studied problems in computer science. In general we need lots of ``resources" for graph isomorphism. But what happens if we have the guarantee that either the two graphs are ``close" to isomorphic or ``far" from isomorphic. I will try to study this problem under various models of computation, mainly query complexity and communication complexity.

Abstract: To enable the rapid execution of many tasks on compute clusters, we have developed Falkon, a Fast and Light-weight tasK executiON framework. Falkon uses (1) multi-level scheduling to separate resource acquisition (via, e.g., requests to batch schedulers) from task dispatch, and (2) a streamlined dispatcher. Multi-level scheduling, introduced in operating systems research in the 1990s, has been applied to clusters by the Condor team and others, while streamlined dispatchers are found in volunteer computing systems. Falkon's integration of the techniques delivers performance not provided by any other system. We describe Falkon architecture and implementation, and present performance results for both microbenchmarks and applications. Microbenchmarks show that Falkon throughput and scalability are one to two orders of magnitude better than other schedulers. Applications (executed by the Swift parallel programming system) reduce end-to-end run time of up to 90% for large-scale astronomy and medical applications, relative to versions that execute tasks via separate scheduler submissions.

Abstract: Everyday life is full of decisions: Should you dress for sunny weather or rain? Drive to work, or take public transport (or walk)? If you drive should you take the freeway or local roads? Or the freeway part of the way, and local roads the rest, and if so which part? Will the stock market go up (so that you should invest) or down? Chinese, Indian, or Italian food for dinner? Or pizza? Should you attend this talk, or skip it because it will be boring? Many such decisions are recurrent: the same choices are available every day, but which decision is "correct" can vary from day to day. How can you learn from past mistakes to make the right decisions in the future?

In this talk, I will present a model for such online decision-making problems and various algorithms to tackle them. I will also discuss what it means for such algorithms to perform well.

Abstract: Finite Element Analysis is often presented in a continuous mathematical framework with derivations using functional analysis. This sort of analysis does not address major implementation issues and is often left aside by many treatments. We will explain finite elements for the non expert and then motivate several challenges to their implementations. Finally we borrow some ideas from topology to discuss the management of the simulation for the entire method. Hopefully this talk will be a gentle overview and motivate several open areas accessible to a computer scientist.

This is joint work with Michael Langberg (The Open University of Israel).

References:
[1]: R. Alshwede, N. Cai, S.-Y.R. Li and R. W. Yeung, "Network information flow," IEEE Trans. Info. Thy, vol. 46, pp. 1204-1216, Feb., 2000.
[2]: Z. Li, B. Li, "Network Coding in Undirected Networks," in Proc. of the 38th Annual Conference on Information Sciences and Systems (CISS), 2004.

Abstract: Consider the task of getting a computer to automatically classify web documents into several categories: news, sports, finance, politics, research etc. Traditional machine learning algorithms construct such classifiers from a set of manually labeled training examples. Labeling is slow, costly and often impractical due to the sheer amounts of data available. Semi-supervised learning is a new paradigm where classifiers are constructed by utilizing large amounts of unlabeled data together with a small set of labeled examples. In this talk, I will present two classes of algorithms: Manifold Regularization and Low-density Separation, which extend classical kernel methods (such as Support Vector Machines) for semi-supervised learning.