Ming-Yang Kao - US grants

A separator of a graph is a set of vertices whose removal breaks the graph into small pieces. A cycle separator is a simple cycle whose vertices form a separator. Finding separators is an essential part of divide-and-conquer strategies for many graph-theoretic applications. The PI has recently discovered that, surprisingly, every graph has a cycle separator and such a cycle separator can be efficiently computed by depth-first search in sequential and parallel computations. Consequently, depth-first search now assumes a new role as a divide- and-conquer tool. This linkage between cycle separators and depth- first search has never been available before, and promises to bring about unconventional applications of depth-first search. This project is intended to explore new possibilities opened up by the search- separator linkage.

PI: Ming-Yang Kao
Institution: Yale University
Proposal Number: 9988376

In scientific disciplines, significant issues are sometimes assumed
away by overmodeling, which results in lost knowledge. Such
overmodeling is often caused by analytical or computational difficulty
of the issues involved. By shifting the existing balance among
modeling, analytical, and computational components of the current
solution to an issue, one inevitably discovers new technologies.
Motivated by this research philosophy, this project has three general
themes. The first is to explore trade-offs between modeling and
computation in finance with emphasis on advancing computational
technologies for practical and theoretical finance problems. The
second is to develop finance ideas to help solve computer science
problems. The third is to formulate novel finance problems which
break away from traditional paradigms of finance research.

This project pursues these three themes in five interrelated areas of
computational finance: (1) market modeling, (2) investment and trading
algorithms, (3) risk management, (4) market index design, and (5)
auctions.

For the area of market modeling, the main goal is to study short-term
predictability of stock markets using agent-based approaches. The
models established will be used to test algorithms developed for other
parts of the project.

For the area of investment and trading algorithms, this project
focuses on two fundamental issues: (1) what sorts of information can
be used to enhance the performance of a portfolio and (2) how to
measure the performance of investment and trading algorithms. Results
in this area can be useful for long-term investors such as those who
save for retirement.

For the area of risk management, this project investigates two basic
issues: (1) how to assess the risk of a portfolio of assets and (2)
how to design optimal portfolios which meet security requirements.
Results in this area may be used to help institutional investors
detect and minimize unwanted risks.

For the area of market index design, novel optimization problems will
be formulated to help design portfolios which are easier to manage
than popular market indices but can track or outperform the indices.

For the area of auctions, the primary goal is to use auction
algorithms to design solutions to computer science problems. To this
end, the project will identify auction primitives which can be used to
construct complicated auction mechanisms.

Electronic markets are emerging as a primary medium of trade in business-to-business, business-to-consumer, and consumer-to-consumer settings. In order to design viable electronic marketplaces, a host of novel interrelated game-theoretic and computational issues must be
addressed. With a team of interdisciplinary researchers from multiple institutions, this project will develop a unified theory of games and computing to guide and facilitate the growth of such markets. Specific research directions of the project include the following: (1) Market designs will be generalized to incorporate combinatorial bidding, multi-attribute preferences, multi-stage mechanisms, continuous mechanisms, and multi-unit sale; (2) New algorithms for clearing, quoting, incentive-compatible pricing as well as new incentive-compatible tractable mechanisms will be designed with particular emphasis on online and incremental updating of market states; (3) Bounded rationality of the agents will be investigated under a wide spectrum of models of computations, equilibrium concepts of game theory, and trade-offs between centers and agents; and (4) Novel approaches to relaxing the classic common prior assumption will be explored in order to develop practically useful models for ecommerce. The successful completion of this project will make significant contributions to both theory and practice in the areas of electronic commerce, multi-agent systems, algorithms, computational complexity theory, and game theory.

EIA 02-24449
Dinda, Peter A.
Banerjee, Prithviraj; Kao, Ming-Yang
Northwestern University

