1983 — 1987 
Kannan, Ravindran 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Computational Complexity of Numerical Algorithms (Computer Research) @ CarnegieMellon University 
0.97 
1985 — 1988 
Kannan, Ravindran 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Lattice Algorithms and Their Applications to Combinatorial Optimization @ CarnegieMellon University
While integer programming problems are known to be hard (NPhard) in general, there is a great practical need to solve such problems. In the last decade or so, operations researchers have looked at integer programming problems from a computational complexity viewpoint and a polynomial time algorithm was devised for any fixed number of dimensions. The approach involved solving a welldefined problem on lattices and then applying the result to integer programs. A lattice is the set of all integer combinations of a finite set of linearly independent vectors (the finite set of vectors is called a basis of the lattice). These results indicate that a better understanding of lattices could yield important advances in solving combinatorial optimization problems. This research will concentrate on lattices and has two main aims: to devise more efficient algorithms for lattice problems, and to apply these algorithms to solve integer programming and other combinatorial optimization problems.

0.97 
1988 — 1990 
Kannan, Ravindran 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Algorithmic Geometry of Numbers @ CarnegieMellon University
The project aims to develop mathematics in the area of Algorithmic Geometry of Numbers, apply the mathematics to sequential and parallel algorithms for Integer Programming, testing and ensuring randomness of sequences and numerical integration. It is intended that some of the algorithms will be implemented.

0.97 
1990 — 1993 
Kannan, Ravindran 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Algorithms For Convex Sets @ CarnegieMellon University
The project has three parts: Efficient algorithms for random sampling from convex sets in Euclidean space using the theory of rapidly mixing Markov chains and the applications of such algorithms. Lattice relaxations of Integer Programming problems that produce better bounding procedures and related lattice questions. Strongly polynomial time algorithms for the greatest common divisor and genealizations.

0.97 
1992 — 1996 
Kannan, Ravindran 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Random Walks, Parametric Integer Programming @ CarnegieMellon University
This project will have four parts. The first part seeks to improve the running time of algorithms to compute the volumes of convex sets, to do multivariate sampling and integration. Randomized polynomial time algorithms for these problems using rapidly mixing Markov Chains have been used; some new ones will be designed that are ultimately intended to render these theoretically polynomial time bounded algorithms usable in practice. The second part considers some general results on logconcave functions that will reduce the running time of sampling according to such functions; most statistical distributions belong to this class. The third section considers some problems arising in Manufacturing where, one has to optimize (minimize)the cost of components (raw materials) subject to the (chance) constraint that one has enough components to make the probability of our being able to meet the stochastic demands high enough. The last part considers Parametric Integer Programming which arises in contexts where the constraint matrix of an integer program remains fixed and one wishes to solve the problem for various right hand side vectors. Algorithms to preprocess the constraint matrix with a parallel algorithm will be considered.

0.97 
1995 — 1999 
Kannan, Ravindran Cornuejols, Gerard Balas, Egon [⬀] Frieze, Alan (coPI) [⬀] 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Gig: Algorithms, Combinatorics & Optimization: An Interdisciplinary Ph.D. Program @ CarnegieMellon University
9509581 Balas The last half century has seen an increasing use of computers insolving the complex decision problems that arise in a modern society.The methods needed to solve many of these problems are a fusion of ideas from Mathematics, Computer Science and Operations Research, Linear Programming, Integer Programming and Combinatorial OptimizationTechniques are widely used in today's world. Problems of production, distribution, and allocation are routinely modeled in this way. New techniques drawing from developments in all three disciplines are needed to solve the ever larger problems that arise in a technologically advanced society. In addition, new areas of application emerge repeatedly. For example, the recent upsurge of activity in Computational Molecular Biology relies heavily on Discrete Mathematics to untangle the knotty sequencing problems that it throws up. The knowledge needed to solve such problems transcends the traditional boundaries of a modern university. Researchers in Mathematics, Operations Research and Computer Science Departments often find themselves working on similar problems. On the other hand the idea of training graduate students simultaneously in all three areas has been slow to get off the ground. Carnegie Mellon recognized this several years ago. Using it's internationally recognized strengths in all three areas it responded by setting up the Ph. D. program in Algorithms, Combinatorics and Optimization. A unique feature of the program is that students are given a thorough grounding in the foundations of all three areas before they embark on their research. Now nearly 30 students have taken part in the program. The quality of the students has been excellent and the first crop of graduates have taken up positions in major universities and research laboratories.The program has inspired other institutions to provide similar courses.The money from this grant will be used to support graduate students and to provide t hem with an environment in which they can acquire knowledge and research skills in all three areas.

