Fall
2008 
 September 19  David Charlton (Boston U.)
User Preferences and the Netflix Prize
Abstract:
Two years ago, Netflix started a novel research experiment by publicly
releasing part of their movie rating database and offering a $1 million
prize to any team that could predict movie ratings with 10% better accuracy
than Netflix's proprietary Cinematch algorithm.
The Netflix Prize produced a surge of interest in the already growing field of
collaborative filtering, which asks: given a large but sparse set of past user
opinions, how can we accurately predict future ones? This talk will describe
common theoretical approaches to collaborative filtering, the obstacles
encountered in realworld implementations, as well as some surprisingly
effective new algorithms discovered by Netflix Prize competitors, the
theoretical basis of which is still unclear. It will also summarize an
implementation that currently gives 8.79% improvement over Netflix's Cinematch
baseline.
 September 24  Jie Wang (U. of Mass., Lowell)
Strong Barrier Coverage using Networks of Randomly Deployed Sensors
Abstract:
Constructing sensor barriers to detect intruders crossing a randomlydeployed sensor network
along boundaries of a geographical region is an important problem, which has been studied
intensively in recent years under the assumption that sensors are deployed uniformly at random
in a large area (Poisson point process model). Early results have shown how to construct a
sensor barrier to detect intruders moving along restricted crossing paths in rectangular areas.
We present a complete solution to this problem using percolation theory and maxflow algorithms.
In particular, we show how to efficiently construct sensor barriers on long strip areas of
irregular shape without any constraint on crossing paths.
Next, we consider linebased sensor deployments where sensors are dropped from an aircraft (or
by other means) along a given path. Under this model, sensors are distributed along the line
with random offsets due to wind and other environmental factors. We present the first set of
results in this direction. In particular, we establish a tight lowerbound for the existence
of barrier coverage under linebased deployments. Our results show that the barrier coverage of
the linebased deployments significantly outperforms that of the Poisson model when the random
offset is relatively small compared to the sensor's sensing range. We then study sensor
deployments along multiple lines and show how barrier coverage is affected by the distance
between adjacent lines and the random offsets of sensors. These results offer guidelines to
the deployment and performance of wireless sensor networks for barrier coverage.
This is joint work with Benyuan Liu, Olivier Dousse, Anwar Saipulla, and Cedric Westphal.
 October 3  Ben Allen (Boston U. Math. Dept.)
The CategoryTheoretic Arithmetic of Information
Abstract:
We highlight the underlying categorytheoretic structure of measures of
information flow. We present an axiomatic framework in which communication
systems are represented as morphisms, and information flow is characterized
by its behavior when communication systems are combined. Our framework
includes a variety of discrete, continuous, and, conjecturally, quantum
information measures. It also includes some familiar mathematical constructs
not normally associated with information, such as vector space dimension. We
discuss these examples and prove basic results from the axioms.
 October 10  Ben Hescott (Tufts U.)
Reductions with and without advice in exponential time
Abstract:
We investigate the relationship between nonuniform and uniform reductions in
exponential time. Specifically, we show that sets that are complete for EXP
using polynomial time many one reductions with one bit of advice are also
complete using polynomial time Turing reductions. We show how to strengthen
this result to a logarithmic amount of advice. Interestingly this result is
nonrelativizing and we construct an oracle separating the two reductions in
EXP. We conclude with a nonuniform version of JosephYoung conjecture.
 October 17  Bhavana Kanukurthi (Boston U.)
An Improved Robust Fuzzy Extractor
Abstract:
We consider the problem of building robust fuzzy extractors, which
allow two parties holding similar random variables W, W' to agree
on a secret key R in the presence of an active adversary.
Robust fuzzy extractors were defined by Dodis et al. in Crypto 2006
to be noninteractive, i.e., only one message P, which can be modified
by an unbounded adversary, can pass from one party to the other.
This allows them to be used by a single party at different points in
time (e.g., for key recovery or biometric authentication), but also
presents an additional challenge: what if R is used, and thus
possibly observed by the adversary, before the adversary has a chance to
modify P. Fuzzy extractors secure against such a strong attack
are called postapplication robust.
We construct a fuzzy extractor with postapplication robustness
that extracts a shared secret key of up to (2mn)/2 bits (depending
on errortolerance and security parameters), where n is the
bitlength and m is the entropy of W. The previously best known
result, also of Dodis et al., extracted up to (2mn)/3 bits
(depending on the same parameters).
This is joint work with Leonid Reyzin.
 October 24  Emanuale Viola (Northeastern U.)
