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 2009: The next talk is on April 10^th by Lance Fortnow from the Dartmouth University.
4:00pm at Boston University at 111 Cummington Street in room MCS135.

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.

• January 14 - Bodo Manthey (Saarland U.)
  Approximating Multi-Criteria Traveling Salesman Problems
  Abstract: In many optimization problems, there is more than one objective to be optimized. In this case, there is no natural notion of a best choice. Instead, the goal is to compute a so-called Pareto curve of solutions, which is the set of all solutions that can be considered optimal. Since computing Pareto curves is very often intractable, one has to be content with approximations to them.
  We present approximation algorithms for several variants of the multi-criteria traveling salesman problem (TSP), whose approximation performances are independent of the number k of criteria and come close to the approximation ratios obtained for TSP with a single objective function.
  First, we present a randomized approximation ratio for multi-criteria Min-ATSP with an approximation ratio of log n + eps, where eps is arbitrarily small. Second, we present a randomized 1/2 - eps approximation algorithm for multi-criteria Max-ATSP. This algorithms can be turned into a 2/3 - eps approximation for multi-criteria Max-STSP. Finally, we devise a deterministic 1/4 approximation algorithm for bi-criteria Max-STSP.
  
• January 23 - Fred Green (Clark University)
  Uniqueness of Optimal Mod 3 Circuits for Parity
  Abstract: We prove that the quadratic polynomials modulo 3 with the largest correlation with parity are unique up to permutation of variables and constant factors. We thus completely characterize the MOD$_3 \circ {\rm AND}_2$ circuits that have the highest correlation with parity, where a MOD_3 \circ AND_2 circuit is one that has a MOD 3 gate as output, connected to AND gates of fan-in 2 which are in turn connected with the inputs. We also prove that the sub-optimal circuits of this type exhibit a ``stepped" behavior: any sub-optimal circuits of this class that compute parity must have a correlation at most $frac{\sqrt{3}}{2}$ times the optimal correlation. This verifies, for the special case of m=3, two conjectures made by Duenez, Miller, Roy and Straubing (Journal of Number Theory, 2006) for general MAJ~$circ mathrm{MOD}_m circ { m AND}_2$ circuits for any odd m. The correlation bounds are obtained by studying the associated exponential sums, based on some of the techniques developed by Green (JCSS, 2004). We regard this as a step towards obtaining tighter bounds both for the m not equal to 3 quadratic case as well as for higher degrees.
  This is joint work with Amitabha Roy.
  
• January 30 - Arkadev Chattopadhyay (IAS)
  Part of BU/NEU Theory of Computation seminar.
  This talk will take place in Boston University.
  Mutliparty Communication Lower Bounds by the Generalized Discrepancy Method
  Abstract: Obtaining strong lower bounds for the `Number on the Forehead' model of multiparty communication has many applications. For instance, it yields lower bounds on the size of constant-depth circuits and the size of proofs in important proof-systems.
  Recently, Shi and Zhu (2008), and Sherstov (2008) independently introduced two closely related techniques for proving lower bounds on 2-party communication complexity of certain functions. We extend both techniques to the multiparty setting. Each of them yields a lower bound of n^{\Omega(1)} for the k-party communication complexity of Disjointness as long as k is a constant. No superlogarithmic lower bounds were known previously on the three-party communication complexity of Disjointness.
  Part of this is joint work with Anil Ada.
  
• February 6 - Debajyoti Bera (BU)
  This is also the PhD proposal of Debajyoti Bera.
  Lower bound techniques for constant-depth quantum circuits
  Abstract: The circuit model of computing attracted theoretical computer scientists in the 1970s. There are usually two kind of questions for any model of computation, what can it efficiently compute and what it cannot. The initial decades of circuit theory were marked with a several new results and techniques and high expectations for the latter question. Opinions differ now about the viability of such techniques in the pursuit of the "ultimate answers" but nevertheless the line of research is active and interesting (and "practical", since real hardware is built using circuits).
  Quantum circuit is the same model extended to allow circuits with quantum gates and quantum information. In our work, we intend to gauge the power of of such circuits. We start with very simple circuits, limited in size and depth and number of extra fixed-values inputs and try to analyze them. We consider families of circuits with common gates and compare their power and their limits.
  In my proposal defense, I will mostly talk about a new technique to analyze constant-depth quantum circuits without ancillae. The technique is reminiscent of the algebraic lower bound technique for classical circuits. It gives us a new proof that the parity function cannot be computed by quantum circuits with limited resources. In the interest of the audience, I will also introduce the quantum circuit model, just the bits (or "qubit"s since this is a quantum talk) needed for this talk.
  
• February 20 - Joshua Brody (Dartmouth University)
  Part of BU/NEU Theory of Computation seminar.
  This talk will take place in Northeastern University.
  Some Applications of Communication Complexity
  Abstract: Communication Complexity has been used to prove lower bounds in a wide variety of domains, from the theoretical (circuit lower bounds) to the practical (streaming algorithms, computer security).
  In this talk, we present new results for two communication problems. We begin with a new lower bound for the communication complexity of multiparty pointer jumping. In the second half of the talk, we give several new results for distributed functional monitoring problems.
  Part of this talk is joint work with Amit Chakrabarti and Chrisil Arackaparambil.
  
• March 20 - Heiko Roeglin (MIT)
  k-Means has Polynomial Smoothed Complexity
  Abstract: The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points.
  We settle the smoothed running time of the k-means method: We show that the smoothed number of iterations is bounded by a polynomial in n and 1/sigma, where sigma is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.
  This is joint work with David Arthur (Stanford University) and Bodo Manthey (Saarland University).
  
• April 10 - Lance Fortnow (Northwestern University)
  Part of BU/NEU Theory of Computation seminar.
  This talk will take place in Boston University.
  Some Recent Results on Structural Complexity
  Abstract: We will talk about some recent work on complexity classes.
  1. For any constant c, nondeterministic exponential time (NEXP) cannot be computed in polynomial time with n^c queries to SAT and n^c bits of advice. No assumptions are needed for this theorem.
  2. A relativized world where NEXP is contained in NP for infinitely many input lengths ?
  3. If the polynomial-time hierarchy is infinite, one cannot compress the problem of determining whether a clique of size k exists in a graph of n vertices to solving clique problems of size polynomial in k.
  4. If the polynomial-time hierarchy is infinite there are no subexponential-size NP-complete sets (Buhrnan-Hitchcock).
  1 and 2 are from an upcoming ICALP paper by Buhrman, Fortnow and Santhanam.
  3 is from a STOC '08 paper by Fortnow and Santhanam answering open questions of Bodlaender-Downey-Fellows-Hermelin and Harnik-Naor.
  4 is from a CCC '08 paper by Buhrman and Hitchcock building on 3.