Steven Homer - US grants

This project is aimed at an improved understanding of properties and structure of complete sets for several, extensively studied complexity classes. In particular, complete sets under strong polynomial reductions and the existence of p-isomorphisms between these sets are to be studied. In addition, a study will be made of honest polynomial reducibilities and minimal sets for these reducibilities. The goal is to relate the structure of polynomial reducibilities and open problems in complexity theory to methods and results of recursion theory. The relationship between the existence of minimal sets with respect to honest polynomial reductions and the P=? NP problem will be studied.

With the increased use of automated reasoning systems and the proliferation of parallel machines, the need for research in parallel automated reasoning was never more evident. Coarse grain parallel theorem provers have been developed which demonstrate linear speed-up for small to medium scale problems; however, fine grain provers for very large scale problems have yet to be developed. In this work a SIMD parallel automated reasoning system will be designed based upon the clause graph (or connection graph) model. This system will be implemented on the Connection Machine model CM-2 and will be applied to a number of problems in group theory and combinatorial geometry. In addition, parallel algorithms will be developed for computing and analyzing the spectra of clause graphs.

This research attempts to gain a better understanding of the intrinsic properties of complete sets for many natural complexity classes. The research will explore how the complexity-theoretic properties of complete sets are affected by the strength of the reducibilities defining them, and the relationships between these properties and the central problems in complexity theory. One such property is immunity, which examines whether all complete problems have larger subproblems which are easier to solve than the full problem. This research bears upon the existence of certain types of approximations to these intractable sets. Another area of study is the strength of efficient reductions between pairs of complete sets and the possibility of reductions from complete sets to sparse sets or other sets with a particular structure. The relationships between the complexity-theoretic results in these areas and other current research problems such as the isomorphism problem and the existence of certain types of one-way functions are a central focus of this work.

This award is for the development of an interdisciplinary curriculum for undergraduate students in computer science, the natural sciences and engineering. The curriculum will focus on massively parallel computing and will use Boston University's 64-node CM-5. The courses will be project- oriented emphasizing direct experience with computational problem-solving in the sciences and with programming in a massively parallel environement. This award is for the development of an interdisciplinary curriculum for undergraduate students in computer science, the natural sciences and engineering. The six project oriented courses that are proposed: one in fundamental methods and five in advanced computational topics, will emphasize direct experience with computational problem- solving in the sciences and with programming in a massively parallel environment. The results of the curriculum and materials development will be disseminated through summer workshops, publications, and presentations at professional meetings.

This award supports a group of three U.S. computer scientists coordinated by Professor Steven Homer of Boston University to collaborate with Professor Peter van Emde Boas and others of the Department of Mathematics and Computer Science of the University of Amsterdam, the Netherlands. Their research will focus on several current topics in the theory of computation, including structural complexity theory and Kolmogorov complexity theory. The planned collaboration will be expedited by several reciprocal working meetings among the participants that will give opportunities to local young researchers and particularly graduate students to benefit from participation in the discussions. This research lies on the boundary between mathematics and computer science. The various research partnerships among the seven participants should yield significant results in several central areas of complexity theory. The complementary expertise contributed by the U.S. and Dutch participants has the potential to contribute insights and connections which would not emerge without the cooperative interactions.

PI: Steven Homer
Proposal Number: 9988310
Institution: Boston University

Abstract

Two complementary areas of computational complexity theory will be studied. The first is the complexity of quantum computing, a project that my colleagues and I have begun work on during the past two years. To this point two projects have been completed, both concern finding lower bounds for classes of quantum computations. I propose to continue to explore the power of quantum computation and try to obtain both lower and upper bounds by relating quantum classes to classical complexity theory. The second area concerns the study of the complexity theory of natural combinatorial functions in PSPACE. Here the goal is to make use of the extensions of the polynomial hierarchy, which were defined and explicated in an earlier paper on the hyperpolynomial hierarchy. Tools such as the NP-jump and the methods of Toda's theorem will be studied and extended in order to classify counting problems and other natural complex problems in PSPACE. We intend to explore this new framework for the classification of optimization problems and to study the relationship between older notion such as alternation and the extended polynomial hierarchies which we have defined.