0.97 
1996 — 1997 
Kannan, Ravindran 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Fast Randomized Algorithms For Optimization and Other Applications of Geometric Random Walks @ CarnegieMellon University
This is a companion project with CCR9528973 (entitled ``Optimization and Learning over Convex Sets'') and is an award under the Software Capitalization Program. The project's goal is to upgrade and update software that had been produced. These upgrades and updates are based on algorithms developed under support of CCR9208597. The software is for executing random walks that produce a sample from certain multivariate probability distributions. An update of the software involves simply changing the ``number of steps'' parameter in the random walk. Applications of this discrete probabilistic software (i) to contingency tables and (ii) to the membership oracles for optimization over convex sets, are investigated. With good planned dissemination (for example, on the world wideweb)and well thoughtout testing, other applications of this software are anticipated. ***

0.97 
1996 — 2000 
Kannan, Ravindran 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Optimization and Learning Over Convex Sets 
1 
1999 — 2003 
Kannan, Ravindran 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Randomized Algorithms For Matricies, Graphs, and Convex Sets
This project is focused on two areas. The first is applying techniques developed for randomized algorithms to traditional matrix problems that have to be solved for very large matrices. In particular, the problem of finding an approximation to a given matrix having a fixed rank. If the matrix is the adjacency matrix of a graph, connection has been developed between such approximations and certain partitions of the vertex set of the graph. The second area is approximation algorithms for convex sets.

1 
2000 — 2004 
Kannan, Ravindran Coifman, Ronald (coPI) [⬀] Howe, Roger (coPI) [⬀] Jones, Peter [⬀] Mandelbrot, Benoit 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Yale Vigre Program in Mathematics and Applied Mathematics
Abstract:
The Yale VIGRE program will build on the strong base of an existing interdisciplinary and substantially vertically integrated program by creating vertically integrated project groups (VPGs) to carry out defined research and development agendas in pure and applied mathematics, curriculum development, education and outreach. VIGRE at Yale will support undergraduates, graduate students and postdocs working together, with the guidance of faculty, for a diverse and flexible set of goals. It will provide undergraduates with a new range of opportunities to encounter mathematics in a more immediate and vital way than traditional coursework. It will broaden and deepen graduate training, and provide for shortened length of study. It will provide students and postdocs with opportunities to deepen their understanding of and expertise in teaching. It will develop and disseminate curricular materials for courses embodying new mathematical ideas, and new approaches to traditional topics.
This program is being jointly funded by the Division of Mathematical Sciences and the Office of Multidisciplinary Activities from the Directorate of Mathematical and Physical Sciences.

1 
2000 — 2003 
Kannan, Ravindran Kao, MingYang [⬀] 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Computer Science Approaches to Finance Problems: Computational Complexity and Efficient Algorithms
PI: MingYang 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 tradeoffs 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 shortterm predictability of stock markets using agentbased 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 longterm 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.

1 
2003 — 2010 
Kannan, Ravindran Feigenbaum, Joan [⬀] Silberschatz, Abraham (coPI) [⬀] 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Information Technology Research (Itr): Sensitive Information in a Wired World
Increasing use of computers and networks in business, government, recreation, and almost all aspects of daily life has led to a proliferation of sensitive data (i.e., data that, if used improperly, can harm data subjects or other relevant parties), and concern about the ownership, control, privacy, and accuracy of these data has become a top priority. Despite significant technical accomplishments in relevant research fields (e.g., cryptology and security, database systems, and data mining), there is no comprehensive, endtoend technological infrastructure for handling sensitive data over the entire course of their lifetime, nor is there even widespread social agreement about the rights and responsibilities of major stakeholders in our dataintensive, networked world.
This project is a multiinstitutional, multidisciplinary, multimodal project that looks comprehensively at sensitive data in a networked world. There are two main academic centers of activity (Yale and Stanford), three smallerscale academic participants (Stevens Institute of Technology, NYU, and the University of New Mexico), and substantial participation by nonacademic partners, including technology companies, (IBM, HP, and Microsoft), representatives of user communities (Citigroup, NIH, Yale Center for Medical Informatics, the Census Bureau, and the Secret Service), and DCbased policy organizations (The Center for Democracy and Technology and The Electronic Privacy Information Center).
A major technical theme of the project is privacypreserving data mining, and, more generally, techniques for meeting the potentially conflicting goals of respecting individual rights and allowing law enforcement and other legitimate organizations to collect and mine massive data sets. Other technical agenda items include (1) accessibility and reliability of distributed data (2) operating on encrypted databases, (3) remote control of data, (4) repelling hostile data, and (5) auditability of datamanagement systems. Because these technical goals are affected by lack of agreement about the meanings of basic terms, most notably "privacy," a major goal of the project is the development of a conceptual framework for the study of rights, responsibilities, and public policies focused on sensitivedata handling. This part of the project incorporates the notion of "contextual integrity," which considers both the context and the content of data sets in assessing sensitivity.
Projected outcomes of the project include a next generation of technology for handling sensitive information that is qualitatively better than the current generation's and an effective conceptual framework for policy making and philosophical inquiry into the rights and responsibilities of data subjects, data owners, and data users.