CISE RR: Collaborative Research on Wide-Area Network Computing Using Virtual Machines
This collaborative research project (with Fortes at University of Florida, proposal 02-24442), requiring a wide-area test bed that enables experimentation with, access to, and running of applications on unique resources, requests PC clusters, an IBM server, and other ancillary hardware for projects in
1. Distributed grid computing and information processing systems using virtualization technologies and
2. Information grids with real users and research applications requiring capabilities enabled by virtual machines (VMs).
Deploying a distributed system based on clusters connected by local, metropolitan, and wide area networks, the work aims to provide a virtual computing and data storage interface to clients that access resources on the underlying "information grid." The test bed includes the following defining features.
1. Virtualization capabilities, i.e., the ability to instantiate independent logical machines that can be multiplexed on physical processors (or fractions of them), storage and network I/O channels, and can use distinct operating systems;
2. Wide-area distribution, i.e., Internet-linked test bed components in independently-administered geographically-apart network domains;
3. Scalable capacity for both scientific computing and information processing; and
4. Heterogeneity.
Interrelated projects enabled by the test bed towards the goal of developing VM-based middleware for grid computing include virtualized end resources, monitoring and prediction, interactive computing, virtual file systems, data management, cycle selling, and security. Information grids and web portals for use of CAD tools are also enabled by the infrastructure for dissemination of collaborative research results and data, and for digital government services. From the availability of the portals and grid-computing resources benefits are expected in brain-machine interfaces, biologically-inspired nanocomputing, auction-based computing, distributed knowledge applications, medical imaging and data archiving, light-scattering spectroscopy, and mixed non-linear optimization. Collaborations include the Sigmicro microarchitecture center, NETCARE and the Purdue-hosted Nanohub (enabling users to run tools for computer architecture and parallel computing, and nanoelectrnics). The project impacts some minority serving institutions such as Chicago State and Florida A& M Universities and enables a testbed for a transnational digital government projects involving Carnegie Mellon University, University of Belize, University of Colorado, University of Florida, University of Massachusetts, and Pontificia Universidad Catolica Madre y Maestra of the Dominican Republic.

Yan Chen
Northwestern University
0627751
Panel: P060969

Abstract


Attacks are commonplace in today's networks, and identifying them
rapidly and accurately is critical for large network/service
operators. Most existing intrusion detection systems (IDSes) are
signatures-based. But such signatures are usually generated manually
or semi-manually, a process too slow for defending against
self-propagating malicious codes, or worms. To evade detection by
signatures, attackers may also employ polymorphic worms which change
their byte sequence at every successive infection.

In order to thwart a zero-day worm attack, it is essential to design
an automatic signature generation system against polymorphic worms
which may be deployed at the network gateways/routers and satisfy
the following requirements: network-based, noise-tolerant,
attack-resilient, and having efficient signature matching.

None of the existing work satisfy all the requirements above. Thus
the PIs design NAPOLEON( Network-based Attack-resilient
POLymophic-worm signaturE generatiON), a network-based automatic
signature generation system with all the aforementioned properties.
NAPOLEON has two components which complement each other: TOken-based
Signature Generator (called TOSG) and LEngth-based Signature
Generator (called LESG).

This project combines theoretical computer science with practical
network security research. The PI has extensive experience on
network anomaly/intrusion detection. The co-PI's expertise is in
theoretical computer science and algorithms and has a track record
of applying them to various applications including security.

This interdisciplinary research will have a strong impact. For
example, during the PIs' collaboration, they have found that certain
algorithmic techniques in bioinformatics are directly or indirectly
applicable to worm detection problems.

Project Summary

Self-assembly is a process by which simple objects assemble into complex structures under minimal or no external control. It is believed that self-assembly technology will ultimately permit precise and efficient fabrications of nanostructures. Self-assembly is common in nature but is not yet well understood from mathematical and programming (i.e., algorithmic) perspectives. There are many kinds of self-assembly. This project will focus on self-assembly of DNA molecules.

Small molecules consisting of multiple DNA strands have been designed to act as four-sided building blocks (which are called tiles) for DNA self-assembly. Experimental work has demonstrated that these building blocks can effectively perform computation as well as assemble crystals. Some key aspects of the self-assembly process of such building blocks have been used to formulate a preliminary mathematical model called the abstract tile assembly model. This model extends Wang's mathematical theory of two-dimensional tilling by adding a natural mechanism for growth. The model consists of a set of square tiles. The four sides of a tile are each associated with a glue (which is implemented as a DNA strand). A special tile in the tile set is designated as the seed. Self-assembly proceeds by starting with the seed and then attaching copies of tiles from the tile set one by one to the growing seed whenever the total binding strength between a tile and the seed is no less than a threshold (which is implemented as the temperature in the tube).

Intellectual Merit: This project is in the intersection of nanotechnology and computer science with a focus on exploring the potential and limitation of DNA self-assembly from the perspective of algorithms.
The project will build on the PI's prior results and insights in this emerging field to explore theories of encoding algorithms into the glues of DNA tiles to guide the self-assembly process. Specifically, the project will investigate three interconnected research directions. These directions together will explore new ways to minimize the number of tiles with distinct glues (which is called the tile complexity) used to assemble a structure, to minimize the amount of time needed to assemble a structure, and to impose desirable structural properties on the assembly process as well as on the assembled structures. A common theme across these directions is to seek ways to automate the design of DNA self-assembly systems. Our approaches in this project will be theoretical, and we will design algorithms and prove complexity bounds for these directions.