Part of BU/NEU Theory of Computation seminar.
This talk will take place at Boston university.
Polynomials over {0,1}
Abstract:
Polynomials are fundamental objects in computer science that arise in a
variety of contexts, such as errorcorrecting codes and circuit lower bounds.
Despite intense research, many basic computational aspects of polynomials
remain poorly understood. For example, although it is known that most functions
cannot be approximated by lowdegree multivariate polynomials, an explicit
construction of such a function is still unknown.
In this talk we discuss some of the progress we have made towards understanding
computational aspects of polynomials. In particular, we present our recent
result that the sum of d pseudorandom generators for degree1 polynomials is
a pseudorandom generator for polynomials of degree d.
 October 31  Matthias Englert (U. of Warwick)
The Power of Reordering for Online Minimum Makespan Scheduling
Abstract:
In the wellknown minimum makespan scheduling problem, we are given an
input sequence of jobs with processing times. A scheduling algorithm has
to assign the jobs to m parallel machines. The objective is to minimize
the makespan, which is the time it takes until all jobs are processed.
We consider online scheduling algorithms without preemption.
However, we do not require that each arriving job has to be
assigned immediately to one of the machines. A reordering
buffer with limited storage capacity can be used to reorder
the input sequence in a restricted fashion so as to schedule
the jobs with a smaller makespan. This is a natural extension
of lookahead.
We present an extensive study of the power and limits of
online reordering for minimum makespan scheduling. As
main result, we give, for m identical machines, tight and,
in comparison to the problem without reordering, much
improved bounds on the competitive ratio for minimum
makespan scheduling with reordering buffers. This optimal
ratio is achieved with a buffer of size Theta(m). We show
that larger buffer sizes do not result in an additional
advantage and that a buffer of size Omega(m) is necessary
to achieve this competitive ratio.
This talk is based on joint work with Deniz Ozmen and Matthias Westermann.
 November 7  Peter Gacs (Boston U.)
A storage allocation game with an application in algorithmic information
theory
Abstract:
I will present a game in which User is gradually increasing the weight
(probability) of strings, and Server allocates binary codewords to these
strings gradually (and irrevocably) in such a way that the prefix relation is
preserved. Server's additional constraint is that to strings with
large weight, (also) short codewords must be assigned. In case the
alphabet of the strings is infinite, the reachable bound can be
characterized exactly. But if it is finite then the solution is only
known to be somewhere between loglog and log. Until two months ago,
the lower bound was much worse: Adam Day improved it from the
inverse Ackermann function (my old result) to loglog.
The problem is coming from algorithmic information theory, I will outline
the connection.
 Nov 14  Lenore Cowen (Tufts U.)
Fault Tolerance in Protein Interaction Networks: Stable Bipartite Subgraphs and Redundant Pathways
Abstract:
As increasing amounts of highthroughput data for the yeast
interactome becomes available, more systemwide properties
are uncovered. One interesting question concerns the fault
tolerance of protein interaction networks: whether there exist
alternative pathways that can perform some required function
if a gene essential to the main mechanism is defective, absent or
suppressed. One signature pattern for redundant pathways is the
BPM (betweenpathway model) motif, first suggested by Kelley and
Ideker. Past methods proposed to search for BPM motifs have had
several important limitations. First, they have been driven
heuristically by local greedy searches, which can lead to the
inclusion of extra genes that may not belong in the motif;
second, they have been validated solely by functional coherence of the
putative pathways using GO enrichment, making it difficult to evaluate
putative BPMs in the absence of already known biological annotation.
We show how a simple "folk" theorem in graph theory (probably due to Erdos)
can help us identify possible BPMs in such a way that not only do we get
better coherence of biological function, but we also have a direct way
to validate our results based directly on the structure of the network.
We uncover some interesting biological examples of previously unknown
putative redundant pathways in such areas as vesiclemediated transport
and DNA repair. We then show how a separate source of highthroughput
data, based on microarrays, can be used to further independently validate
putative BPMs.
 November 21  Alex Samorodnitsky (Hebrew University and Microsoft Research)
Part of BU/NEU Theory of Computation seminar.
This talk will take place in Northeastern University.
Edgeisoperimetry and influences
Abstract:
We will give alternative proofs of two known results on influences of
boolean functions, deriving them from a variant of the edgeisoperimetric
inequality on the boolean cube. The first result is a theorem of Kahn,
Kalai, and Linial stating that every boolean function has an influential
variable. The second result is a theorem of Friedgut which states that
a function with a small sum of influences essentially depends only a on
few of its variables.
 December 12  Benjamin Rossman (MIT)
Part of BU/NEU Theory of Computation seminar.
This talk will take place in Northeastern University.
The ConstantDepth Complexity of kClique
Abstract:
I will discuss a recent AC0 lower bound: the kclique problem on graphs
of size n cannot be solved by constantdepth circuits of size O(n^{k/4}).
This result has an interesting corollary in logic (finite model theory):
the firstorder "variable hierarchy" is strict in terms of expressive
power on ordered graphs (it was previously open whether 3 variables
suffice to define every firstorder property of ordered graphs).