1 
2003 — 2007 
Kannan, Ravindran 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Collaborative Research: Itr: Models, Algorithms and Analyses For Clustering Data
The unprecedented explosion in the volume of readily accessible data in recent years, although highly desirable, comes at a heavy price  it is now considerably more difficult to locate the answer to a specific question, or to find patterns and correlations that are central to a phenomenon. The PI's propose to study generalpurpose clustering as a solution to the problem of locating relevant information and organizing it in an intelligible way.
The proposal falls into two tracks. The first track is to develop measures and criteria that accurately re the quality of a clustering. The PI's have initiated work in this direction, and plan to build a theory of clustering criteria firmly grounded in the intuition of practitioners.
The second track is the design of efficient algorithms to find nearoptimal clustering under the right measures. The PI's propose to develop algorithms based on the socalled "spectral methods" and other techniques. They plan to make them efficient by the use of random (nonuniform) sampling. The PI's also plan to implement some of the algorithms and empirically evaluate them.
The PI's propose to ensure that any positive impact from their research is maximized by (a) widely disseminating the results via conferences and also by inviting other researchers to discuss the ideas, (b) by making the preliminary implementations of clustering algorithms available.

1 
2003 — 2007 
Kannan, Ravindran 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Sampling On the Fly From Massive Data
The sizes of problems that need to be solved in modern applications have grown enormously. Sampling to draw a (small) subset of the data to store in main memory and process in detail is thus a natural alternative to computing on the entire data. The project addresses the questions of how well the answers from a sample approximates answers to the full problem for many optimization problems that go under the name of Constraint Satisfaction Problems. The project also considers problems where the input data consists of matrices or higher dimensional arrays. Here adaptive sampling (where the probability of sampling a piece of the data depends on its relative importance) has been successfully used by the PI and others recently. The existing results are to be improved. Adaptive sampling calls for making more than one pass through the data. The project will study models of computation, where the number of passes is measured as an important resource. This is expected to contribute to the discussion of models to handle large data.
A third part of the proposal is to continue the PI's study of rapidly mixing Markov Chains, both by developing new general techniques and applying to specific problems like the computation of volumes of convex sets.
Broader Impact: The research is expected to have broad impact since the processing of massive data via sampling is of enormous importance in modern computing. The PI teaches specialized courses at Yale and hopes to disseminate the results of the research to students through the courses.

1 
2004 — 2008 
Kannan, Ravindran Kalai, Gil (coPI) [⬀] 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Three Topics in Combinatorics With Relations to Theoretical Computer Science
We intend to study three topics in combinatorics which are related to theoretical computer science. We will study the diameter problem for graphs of polytopes aiming at a polynomial upper bound, and also try to find versions of the simplex algorithm with subexponential worst case behavior. We will study Boolean functions, their Fourier transform and how it relates to questions in probability and complexity. We will also try to find general methods to relate the solution of a positive integer programming problem and its linear programming relaxation.
Combinatorics have now become the central mathematical discipline in theoretical computer science (and various applied areas of computer science as well). The role of combinatorics in computer science today is quite similar to the role of logic in the early days of computation. Problems from theoretical computer science enriched and enforced combinatorial thinking and areas which were regarded as having clear intellectual merit have gained surprising reallife applications. Linear programming and the simplex algorithm are among the most important applications of computers and in our earlier work as well as the planned research. We intend to study fundamental questions concerning linear programming. Another area of our research, the Fourier analysis of Boolean functions is a relatively new area which we helped to develop in the past. In view of the importance of Fourier analysis in other areas we should not have been surprised to see its recent applications in combinatorics and complexity theory and we intend to explore further connections.

1 
2006 — 2010 
Kannan, Ravindran Spielman, Daniel [⬀] 
N/AActivity Code Description: No activity code was retrieved: click on the grant title for more information 
Spectral Methods: Algorithms and Applications
Abstract 
Problems in many areas where the input data is a matrix have been tackled by Spectral Methods which use lowrank approximations to the input matrix. In the important application area of Clustering, only known proofs that the methods succeed have to make the unrealistic assumption that all entries of the matrix are statistically independent. This research removes this important impediment to the wider use of the method by developing the theory and algorithms that work under limited independence, a much more realistic assumption. To illustrate, in one example  documentterm matrices  this research assumes only that the documents are statistically independent, not the terms in each document.
The research also generalize the methods developed for limited independence to deal with matrixvalued random variables which are of interest in several areas and to date have no substantial work on them. The PI and supported students will extend the applications of spectrallike methods to tensors  multidimensional arrays. It is expected that the research here will be one of the key bridges between theory and practice in this area, thus leading to a broad transfer of theoretical developments into practice in time.

1 