Chronological list of talks in the 2000-2001 academic year
September 18, 2000, 12:15pm
Speaker: Joerg Rothe , Friedrich-Schiller-Universit\"at Jena, Germany
Topic: Strongly Noninvertible Associative One-Way Functions
Rabi, Rivest, and Sherman developed cryptographic protocols for secret-key agreement and digital signatures. Their protocols use ``strongly noninvertible,'' associative one-way functions as their key building blocks. Strong noninvertibility alters the standard notion of noninvertibility. Informally speaking, a 2-ary function is strongly noninvertible if, given an output of the function and one of its two arguments, it is hard to find an argument that together with the given argument is mapped to the given output. In this talk, we survey the progress of results on strongly noninvertible, associative one-way functions. The main focus is on two recent papers. Hemaspaandra and Rothe [Journal of Computer and System Sciences, 1999] show that from any given one-way function one can construct a strongly noninvertible, total, commutative, associative one-way function. This result solves an open question of Rabi and Sherman [Information Processing Letters, 1997]. Rabi and Sherman's definition of strong noninvertibility has a small twist (``respecting the argument given'') that precludes direct attacks against the cryptographic protocols. Hemaspaandra, Pasanen, and Rothe [Univ. of Rochester TR-737, 2000] show that this small twist has a large, unexpected consequence: Unless P = NP, some strongly noninvertible functions are invertible.
October 2, 2000, 12:15pm
Speaker: The Singing UR-CS Theory Graduate Students
Topic: Subtractive Reductions
The latest pop singing sensations will serenade us with their presentation of and comments on the paper ``Subtractive Reductions'' by Durand, Hermann, and Kolaitis, from the proceedings of MFCS 2000 (August/September 2000). Among other things, this paper proves the closure of #P (and even #.\Pi_k^p) under the newly defined notion of subtractive reductions. How is this possible in light of the Ogihara-Hemaspaandra results on the (conditional) impossibility of subtracting even one from #P functions? Find out, melodiously, on October 2nd.
October 16, 2000, 12:15pm
Speaker: Harald Hempel, Friedrich-Schiller-Universit\"at Jena, Germany
Topic: Query Order
As everyone has certainly experienced, order matters in everyday live. So does the order in which we access information sources. In this talk we will find out whether this everyday-life intuition carries over into complexity theory. A good modell for information sources are oracles. So during this talk we will answer questions like: Does the order in which an oracle machine queries two oracles (being from two different complexity classes) matter? Is it better to query the "harder" oracle first or last? Does an "easy" second oracle give any additional computation power at all? The talk will review results on query order in the polynomial hierarchy and the boolean hierarchy.
October 30, 2000, 12:15pm
Speaker: Christopher Homan
Topic: Creating Optimally Unambiguous Strong, Total, Associative, One-way Functions: Part I
Strong, total, associative, one-way functions form the basis of a cryptographic protocol for 2-party secret key agreement. Thanks to this protocol, you can now securely share the same exact bits of information with your best friend, assuming that such functions exist. Fortunately, Hemaspaandra and Rothe showed they are as likely to exist as standard one-way functions are. There is a cost, however: no such function can be one-to-one. If fact---as I showed in my area paper---no such function can by c-to-one for any constant c. As a result, you may be left with a number of choices as to what the bits you share actually mean. For these functions to be useful, then, we need to at least be able to guarantee that the number of choices grows *VERY* slowly.
In this talk, I will present my recent efforts to construct such a function whose worst-case ambiguity is as close as possible to the best known lower bound.
November 6, 2000, 12:15pm
Speaker: Christopher Homan
Topic: Creating Optimally Unambiguous Strong, Total, Associative, One-way Functions: Part II
Part II of the talk started on October 30th. See the October 30th entry above for the abstract.
November 20, 2000, 12:15pm
Speaker: Yin-He Cheng
Topic: Datamining methods used in interpreting pattens of
gene expression
Clustering and classificatin are data mining methods got great use in medical analysis based on gene expression monitoring by DNA microarrays. In this talk a clustering techique self-organizing map will be introduced, which is particularly well suited for recognizing and classifying features in complex, multidimensional data, such as gene expression data. There are also many other methods used in this area, you will also got some flavour of them. Then a paper on Molecular Classificatin of cancer--Class Discovery and Class Prediction by Gene Expression Monitoring will be introduced. this paper given a good example of using SOM in gene expression analysis, which also give us the dataset we are working on for the CAMDA'00. At the end I will talk a little what we are doing for the CAMDA'00, and the result we got so far.
December 4, 2000, 12:15pm (Final Theory Seminar of the Fall Term)
Speaker: Alina Beygelzimer
Topic: Extracting Randomness from Weak Random Sources
Conceivable physical sources of randomness possess only weak random properties (i.e. have dependencies and biases, rather than being uniformly distributed). At the same time, when randomness is used in computation, it is modeled as an ideal stream of truly random bits. This talk will present several results in the direction of bridging this gap between weak (realistic) and perfect (useful) sources of randomness. First, several impossibility results will be presented ([CG88]) stating that deterministic extraction is not possible (in a certain sense). Then we turn to a discussion of extractors. Loosely speaking, extractors are functions that extract (almost) uniform bits from somewhat random distributions, using a small amount of additional randomness. A handful of papers have been devoted to explicit constructions of extractors. Recently Trevisan showed that, rather surprisingly, certain pseudorandom generators, when properly viewed, ARE already good extractors! (in fact, they are better than previously known explicit constructions). We sketch the construction of Impagliazzo-Wigderson generator, and show why it is a good randomness extractor. We also present Trevisan's second (simpler) construction based on a modification of Nisan-Wigderson generator. Clearly, extractors that use a short (logarithmic) seed suffice for running randomized algorithms with only a weak random source. However, in some cases, randomness is fundamentally required (e.g. consider probabilistic encryption). Since deterministic extraction does not work for every source with a given min-entropy (due to the impossibility results above), it is natural to try to provide some characterization of distributions that allow an efficient deterministic extraction (without the help of additional random bits). A recent paper by Trevisan and Vadhan proves several interesting results in this direction, and identifies a large natural family of distributions which have deterministic extractors. The seminar will be mainly based on the results from the following papers: [Tre99] L. Trevisan. Construction of extractors using pseudo-random generators, STOC99. [TV00] L. Trevisan and S. Vadhan. Extracting Randomness from Samplable Distributions, FOCS00. [CG88] B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal of Computing, 17(2): 230-261, 1988.
January 29, 2001, 12:15pm
Speaker: Chris Homan
Topic: Web Archaeology
Web Archaeology is the discovery of useful or interesting structure in the World Wide Web. I will describe recent applications that use the graphical structure of the Web to improve search engine results. I will also describe the process of acquiring Web data and storing it in a way that facilitates large-scale computation. Finally, I will discuss some surprising results about the structure of the Web discovered during my summer internship at Compaq SRC.
February 5, 2001, 12:15pm
Speaker: Joel Seiferas
Topic: Nondeterministic Time Hierarchy Theorem
Consider nondeterministic computation. When is time T enough larger than T' so that more can be done within time T than within time T'? Diagonalization seems to require an exponential difference, but T(n) just slightly larger than T'(n+1) turns out to be enough. Similar results hold for space. We will look back at Zak's version of the argument for these results.
February 19, 2001, 12:15pm
Speaker: Tao Li
Topic: Instruction Balance, Energy Consumption and Program Performance
(joint work with Chen Ding)
A computer processor consists of multiple components such as functional units, cache and main memory. At each moment of execution, a program may have a varied amount of work for each component. Recent research has exploited this imbalance to save energy by slowing the components that have a lower load. Symmetrical to reconfiguring hardware is reorganizing software. For each program segment, we can alter its demands for different components by reordering program instructions. In other words, we can change the balance of program loads in different parts of a program. This paper explores the theoretical lower bound of the energy consumption assuming that both a program and a machine are fully adjustable. It shows that a program with constant load balances always consumes less power than the same program with uneven balances. In addition, the paper examines the relation between energy consumption and program performance. It shows that as far as program reordering is concerned, reducing power is a more complex problem than improving performance.
March 19, 2001, 12:15pm
Speaker: Marius Zimand, Towson University
Topic: List Decoding of Error-Correcting Codes
List decoding for an error-correcting code is the task of finding the list of all codewords within some distance d from the input word. We'd like to do this in poly time and for d as big as possible. I will show a result of Madhu Sudan that describes a particular error-correcting code in which list decoding is possible for distances just slightly less than half the length of the input word. I will also present some applications in complexity theory.
April 2, 2001, 12:15pm
Speaker: Ioan Macarie, Vanteon Corp.
Topic: The equivalence between space-bounded nondeterministic
computation and one-sided-error computation
Nondeterministic Turing machines can be viewed as probabilistic machines with errors that are one-sided but not significantly bounded. We show how to transform such a machine to an equivalent one that does have a "good" one-sided error bound (more than 1/2 for example) at absolutely no cost in either space usage or storage-tape alphabet. This improves a result of Gill (1977) where the space of the one-sided error probabilistic machine was roughly twice the space of the nondeterministic machine. In models of computation where the storage-tape alphabet is not bounded Gill's space penalty is considered insignificant. However the difference is visible when we work with more refined space models: for example, in the world of multihead finite state automata doubling the space means doubling the number of heads, which is not an insignificant resource anymore. It follows from our transformation that we have exactly the same space-complexity classes and hierarchy for bounded one-sided error probabilistic computation that we have for nondeterministic computation (at least when the spaces are "constructible"). Similarly we have the same number of heads complexity classes and hierarchy for bounded-one-sided-error probabilistic multihead finite automata as for nondeterministic ones. This main part of the talk is based on a joint paper with Joel Seiferas which appeared in IPL 72 (1999).
April 16, 2001, 12:15pm
Speaker: Pavan Aduri, Department of Computer Science,
University at Buffalo
Topic: Separation of NP-completeness notions
Lutz and Mayordomo using the hypothesis "p-measure of NP is not zero" proved that 3-truth-table completeness for NP is different from many-one completeness. Ambos-Spies and Bentzien extended this result significantly. They used an hypothesis of resource-bounded category theory that is weaker than the measure hypothesis to separate nearly all NP-completeness notions for bounded truth-table reducibilities. However the question about whether Turing completeness is different from truth-table completeness in NP remained open. In this talk we introduce a new hypothesis, different from measure and genericity hypotheses, and prove from this hypothesis that Turing completeness is different from truth-table completeness in NP. Using a weaker hypothesis we prove that Turing and many-one completeness notions differ in NP. This is a joint work with Alan Selman.
April 30, 2001, 12:15pm (Final Theory Seminar of the Spring Term)
Speaker: Jason Eisner
Topic: Complexity Results for Optimality Theory