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 time is Friday 2-4pm and usually it is in MCS 135 (Computer Science Department).
For directions, go here.

Next  Talk :

Spring 2010: The next talk is on April 30^th by Ravi Sundaram  from Northeastern University.
3: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.

• April 30, 2010 - Ravi Sundaram (Northeastern University)
  Abstract:
  
  Inspired by the recent "2-NASH is PPAD-complete" breakthrough we show that a number of other problems are hard as well. Here is a list of the problems along with their area of motivation/significance:
  1. Fractional Stable Paths Problem - Internet Routing
  2. Core of Balanced Games - Economics and Game Theory
  3. Scarf's Lemma - Combinatorics
  4. Hypergraph Matching - Social Choice and Preference Systems
  5. Fractional Bounded Budget Connection Games - Social Networks
  6. Strong Fractional Kernel - Graph Theory
  
  We will define these problems, state our results, give a flavor of our reductions and conclude with some open problems.
  
  Joint work with S. Kintali, L. Poplawski, R. Rajaraman and S. Teng.
   

• April 23, 2010 - Andrei Lapets (Boston University)
  The complexity of a restricted variant of the stable paths problem
  Abstract:
  
  The stable paths problem (SPP) is the problem of selecting next-hop paths (i.e. routes) to some destination for each node in a graph (i.e. network). A stable solution to this problem consists of a selection of routes from which no node would prefer to deviate according to its preferences. BGP can be viewed as a distributed algorithm for solving an SPP instance. We define an even more restricted variant of SPP, which we call f-SPP, and present a succinct proof that the problem of determining whether a stable solution for an f-SPP instance exists is NP-complete. This proof implies that even if each node in a network is restricted to one of only two policies, and each of these two policies is based on a monotonic path weight aggregation function, the problem of determining whether a stable solution exists is still NP-complete. Because f-SPP can also be viewed as a natural
  multi-dimensional generalization of the shortest path problem, this result may provide clues about the complexities of "multi-dimensional" variants of other efficiently solvable problems involving weighted graphs.
  
  These results are based on joint work with Kevin Donnelly and Assaf Kfoury.
   

• April 16, 2010 - Alexander Shen (LIF Marseille, on leave from IITP RAS, Moscow)
  Everywhere complex sequences and the probabilistic method
  Abstract:
  
  Let c<1 be some positive constant. One can show that there exists an ``everywhere complex'' bit sequence (=``Levin sequence'') W such that every substring x of W of length n has complexity at least cn-O(1). There are several ways to prove the existence of such a sequence (a complexity argument; application of Lovasz Local Lemma, and some others). S. Simpson asked whether there exist an algorithm that produces such a sequence when supplied with a Martin-Lof random oracle. Recently A.Rumyantsev gave a negative answer to this question; we discuss this and related results.
  
   

• March 19, 2010 - Giorgios Zervas (Boston University)
  Information Asymmetries in Pay-Per-Bid Auctions
  Abstract:

  Recently, some mainstream e-commerce web sites have begun using "pay-per-bid" auctions to sell items, from video games to bars of gold. In these auctions, bidders incur a cost for placing each bid in addition to (or sometimes in lieu of) the winner's final purchase cost. Thus even when a winner's purchase cost is a small fraction of the item's intrinsic value, the auctioneer can still profit handsomely from the bid fees. Our work provides novel analyses for these auctions, based on both modeling and datasets derived from auctions at Swoopo.com, the leading pay-per-bid auction site.

  While previous modeling work predicts profit-free equilibria, we analyze the impact of information asymmetry broadly, as well as Swoopo features such as bidpacks and the Swoop It Now option specifically. We find that even small asymmetries across players (cheaper bids, better estimates of other players' intent, different valuations of items, committed players willing to play "chicken") can increase the auction duration significantly and thus skew the auctioneer's profit disproportionately. We discuss our findings in the context of a dataset of thousands of live auctions we observed on Swoopo, which enables us also to examine behavioral factors, such as the power of aggressive bidding. Ultimately, our findings show that even with fully rational players, if players overlook or are unaware any of these factors, the result is outsized profits for pay-per-bid auctioneers.

  Joint work with John Byers and Michael Mitzenmacher

  
  

• March 5, 2010 - Philipp Weis (UMass Amherst)
  Expressiveness and Succinctness of First-Order Logic on Words and Linear Orders
  

  Abstract:

  Both expressiveness and succinctness are important characteristics of any logical language. While expressiveness simply asks for the properties that can be expressed in a given logic, succinctness is concerned with the relative size of the formulas of one logic compared to another logic. For this talk, we restrict our attention to the finite-variable fragments of first-order logic, and only consider word structures and linear orders.

  We present an expressiveness result for first-order logic with two variables on words, proving that there is a strict quantifier alternation hierarchy for this logic. As a consequence of our structural results, the satisfiability problem for this logic, which was previously only known to be NEXP-complete, is NP-complete for alphabets of a bounded size.

  In the second part of this talk, we will briefly survey known results on succinctness, point out a close connection to the complexity theoretic trade-off between parallel time and the number of processors, and present some open questions and ongoing research
  

• April 10, 2009 - Lance Fortnow (Northwestern 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&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.
  
• 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.