Seminar Abstracts

James Abello, Rutgers University, DIMACS
Title: Graph Mining?

Abstract:

A variety of massive data sets exhibit an underlying structure that can be modeled as dynamic weighted multi-digraphs. Their sizes range from tens of gigabytes to petabytes. These include the World Wide Web, Internet Traffic and Telephone Call Detail. These data sets sheer volume brings with it a series of computational and visualization challenges due mainly to the I/O and Screen Bottlenecks. We present external memory algorithms for connectivity and minimum spanning trees together with heuristics for quasi-clique finding. We describe how hierarchy trees help us to cope in a unified manner with both, the I/O and screen bottlenecks. This line of research has suggested the need to look for "novel" graph representations in order to provide a user or a data-mining engine with informed navigation paths. We will discuss our results with graphs having on the order of 200 million vertices and several billion edges and we will point out some mathematical problems that have surfaced along the way. The overall goal is to extract useful information that can be brought into a user's palm top and to export these techniques to other mining domains. Related information can be found at http://www.mgvis.com or by emailing to abello@dimacs.rutgers.edu .

Nate Dean, Texas State University-San Narcos, Department of Mathematics
Title: Incomprehensible Graphs

Abstract:

In this talk we discuss a purely mathematical conjecture proposed by S. Ulam (Hammer 1977): In any partition of the integer lattice points into uniformly bounded sets there exists a set that is adjacent to at least six other sets. Actually, this problem turned out to be not as pure as we thought. It led us very naturally to some problems in network visualization that we’ve shown cannot be solved. (Collaborator: Kiran Chilakamarri, Texas Southern University)

Jerry Langer
Title: Ethics Case Study Workshop (Part 1)

Abstract:

Jenn Tam, Carnegie Mellon University, Department of Computer Science
Title: If You Break It You Should Fix It and If Possible Make It Better: Audio CAPTCHAs

Abstract:

Jennifer Tam is a third year PhD student at Carnegie Mellon University. As a first year, she worked on analyzing the security of various audio CAPTCHAs (an audio version of the warped images of text used to distinguish humans from bots on the web) including those from Google and reCAPTCHA. After creating a system that could automatically pass the audio CAPTCHAs more than 45% of the time thus breaking the CAPTCHAs, she focused on creating a better audio CAPTCHA during her second year.

Find out how Jennifer broke the original CAPTCHAs and how she uses human computation in her redesigned CAPTCHAs to get audio transcriptions from difficult audio. Jennifer will also address what ethical issues arose from analyzing security measures that are currently in use and how she dealt with them.

Jennifer is also a student coordinator of CMU’s Computer Science Department’s open house weekend during which prospective students are invited to visit the school and meet with faculty and students. She will offer valuable advice regarding grad school applications and what to ask once you get in.

Fred Roberts, Rutgers University, DIMACS
Title: Meaningless Statements in Epidemiology

Abstract:

A statement involving scales of measurement is called meaningless if its truth or falsity can depend on the particular versions of scales that are used in the statement. Using examples from the study of diseases such as HIV, malaria, and tuberculosis, we will give a variety of examples of meaningless and meaningful statements. We will briefly discuss the mathematical foundations of the theory of meaningfulness (which involves such topics as homomorphisms of ordered algebraic systems and functional equations), discuss ways to average scores that lead to meaningful statements, and, time permitting, discuss the meaningfulness of statistical tests. The talk will be self-contained. No knowledge of either epidemiology or the theory of measurement will be required.

Jerry Langer
Title: Ethics Case Study Workshop (Part 2)

Abstract:

Muthu Venkitasubramaniam, Cornell University, Department of Computer Science
Title: On Constant-Round Concurrent Zero-Knowledge

Abstract:

Loosely speaking, zero-knowledge interactive-proofs allow one player (called the Prover) to convince another player (the Verifier) of the validity of a mathematical statement, while providing zero additional knowledge to the Verifier. This is formalized by requiring that the view of every ``efficient'' verifier can be ``efficiently'' simulated. An outstanding open question regarding zero-knowledge is whether constant-round concurrent zero-knowledge proofs exist for non-trivial languages. We answer this question in the affirmative when modeling ``efficient adversaries'' as probabilistic *quasi-polynomial* time machines (instead of the traditional notion of probabilistic polynomial-time machines).

In this talk, I will give a brief introduction on zero-knowledge and concurrency and then present our result. The talk will be self contained.

