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 :

Fall 2008: The next talk is on December 12th by Benjamin Rossman from MIT.
Venue: 4:00 pm at Northeastern University at 440 Huntington Ave in room 366 of West Village H.

The tentative schedule for the this semester is given below.

Some of the talks are part of the joint Boston university/Northeastern university Theory of Computation seminar.

The schedule for the previous semesters from Spring 2004 to Spring 2007 is here.


  • 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 real-world 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 randomly-deployed 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 max-flow 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 line-based 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 lower-bound for the existence of barrier coverage under line-based deployments. Our results show that the barrier coverage of the line-based 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 Category-Theoretic Arithmetic of Information
    Abstract: We highlight the underlying category-theoretic 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 Joseph-Young 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 post-application robust.
    We construct a fuzzy extractor with post-application robustness that extracts a shared secret key of up to (2m-n)/2 bits (depending on error-tolerance and security parameters), where n is the bit-length and m is the entropy of W. The previously best known result, also of Dodis et al., extracted up to (2m-n)/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 error-correcting 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 low-degree 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 degree-1 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 well-known 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 high-throughput data for the yeast interactome becomes available, more system-wide 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 (between-pathway 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 vesicle-mediated transport and DNA repair. We then show how a separate source of high-throughput 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.

    Edge-isoperimetry and influences
    Abstract: We will give alternative proofs of two known results on influences of boolean functions, deriving them from a variant of the edge-isoperimetric 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 Constant-Depth Complexity of k-Clique
    Abstract: I will discuss a recent AC0 lower bound: the k-clique problem on graphs of size n cannot be solved by constant-depth circuits of size O(nk/4). This result has an interesting corollary in logic (finite model theory): the first-order "variable hierarchy" is strict in terms of expressive power on ordered graphs (it was previously open whether 3 variables suffice to define every first-order property of ordered graphs).

Back to the Theory Group home page.

Last Updated: Sep 30th, 2005
Page Maintained by: Debajyoti Bera

Department of Computer Science
Boston University
111 Cummington Street, MCS 138
Boston  MA  02215