






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 34pm and usually its in MCS135
(Computer Science Department).
For directions, go here.
Next
Talk :
This page contains the announcements of the seminar from Spring 2004 to Spring 2007.
For the current semester, go here.


Spring
2007 
 January 26  Ben Hescott
Nonuniform Completeness and Nondeterministic Incompleteness
Abstract:
In this proposal we will consider two different types of reductions,
nonuniform manyone 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, manyone complete sets are also complete with
lengthincreasing 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
Nonuniform reductions and exponential time completeness
Abstract:
Efficient nonuniform reductions are defined and results relating
these reductions to the standard uniform polynomial time reductions
are discussed. We focus on exponential time,
 proving a
result relating uniform and nonuniform EXP complete sets
and
 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 selfstabilization and synchronization. There are (interdependent) selfstabilizing 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 informationtheoretic secure
multiparty computation, IshaiKushilevitz (FOCS 2000) introduced the
notion of randomizing polynomials. One of their interesting results is
that degree3 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 MaxWeight Triangle in SubCubic Time
Abstract:
Given a nodeweighted 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
subcubic algorithm (roughly n^{2.7}, improving the former bound of
(n^{3} / 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 TwoDimensional Regions
Abstract:
This talk will survey some complexity issues involved in computing
twodimensional sets on the plane, based the model of Turing
machine with oracles; that is, the bitcomplexity 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 oneway 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 oneway functions".
 April 27  Nenad Dedic (Boston University)
On Trading Secret Random Bits for Public Ones
Abstract:
We study the question of when a oneway 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 oneway 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 oneway function cannot be
reduced using blackbox techniques (even for regular functions).
Unfortunately, this appealing approach is not possible for general oneway
functions. We prove that for general oneway functions, secret randomness
cannot be replaced with public randomness using blackbox reductions.
As an application of this approach we show a large class of oneway
functions other than permutations that can be used to build pseudorandom
generators with linearlength seeds: regular ones with "known" high
degeneracy. When counting only secret randomness, this forms a first general
construction of pseudorandom generators from oneway functions where the
input length of the generator is sublinear in that of the oneway
function.
Joint work with Danny Harnik (Technion) and Leonid Reyzin.
 May 9  Bill Gasarch (University of Maryland)
The Multiparty Communication Complexity of ExactT
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 nbits long so the numbers themselves are <= 2^{n}.
They want to know if a+b+c=2^{n}.
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^{n} 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/(k1)}) bits.
 In the 3 player case it requires Ω(log log n).
 We have some empirical studies as well in the 3player case.
This is based on a joint work with Beigel and Glenn.



Spring
2006 
 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



Fall
2005 
 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
manyone complete sets (including the NPcomplete sets)
are all manyone autoreducible.
Since then there have have been several
related results concerning selfreducibility
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 NPcomplete 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 (manyone) 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))
627631, 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). Subexponential 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 fanin 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)
279282.
 October 14  Kyle Burke
The GoemansWilliamson's approximation algorithms for MAXCUT
 October 7  Scott Russell
IntrusionResilient Secure Channels
Abstract:We propose a new secure communication primitive called an
IntrusionResilient 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 twoparty 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 nontrivial. We demonstrate the strategy by showing that the
intrusionresilient signature scheme of Itkis and Reyzin
(see SiBIR: IntrusionResilient 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 eprint site.
For links to both versions see: http://cspeople.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
selfsimilar 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 Ptilings is, of course, symmetric under translations. Yet,
any specific Ptiling 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 AllOptical
Network
Abstract: Routing and Path Coloring
(Wavelength Assignment) has been extensively studied in singlefiber
alloptical networks during the last fifteen years. Recently,
variations of the problem inspired from multiplefiber 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.



Spring
2005 
 January 28  Jie Wang
Constructing an optimal clustering from several
existing clusterings
Abstract: Let s be a data set. suppose we
are given m unidentical 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 nphard. we show that it is
straightforward to obtain a ratio8 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
nonlinear 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
nphard.
This is joint work with M.Y. Kao and N. Zhong.
 February 4  Klaus AmbosSpies (University of
Heidelberg)
FiniteState Genericity
Abstract: Algorithmic and resourcebounded
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 finitestate genericity,
which is based on extension functions of constant length, we show that
the corresponding generic languages are not regular but can be
contextfree. Moreover, we give a combinatorial characterization of
this concept by showing that a language is bounded finitestate 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 finitestate extensions of nonconstant length we obtain
stronger finitestate genericity notions forcing some more fundamental
finitestate properties. E.g., for genericity based on generalized
Moore functions, the corresponding generic languages are biimmune 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 BlackBox 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 secretkey
stegosystem that essentially matches this lower bound regardless of the
entropy of the underlying channel. Furthermore, for highentropy
channels, we present the first secretkey 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 manyone completeness. They
proved that all NPcomnplete 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 FirstOrder
Formulas over natural numbers (with +)
Abstract: We consider an extension of
firstorder 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^{1}.
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^{2}
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  ShangHua Teng
LowerStretch Spanning Trees
Abstract: A lowstretch 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 kserver 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 averagestretch is the dominant term in
the complexity of a new solver for diagonallydominant systems of
equations. We present an O(m log^{2}n)time
algorithm that constructs trees of much lower average stretch: O(log^{2}
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.



Fall
2004 
 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 LinialSaks 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
logsquared 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
Selfstabilizing Synchronization in 3 Dimensions
(Joint work with Matthew Cook and Erik Winfree)
Abstract: The simplest known
faulttolerant model of computation is the threedimensional 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
selfstabilizing: 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 stemloop 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, reversecomplement matches of
47 nucleotides (ktuples) between nonoverlapping 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 oneway communication complexity and show that they can be
exponentially more efficient, answering a longstanding 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 2query 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
polylogarithmicround interactive proof system for sets in coNP.
Boppana, Hastad, and Zachos showed that if every set in coNP has
constantround 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 polynomialround
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 KarpLipton collapse under the
assumption that SAT has polynomialsized circuits. The extension of
this operator to quasipolynomial and exponentialtime 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.



Spring
2004 
 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