This is joint work with Rafael Pass. Appeared in Theory of Cryptography Conference (TCC 2008).

Tinevimbo Shiri
Title: Modeling HIV Strain Dynamics

Abstract:

HIV poses a unique modeling challenge because the virus population continuously evolves to become a heterogeneous pool at any time. Mathematical models have contributed significantly to the understanding of various aspects of HIV pathogenesis and its basic biology. However models have not been successful in exploring questions related to risks associated with initiation of chronic therapy (such as highly active antiretroviral therapy (HAART)) a short while after a suboptimal transient regimen like Nevirapine for prevention of mother to child transmission (PMTCT). A further important set of questions arises about the effects of selection pressure, point mutations and recombination on shaping viral diversity. Mathematical descriptions have generally been limited to systems of ordinary differential equations describing mean field behavior or to statistical descriptions of genetic change. New modeling approaches are needed to answer some of these questions. In this talk, I will start by introducing a simple deterministic model interfaced with a stochastic component to explore the risk of occurrence of rare variants after sub-optimal treatment and the period at which the new genome lineage is likely to persist. The model shows that, even transient subpopulations of common mutants which appear to fade are associated with accelerated appearance of rarer mutations. Lastly, I will be talking about new conceptual approaches in modeling HIV sequence diversification.

Huilan Chang
Title: Studies on Two Group Testing Problems with the Introduction of Inhibitors

Abstract:

Pooling designs are common tools to efficiently discriminate positive clones from negative clones in clone library screening. Two variants of the well-known group testing problem are considered. In the first variant a finite set of items O and an unknown P by asking the least number of question of the form “Is |Q &cap P| = 1”, where Q is a subset of O. In the second variant of the problem, the answer to the question “Is |Q &cap P| = 1” is correctly YES if |Q &cap P| = 1 and NO if |Q &cap P| = 0, and it is left to an adversary otherwise. In some applications, there is a third type of clones called “inhibitors” whose effect in a sense is to obscure the positive clones in pools. We introduce inhibitors to those two variants of group testing problems.

Greg N. Frederickson, Department of Computer Science, Purdue University
Title: Beyond Swinging: Hinged Dissections that Twist or Fold

Abstract:

A geometric dissection is a cutting of a geometric figure into pieces that can be rearranged to form another figure. Some dissections can be connected with hinges so that the pieces form one figure when swung one way on the hinges, and form the other figure when swung another way. In addition to using "swing hinges", which allow rotation in the plane, we can use "twist hinges", which allow one piece to be flipped over relative to another piece via rotation by 180 degrees through a third dimension, and also "piano hinges", which allow rotation along a shared edge, a motion that is akin to folding. We also employ piano hinges in a "stack-folding dissection", producing a single assemblage that represents a dissection of a figure that is p levels thick to a second figure that is q levels thick.

This talk will introduce a variety of twist-hinged, piano-hinged, and stack-folding dissections of regular polygons and stars, and also polyominoes. The emphasis will be on both appreciating and understanding these fascinating mathematical recreations. I will employ algorithmic and tessellation-based techniques, as well as symmetry and other geometric properties, to design the dissections. The goal will be to minimize the number of pieces, subject to the dissection being suitably hinged. Animations and video will be used to demonstrate the hinged dissections, in addition to actual physical models.

Jószef Beck, Department of Mathematics, Rutgers University
Title: The Astonishing Uniformity of a Typical Billiard Path in the Unit Square

Abstract:

We study the long-time behavior of a point billiard, assuming the reflection off the wall is elastic (we ignore friction, air resistance, etc.) We prove several elegant properties of the billiard path. For example, if the slope of the initial direction is rational, then the billiard path is periodic, and if the slope is irrational, then the billiard path is (everywhere) dense, and what is more, it is uniformly distributed. For a typical starting point and a typical initial direction the billiard path represents the ``most uniformly distributed curve" in the unit square. We will clarify this vague statement.

Andrew Baxter, Rutgers University
Title: Counting Restricted Permutations via Computers

Abstract:

The concept of pattern avoidance in permutations was first introduced in the 1980s, with the first major paper appearing in 1985. Since then, there has been a bloom of interest in the subject. In 1998 Zeilberger introduced enumeration schemes, a structure which allows computers to count the number of patterns avoiding sets of patterns. This talk will introduce the concept of pattern avoidance, as well as outline enumeration schemes and their subsequent improvements.

Aaron Jaggard, DIMACS
Title:

Abstract:

Coming up...