Boston University Computer Science Dept.
Theory Seminar page

The theory group generally holds a weekly seminar during the semesters. Speakers from Computer Science and other related areas speak about their own work or present interesting papers of theoretical interest. The usual timing is Friday 3-4pm and usually its in MCS135 (Computer Science Department).
For directions, go here.

Next  Talk :

Spring 2007: The next talk is on May 9^th by Bill Gasarch from University of Maryland.
Usual venue: MCS135 at 2:00 pm.

Other  Announcements:

The tentative schedule for the this semester is given below.

• January 26 - Ben Hescott
  Nonuniform Completeness and Nondeterministic Incompleteness
  Abstract: In this proposal we will consider two different types of reductions, nonuniform many-one reductions, reductions computable with small circuits, and nondeterministic reductions, supposedly infeasible reductions.
  Recently, Hitchcock and Pavan showed that for NEXP, and under a reasonable hypothesis NP, many-one complete sets are also complete with length-increasing nonuniform reductions. We continue their work, we reduce the amount of advice necessary, consider weaker hypotheses, and give evidence that these results may be optimal. We begin one of the first investigation into this type of reduction on common complexity classes and compare it to better known reductions.
  We also show that under a reasonable hypothesis there are sets within PSPACE which are complete under nondeterministic polynomial time reductions, but not under deterministic polynomial time reductions. We will consider extensions to higher levels of the polynomial hierarchy and methods to weaken the given hypothesis.
  
• February 9 - Steve Homer
  Non-uniform reductions and exponential time completeness
  Abstract: Efficient non-uniform reductions are defined and results relating these reductions to the standard uniform polynomial time reductions are discussed. We focus on exponential time,
  1. proving a result relating uniform and non-uniform EXP complete sets and
  2. proving that settling a natural open problem about complete sets in EXP would imply a new separation of complexity classes.
  
  This is joint work with Harry Buhrman, Ben Hescott and Leen Torrenvliet.
  
• March 16 - Amitabha Roy
  Fagin's Theorem
  Abstract: In the standard model of random graphs, a property is said to hold almost surely (respectively almost never) if the proportion of labelled graphs on n vertices having this property converges to 1 (respectively 0).
  For example, a property that there is a triangle in the graph holds almost surely. What properties have the characteristic that they hold almost surely or almost never ?
  Fagin's theorem gives a characterization that brings logic into the picture:If A is any property of graphs that can be expressed in first order logic, then such a property holds almost surely or almost never. Following Joel Spencer's monograph "The Strange Logic of Random Graph", I will give a proof of this theorem.
  
• March 2 - Gene Itkis
  Flat Holonomies on Automata Networks
  Abstract: We consider asynchronous dynamic networks of identical finite (independent of the network size) automata. A useful data structure on such networks is centered slope: a partial orientation of its edges, which is
  • straight: has null holonomy (the difference between the number of up and down edges in each cycle)
  • centered: has a unique node with no down edges
  Using such centered slope, any computational task can be efficiently implemented with self-stabilization and synchronization. There are (interdependent) self-stabilizing asynchronous finite automata protocols jointly assuring centered slope. Such protocols may vary in assorted efficiency parameters and it is desirable to have each replaceable with any alternative responsible for a simple limited task. This work presents an efficient reduction of any computational task to any set of such protocols compliant with our interface conditions, bringing major benefits in efficiency and simplicity.
  Joint work with Leonid A. Levin.
  
• March 23 - Bhavana Kanakurthi
  Private simultaneous message protocols and Randomizing polynomials
  Abstract: Motivated by questions in the domain of information-theoretic secure multi-party computation, Ishai-Kushilevitz (FOCS 2000) introduced the notion of randomizing polynomials. One of their interesting results is that degree-3 polynomials are sufficient to randomize any function that has a branching program representation.
  Many of the techniques used to construct randomizing polynomials are implicit in their earlier work on PSM protocols (IK97). In the first part of the talk, I will discuss those techniques. In the second part of the talk, I will introduce the notion of randomizing polynomials and discuss the above result. If time permits, I will discuss the application to multiparty computation. The talk will be self contained.
  