Thomas Keyes, John Straub, and Steven Homer of Boston University are supported by the Chemistry Division and the Division of Materials Research under the Information Technology Research program to develop and apply algorithms for multiple time scale simulations of supercooled liquids and biomolecules. Three different algorithms are being developed for acceleration of transitions between different local minima. All three depend on methods for identifying local minima, transition barriers, and pathways in complicated molecular systems.

Biologically interesting processes may be characterized by slow transitions between dissimilar molecular configurations. Dynamical processes on a much faster time scale occur rapidly within each of the configurations and during the slow transition between the two configurations. A simultaneous accurate accounting of both slow and fast processes represents a significant challenge to computational chemists and materials scientists. This work merges techniques for mathematically describing landscapes near a local minimum with information technology methods to allow for modeling of such slow events. The research is strongly coupled to educational activities that are designed to expose young researchers to the multiple time scale problem.

Mobile phones are in the midst of a dramatic transformation; they are becoming highly powerful sensor-rich software-controlled computing and communication devices. These "softphones" are increasingly entrusted with maintaining users' electronic identity, calendars, social networks, and even bank accounts. However, the vast increases in the flexibility of softphones comes with equally large security issues and opportunities, some of which we are only beginning to understand.

This project studies the new threats and promises of softphones, and focuses on identifying, understanding, and mitigating new security risks. Two broad risk categories are addressed: threats to individual users (such as user privacy or personal finances), and threats to the entire communication system (such as disruptions to emergency services). The project ultimately aims to understand how security problems associated with softphones and their networks are different from those of traditional computers and networks, and how to harness the unique capabilities of softphones for improved security.

The research is being conducted by a broad and diverse team of nine senior investigators, in collaboration with international industry and academic partners, under the aegis of the RISCS Center at Boston University. The project is striving for wide impact through a public seminar series, multiple workshops, course development in phone security across all levels (including honors courses), and cross-disciplinary training of graduate and undergraduate students

The project's successful conclusion will deliver an essential and timely understanding of how to secure the mobile phone infrastructure that already manages many intimate aspects of our lives.

The era of performance scaling by increasing the performance of
individual processors is over, having been replaced by the era of
massive parallelism via multiple cores. Amdahl's law tells us that
our ability to parallelize computation is limited by the inherently
sequential portion of a computation. This unfortunate combination
of facts paints a bleak picture for the future of scalable software.
This work explores a radical new approach to parallelism with the
potential to bypass Amdahl's Law. The approach used involves making
informed predictions about computation likely to happen in the
future, proactively executing likely computations in parallel with
the actual computation, and then "jumping forward in time" if the
actual execution stumbles upon any of the predicted computations
that have already been completed. This research touches many areas
within Computer Science, i.e., architecture, compilers, machine learning,
systems, and theory. Additionally, exploiting massively parallel
computation will produce immediate returns in multiple scientific
fields that rely on computation. The research here provides an
approach to speedup on such real-world problems.

The approach used in this research views computational execution
as moving a system through the enormously high dimensional space
represented by its registers and memory of a conventional single-threaded
processor. It uses machine learning algorithms to observe execution
patterns to make predictions about likely future states of the
computation. Based on these predictions, the system launches
potentially large numbers of speculative threads to execute from
these likely computations, while the actual computation proceeds
serially. At strategically chosen points, the main computation
queries the speculative executions to determine if any of the
completed computation is useful; if it is, the main thread uses the
speculative computation to immediately begin execution where the
speculative computation left off, achieving a speed-up over the
serial execution. This approach has the potential to be infinitely
scalable: the more cores, memory, and communication bandwidth
available, the greater the potential for performance improvement.
The approach also scales across programs -- if the program running
today happens upon a state encountered by a program running yesterday,
the program can reuse yesterday's computation.