Broader Impacts: Algorithmic DNA self-assembly is both a form of nanotechnology and a model of computation. As a computational model, algorithmic DNA self-assembly first encodes a computer program for a given computational problem into the glues of DNA tiles. The tiles then bind with each other to execute the program to produce a DNA nanostructure, which in turn encodes the desired output of the computational problem. As a nanotechnology, the goal of algorithmic DNA self-assembly is to design glues to program a set of tiles to assemble into the desired nanostructure. The PI has taught a new course this past spring quarter (spring 2010) on Algorithmic DNA Self-Assembly at the level of advanced undergraduate students and first-year graduate students. The PI will continue to teach this course on a regular basis in the next few years either as a lecture-based course or as a seminar-based course. The results which the PI will obtain from this project will be incorporated into the course. This course introduces students to research opportunities in the intersection of algorithms and nanotechnology and more generally uses science-fiction-like research in DNA self-assembly to promote multidisciplinary research and thinking by students.

Key Words: DNA self-assembly; algorithms; complexity theory; models of computation; nature-inspired computing; nanotechnology.

Self-assembly is a process by which simple objects connect with each other to form complex structures under very little external control. Given that self-assembly is very common in nature, it is almost certain that self-assembly technologies will ultimately permit precise and efficient fabrications of nanostructures. There are many kinds of self-assembly. This project chooses to focus on algorithmic DNA self-assembly with the goal of understanding self-assembly in general from programming (i.e., algorithmic) and mathematical perspectives.

Algorithmic DNA self-assembly takes advantage of the facts that the four bases of DNA (i.e., A, C, G, T) can be used to encode information and that A binds with T and C binds with G. Small molecules consisting of multiple DNA strands (i.e., more than double strands) have been designed to act as four-sided building blocks (which are called tiles) for algorithmic DNA self-assembly. Experimental work has demonstrated that these building blocks can effectively perform computation as well as assemble crystals. Some key aspects of the self-assembly process of such building blocks have already been used to formulate a fundamental mathematical model called the abstract tile assembly model. This model extends a mathematical theory of two-dimensional tilling by adding a natural mechanism to grow a structure formed by tiles. The model consists of a set of square tiles. The four sides of a tile are each associated with a glue (which is implemented as a DNA strand). A special tile in the tile set is designated as the initial seed structure. Self-assembly proceeds by starting with the initial seed structure and then gluing copies of tiles from the tile set one by one to the growing seed structure whenever the total glue binding strength between a tile and the seed structure is no less than a threshold (which is implemented as the temperature in the tube).

Under the abstract tile assembly model, algorithmic DNA self-assembly is both a form of nanotechnology and a model of computation. As a computational model, algorithmic DNA self-assembly first encodes a computer program and an input data set for a given computational problem into the glues of DNA tiles. The tiles then bind with each other through DNA complementarity to execute the program on the input data set to produce a DNA nanostructure, which in turn encodes the desired output of the computational problem. As a nanotechnology, the goal of algorithmic DNA self-assembly is to design glues to program a set of tiles to assemble into the desired nanostructure.

The project will investigate interconnected research directions in algorithmic DNA self-assembly to explore new ways (1) to minimize the cost of manufacturing the glues and tiles used to assemble a structure, (2) to minimize the amount of time needed to assemble a structure as well as the amount of defects in the assembled structure, and (3) to impose desirable structural properties on the assembly process as well as on the assembled structure. A common theme across these directions is to automate the design of DNA self-assembly systems.

The project will continue the efforts of the Principle Investigator (PI) to introduce this emerging interdisciplinary field to the theoretical computer science community by formulating research problems of interest to that community. With this project, the PI will continue to recruit members of under-represented groups into this field in particular and into computer science in general. The PI has introduced and taught a course in this field in the past two years at the level of advanced undergraduate students and first-year graduate students. This course attracted two undergraduate students from outside computer science to decide to apply to PhD programs in this field and a postdoctoral fellow in Chemistry to collaborate with the PI and undergraduate summer research students. With this project, the PI will continue to teach this course on a regular basis to attract students and researchers into this emerging interdisciplinary computer science field.