• March 30 - David Charlton
  Finding a Max-Weight Triangle in Sub-Cubic Time
  Abstract: Given a node-weighted graph, how quickly can we find a triangle with maximum weight, or a triangle with a weight in some desired range? We present a recent result of Vassilevska and Williams giving the first truly sub-cubic algorithm (roughly n^2.7, improving the former bound of (n³ / log n). The dependence on the bits of precision required is linear, as opposed to some earlier approaches which were exponential. We will discuss some of the applications of this algorithm, as well as remaining open questions.
  
• April 6 - Arthur Chou (Clark University)
  Turing meets Riemann: Complexity Theory of Two-Dimensional Regions
  Abstract: This talk will survey some complexity issues involved in computing two-dimensional sets on the plane, based the model of Turing machine with oracles; that is, the bit-complexity model. This approach dated back to Turing himself and an area in recursion theory called recursive analysis, and is based on the work of Ko and Friedman in the 80's on real functions. We will first introduce the various models and explore their relationships, and then discuss some fundamental results such as Riemann Mapping Theorem, computing distance functions and path finding. Some computational geometry problems will also be treated in this setting. This is a joint work with Keri Ko.
  
• April 20 - Ilir Capuni (Boston University)
  Cryptography on weak BSS model of computation
  Abstract: Modern cryptography is based on the classical model of computing where data are represented as sequences of bits and performing operations such as ANDs and ORs. One - way functions are the weakest assumptions from which secure cryptographic primitives are constructed. In this model, the existence of one-way functions has not been established yet.
  In contrast, there are many algebraic functions that are easy to compute and impossible to invert. One such function is the function that triples an angle since trisection of an arbitrary angle is impossible using a straightedge and a compass with infinite precision.
  In this talk, we will first define a suitable computational model and then we will explore which cryptographic paradigms could be constructed using such "algebraic one-way functions".
  
• April 27 - Nenad Dedic (Boston University)
  On Trading Secret Random Bits for Public Ones
  Abstract: We study the question of when a one-way function can be used securely with fewer input bits than prescribed. We show that by using public randomness it is possible to use a regular one-way function (i.e. a function in which every output has the same number of preimages) with only as much secret randomness as the entropy in the function's the output. Moreover, we show that the use of public randomness is essential as the total amount of randomness required for using a one-way function cannot be reduced using black-box techniques (even for regular functions).
  Unfortunately, this appealing approach is not possible for general one-way functions. We prove that for general one-way functions, secret randomness cannot be replaced with public randomness using black-box reductions.
  As an application of this approach we show a large class of one-way functions other than permutations that can be used to build pseudorandom generators with linear-length seeds: regular ones with "known" high degeneracy. When counting only secret randomness, this forms a first general construction of pseudorandom generators from one-way functions where the input length of the generator is sub-linear in that of the one-way function.
  Joint work with Danny Harnik (Technion) and Leonid Reyzin.
  
• May 9 - Bill Gasarch (University of Maryland)
  The Multiparty Communication Complexity of Exact-T
  Abstract: Assume that Alice, Bob, and Carol all have numbers on their foreheads, which we denote a,b,c. Note that Alice sees only b,c. Bob sees only a,c. Carol sees only a,b. The numbers a,b,c are all n-bits long so the numbers themselves are <= 2ⁿ. They want to know if a+b+c=2ⁿ.
  Alice COULD just say HEY, BOB, b is 100011001, which would take n bits. Can they do better than this?
  It was shown in 1983 that
  • They can determine if a+b+c = 2ⁿ with O(√n) bits.
  • The problem CANNOT be done with a constant number of bits.
  WE show the following
  • if there are k players and they all have numbers on foreheads then it can be done with O(n^1/(k-1)) bits.
  • In the 3 player case it requires Ω(log log n).
  • We have some empirical studies as well in the 3-player case.
  
  This is based on a joint work with Beigel and Glenn.
  

• Jan 20 - Peter Gacs
• Jan 27 - David Charlton
• Feb 10 - John Rachlin
• Feb 17 - Marshall van Alstyne
• Feb 24 - Kyle Burke
• March 3 - Ben Hescott
• March 17 - Matthew Cook
• March 22 - Shanghua Teng
• March 24 - Debajyoti Bera
• March 31 - Fred Green
• April 7 - Ari Trachtenberg
• April 14 - Natalia Luckyanova
• April 21 - Peter Fejer
• April 24 - Jonathan Katz
• April 28 - Lane Hemaspaandra

• October 28 - Steve Homer
  Redundancy in Complete Sets
  Abstract: About a year ago it was shown (by C. Glasser, A. Pavan, A. Selman, and L. Zhang) that many classes of many-one complete sets (including the NP-complete sets) are all many-one autoreducible.
  Since then there have have been several related results concerning self-reducibility of complete sets and other similar notions. These newer results are by Faliscewski and Ogihara and by the original group mentioned above.
  Two examples are:
  If P is not NP then there is an NP-complete set which is not length decreasing self reducible.
  Any NP complete set can be set split into 2 sets such that each of the two is polynomially (many-one) equivalent to the first.
  These results, as well as several open problems, will be discussed.
  
• October 21 - Amitabha Roy
  Bounds on an exponential sum arising in boolean circuit complexity
  Abstract: In this talk, we prove exponentially decreasing upper bounds on the correlation between the following functions defined over n boolean variables:
  • the MOD_m function which is true exactly when the number of variables set to 1 is congruent to 0 modulo m
  • any degree d polynomial defined over Z_q (ring of integers modulo q) where we assume that m and q are relatively prime. The degree d can be any integer up to a constant times log n, where the constant depends on m and q.
  This generalizes a result of J. Bourgain,Estimation of certain exponential sums arising in complexity theory( Comptes Rendus Mathematique, C.R. Acad. Sci. Paris, Ser. I 340 (2005)) 627-631, which proves the same result when q is odd.
  Before Bourgain's result, such bounds were known for the special cases when m=2, q=3, d=2 (due to Green) or when the polynomial is symmetric (due to Cai, Green, Thierauf). Sub-exponential bounds were obtained by Alon and Beigel.
  As a consequence of Bourgain's result and our generalization, the following result in circuit complexity holds:
  Let C be a circuit with a threshold gate at the top, followed by a layer of MOD_q gates in the middle and a layer of AND gates of fan-in at most d. If C computes MOD_m then C has exponential size in the number of inputs. Many open problems will be presented.
  Joint work with Fred Green and Howard Straubing.Paper appears as Bounds on an exponential sum arising in boolean circuit complexity by Green, Roy, Straubing, Comptes Rendus Mathematique, C.R. Acad. Sci. Paris, Ser I 341(2005) 279-282.
  
• October 14 - Kyle Burke
  The Goemans-Williamson's approximation algorithms for MAX-CUT
  
  
• October 7 - Scott Russell
  Intrusion-Resilient Secure Channels
  Abstract:We propose a new secure communication primitive called an Intrusion-Resilient Channel (IRC) that limits the damage resulting from key exposures and facilitates recovery. We define security against passive but mobile and highly adaptive adversaries capable of exposing even expired secrets. We describe an intuitive channel construction using (as a black box) existing public key cryptosystems. The simplicity of the construction belies the technical challenges in its security proof.
  Additionally, we outline a general strategy for proving enhanced security for two-party protocols when an IRC is employed to secure all communication. Specifically, given a protocol proven secure against adversaries with restricted access to protocol messages, we show how the use of an IRC allows some of these adversary restrictions to be lifted. Once again, proving the efficacy of our intuitive approach turns out to be non-trivial. We demonstrate the strategy by showing that the intrusion-resilient signature scheme of Itkis and Reyzin (see SiBIR: Intrusion-Resilient signatures, or toward obsoletion of certificate revocation in Proceeding of Crypto '02) can be made secure against adversaries that expose even expired secrets.
  This is joint work with Robert McNerney, Jr. and Gene Itkis.
  It appears in Applied Cryptography and Network Security (ACNS) 2005, full version available via IACR's e-print site.
  For links to both versions see: http://cs-people.bu.edu/srussell/
  
• September 23 - Leonid Levin
  Aperiodic Tilings: Breaking Translational Symmetry
  Abstract: Classical results on aperiodic tilings are rather complicated and not widely understood. I will discuss an alternative approach in hope to provide additional intuition not apparent in classical works.
  Physical computing media are asymmetric. Their symmetry is broken by irregularities, physical boundaries, external connections, and so on. Such peculiarities, however, are highly variable and extraneous to the fundamental nature of the media. Thus, they are pruned from theoretical models, such as cellular automata, and reliance on them is frowned upon in programming practice.
  Yet, computation, like many other highly organized activities, is incompatible with perfect symmetry. Some standard mechanisms must assure breaking the symmetry inherent in idealized computing models. A famous example of such mechanisms is aperiodic tiling: hierarchical self-similar constructions, first used for computational purposes in rather complicated works by Berger, Robinson, Myers, and others.
  A tile is a unit size square with colored edges. A palette is a finite set of tiles with copies of which one can tile a plane so that the colors of adjacent tiles match. Berger, Robinson, Myers found palettes P that can tile a plane but not periodically (or even recursively). The set of all P-tilings is, of course, symmetric under translations. Yet, any specific P-tiling is aperiodic, this symmetry spontaneously broken. Classical proofs of this result are very cumbersome. I will try to present a more transparent construction and proof.
  More details of this lecture and proofs of the results discussed above can be found here
• September 12 - Stathis Zachos
  Routing and Path Coloring in Multifiber All-Optical Network
  Abstract: Routing and Path Coloring (Wavelength Assignment) has been extensively studied in single-fiber all-optical networks during the last fifteen years. Recently, variations of the problem inspired from multiple-fiber networks have gained considerable interest. In this presentation we will discuss several results in the field, concerning various simple network topologies. We will also describe innovative techniques that are employed.
  

• January 28 - Jie Wang
  Constructing an optimal clustering from several existing clusterings
  Abstract: Let s be a data set. suppose we are given m un-identical clusterings of s produced by different clustering algorithms. we are interested in, based on the information presented in these m clusterings, constructing a new clustering of s that is optimal according to a certain meaningful measure. such a measure can be defined using a graph theoretic model or a set theoretic model. in this talk we will first explore the graph theoretic model. we define threshold graphs and formulate an integer programming problem to produce a new clustering. the problem is np-hard. we show that it is straightforward to obtain a ratio-8 approximation algorithm in polynomial time. we can further improve this ratio to 4 provided that we can solve a minimization problem with a linear objective and non-linear constraints in the form of x <= max{y, z}. we will then explore the set theoretic model and define a minimum clustering problem based on symmetric difference. we show that the problem is np-hard.
  This is joint work with M.-Y. Kao and N. Zhong.
• February 4 - Klaus Ambos-Spies (University of Heidelberg)
  Finite-State Genericity
  Abstract: Algorithmic and resource-bounded genericity concepts have become elegant and powerful tools in computability and computational complexity theory. Here we explore the power of genericity concepts in the setting of formal language theory focusing on the class of regular languages. We introduce and investigate various genericity concepts based on extension functions computable by finite automata. For bounded finite-state genericity, which is based on extension functions of constant length, we show that the corresponding generic languages are not regular but can be context-free. Moreover, we give a combinatorial characterization of this concept by showing that a language is bounded finite-state generic if and only if its characteristic sequence is disjunctive (i.e., every binary word occurs in the characteristic sequence as a subword). By considering finite-state extensions of non-constant length we obtain stronger finite-state genericity notions forcing some more fundamental finite-state properties. E.g., for genericity based on generalized Moore functions, the corresponding generic languages are bi-immune to the class of regular languages.
  This is a joint work with Edgar Busse, University of Heidelberg.
• February 18 - Nenad Dedic
  Upper and Lower Bounds on Black-Box Steganography
  Abstract: We study the limitations of steganography when the sender is not using any properties of the underlying channel beyond its entropy and the ability to sample from it. On the negative side, we show that the number of samples the sender must obtain from the channel is exponential in the rate of the stegosystem. On the positive side, we present the first secret-key stegosystem that essentially matches this lower bound regardless of the entropy of the underlying channel. Furthermore, for high-entropy channels, we present the first secret-key stegosystem that matches this lower bound statelessly (i.e., without requiring synchronized state between sender and receiver).
  Joint work with Gene Itkis and Leonid Reyzin and Scott Russell.
• February 25 - Steve Homer
  Autoreducibility for complete sets
  Abstract: A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. Long ago (1992), Buhrman, Fortnow, van Melkebeek and Torenvliet studied the question of whether all complete sets for various classes are autoreducible. They answered this question for some classes. For example, the answer is yes for levels of the exponential time hierarchy and no for doubly exponential space. Settling this  problem for doubly exponential time is more interesting, as settling it would either separate P from PSPACE or NL from NP.
  More recently Glasser, Ogihara, Pavan, Selman and Zhang have made progress on this same problem, but for many-one completeness. They proved that all NP-comnplete and PSPACE complete  sets are autoreducible.
  We will discuss these results and prove at most one of them.
• March 4 - Amitabha Roy
  Definability of Languages by Generalized First-Order Formulas over natural numbers (with +)
  Abstract: We consider an extension of first-order logic by modular quantifiers of a fixed modulus q . Drawing on techniques from both model theory and finite semigroup theory, we show that if the only available atomic formulas are addition and a predicate stating that the bit in a given position is on, then sentences in this logic cannot define the set of bit strings in which the number of 1's is divisible by a prime p that does not divide q.  The corresponding statement, with addition replaced by arbitrary numerical predicates, is equivalent to the conjectured separation of the circuit complexity class ACC from NC¹. Thus this new result can be considered as a highly uniform version of the conjecture.
  This is a joint work with Howard Straubing (Boston College).
• March 25 - David Charlton
  The Difficulty of Lower Bound Proofs
  Abstract:Most researchers believe we are still far from resolving major lower bound questions such as P != NP. Even PSPACE, a class arguably containing all problems whose solutions humans could understand, is not proven to be distinct from P. With so many characterizations of the different complexity classes, and so many natural problems arising in each of them, it is reasonable to ask: why is this so hard? Why don't we have even an n² bound on any function below EXP?
  This talk presents Razborov and Rudich's notion of Natural Proofs, which attempts to explain why our intuition fails us when we deal with these kinds of complexity classes. We formally define "natural" function properties, and show why proofs relying on such properties are unlikely to give us significant lower bounds. If time permits, we will also discuss formal reasons why lower bound proofs tend to rely on natural properties.
• April 16 - Shang-Hua Teng
  Lower-Stretch Spanning Trees
  Abstract: A low-stretch spanning tree T of a graph G is a spanning tree subgraph in which most edges of G can be routed with small dilation. In particular, the stretch of an edge of G in T is the length of the path in T connecting the endpoints of that edge. The average stretch is the average over edges in G of their stretch. In an analysis of an algorithm for the k-server problem, Alon, Karp, Peleg and West showed that there exist spanning trees of average stretch exp(O(sqrt(log nlog log n )). We were motivated to improve their construction because this average-stretch is the dominant term in the complexity of a new solver for diagonally-dominant systems of equations. We present an O(m log²n)-time algorithm that constructs trees of much lower average stretch: O(log² n log log n).
  This is joint work with Michael Elkin, Yuval Emek and Daniel Spielman.
• April 22 and 29 - Fred Green
  On the Correlation between Mod q Functions and Polynomials Mod m
  Abstract: We say a polynomial $t$ computes a boolean function $f$ if $t$ is zero exactly when $f = 1$. The correlation between two boolean functions is a measure of how well they agree. It is an important open problem to determine as precisely as possible the correlation between the Mod q function and polynomials over Z_m (where these polynomials compute a boolean function as defined above) when (q, m) = 1. In this talk I will briefly review some of the motivation for this problem, hearkening back to the talk I gave way back in December of 2004. Since then, J. Bourgain has given a proof that shows that the correlation between such functions is indeed, as was conjectured, exponentially small, as long as the degree of the polynomial is at most log n. The proof uses analytic techniques for the estimation of exponential sums.

• October 1 - Debajyoti Bera
  Using Grover's Algorithm to speed up Graph Problems
  Abstract: The talk will discuss an extension of the methods of Grover's algorithm, and the application of these methods to common graph algorithms. In particular, quantum algorithms for finding minimum weight spanning trees and for connectivity will be considered. The talk is based on the 2004 ICALP paper on this topic by Durr, Heiligman, Hoyer and Mhalla.
  The PDF file of the presentation is here.
• October 8 - Kyle Burke
  The Linial-Saks Graph Decomposition Algorithm
  Abstract: In a paper by Nathan Linial and Michael Saks titled, "Decomposing Graphs into Regions of Small Diameter," we find a slick randomized algorithm which runs in log-squared time and decomposes a graph into O(log n) blocks of O(log n) diameter. This algorithm utilizes a simple message passing scheme in which nodes of the graph broadcast some information about themselves, then select a center from the messages they receive. This talk will cover the algorithm and the probability deductions which show its strength. If time permits, we will cover the protocol used for the message passing, as well as the problems we are having to adopt this method.
  
• October 15 - Maosen Fang
• October 22 - Ed Farhi
  Continuous Time Quantum Random Walk
  
• October 29 - Peter Gacs
  Self-stabilizing Synchronization in 3 Dimensions
  (Joint work with Matthew Cook and Erik Winfree)
  Abstract: The simplest known fault-tolerant model of computation is the three-dimensional cellular automaton introduced by G\'acs and Reif. However, this automaton works only in discrete time (that is, if synchronization is provided for free); the only known asynchronous reliable cellular automata are vastly more complex. Surprisingly, a simple scheme is known to introduce asynchrony into any kind of network: each cell keeps track of which neighbors are ahead or behind (at most one step difference is allowed), for example via a mod 3 clock. This mechanism is very efficient in the absence of errors, or if the errors leave the local ordering in a consistent state (no cycles). But errors could create topological inconsistency in spacetime which, unless resolved quickly, may become fatal. We found a simple way to resolve localized topological inconsistencies of arbitrary size. The scheme is self-stabilizing: it corrects inconsistency of an arbitrary size fast, in the absence of further errors. The final goal is to show that this scheme also works in noise.
  
• November 5 - Gary Benson
  Searching for Inverted Repeats in Genomic Sequences
  Abstract: Inverted repeats (IRs) consist of two arms of homologous DNA with one inverted and complemented relative to the other around a central spacer region, and are in theory capable of forming stem-loop structures through pairing of the arms. Short IR pairing forms secondary structure in RNA sequences. Longer IR pairing in DNA can in principle form cruciform structures, which would be facilitated by negative DNA supercoiling. IRs have been associated with DNA replication, genomic instability, SMC protein binding and microRNA expression. Until recently, there has been no efficient program for detecting IRs in long genomic sequences.
  In this talk, I discuss recent work on a program, Inverted Repeats Finder (IRF), for finding approximate inverted repeats. IRF works, in many ways, like an earlier program, Tandem Repeats Finder. Candidate IRs are detected by finding short, exact, reverse-complement matches of 4-7 nucleotides (k-tuples) between non-overlapping fragments of a sequence. Unlike the case for tandem repeats, the distance between matching tuples is not related to the size of the repeat. This makes for some interesting differences in the approach to candidate recognition.
  The first application of IRF has been analysis of the recently completed human genome sequence (hg16). After masking of know repetitive elements, IRF detected 22,429 human IRs in 6 hours on a desktop PC. 159 IRs had arm lengths >8kb with a significant overabundance of these large IRs on the X and Y chromosomes. The presence on the Y chromosome of large, highly homologous IRs, which often contain genes expressed predominantly in testes, was recently described. Our analysis shows that there are similar large, homologous IRs on the X chromosome and that many of these also contain testes genes.
  
• November 12 - Iordanis Kerenidis
  Quantum Encodings and applications to Communication Complexity and Locally Decodable Codes
  Abstract: Quantum computation and information has become a central research area in theoretical computer science. It studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. The ability of a quantum system to be in a superposition of states enables us to store an exponential amount of information in a quantum system. However, this information is accessible only indirectly via measurements. Our goal is precisely to investigate the fundamental question of how information is encoded and processed in quantum mechanical systems.
  We investigate their power relative to classical encodings in the model of one-way communication complexity and show that they can be exponentially more efficient, answering a long-standing open question in the area of quantum communication complexity. Furthermore, we show how the theory developed for the study of quantum information can be employed in order to answer questions about classical coding theory and complexity by proving an exponential lower bound for 2-query Locally Decodable Codes. This is the first example where quantum techniques are essential in resolving a purely classical question.
  No previous knowledge of quantum computing is assumed.
  
• November 19 - Samik Sengupta
  Competing Provers and Nonexistence of Small Proofs for coNP
  Abstract: In this talk, we present the recent result that provides evidence of nonexistence of polylogarithmic-round interactive proof system for sets in coNP. Boppana, Hastad, and Zachos showed that if every set in coNP has constant-round interactive proof system, then the polynomial hierarchy collapses to the second level. On the other hand, Lund, Fortnow, Karloff, and Nisan proved that every set in coNP has a polynomial-round interactive proof system. Our result is the first step towards bridging the gap between these two results.
  We define the operator S_2 defined by Russell and Sundaram, and by Canetti, and show the improvement of Karp-Lipton collapse under the assumption that SAT has polynomial-sized circuits. The extension of this operator to quasipolynomial and exponential-time hierarchies are used in obtaining our result.
  This is joint result with Alan L. Selman.
  
• December 3 - Ben Hescott
  Separating Notions of Completeness in PSPACE
  Abstract: The question of whether polynomial time Turing completeness (Cook) differs from polynomial time many one completeness (Karp) has remained open for decades. Of course a separation of these notions in PSPACE separates P from PSPACE. We consider a variation of this problem by focusing only on Turing reductions and instead vary the computational power of the reduction, i.e., P Turing reductions, BPP Turing reductions, and NP Turing reductions. Specifically under what assumption is there a set A in PSPACE which is not complete for PSPACE under polynomial Turing reductions, but is under nondeterministic Turing reductions. We show that producing a set which is complete under randomized reductions will answer this question, and give evidence that sets in PSPACE with high Kolmogorov Complexity seem to be likely candidates. We continue by considering a measure theoretic assumption and discuss open problems related to building such sets.
  
• December 10 - Fred Green
  The Correlation Between Parity and Quadratic Polynomials Mod 3, Revisited
  Abstract: We say a polynomial t computes a boolean function f if t is nonzero exactly when f = 1. The correlation between two boolean functions is the fraction of all input settings on which they agree minus the fraction of settings on which they disagree. It is an important open problem to determine as precisely as possible the correlation between parity and polynomials over Z_m (where these polynomials compute a boolean function as defined above) when m is odd. In this talk I will present some of the motivation for this problem. Three years back I showed that the correlation between parity and quadratic polynomials mod 3 decreases exponentially, by proving a tight bound on the value of a certain type of exponential sum that generalizes the classical Gauss sum. Since then, a number of researchers have worked to generalize the result to other values than m = 3 and also to higher degree polynomials. I will briefly discuss some of these efforts and report on some new facts we can prove for m = 3 that lend support to conjectures arising out of this recent work.
  

• January 30 - David Taylor
• February 6 - Drue Coles
• February 13 - Wim van Dam
• February 27 - Ari Trachtenberg
• March 5 - Eduardo Novais
• March 19 - Peter Shor
• March 26 - Erik Winfree
• April 2 - Dana Ron
• April 9 - Debajyoti Bera
• April 16 - Fred Green
• April 30 - Steve Homer