Spring 2010 

April 30, 2010 
Ravi Sundaram
(Northeastern University)
Abstract:
Inspired by the recent "2NASH is PPADcomplete"
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
nexthop
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 fSPP, and present a succinct proof that the problem
of
determining whether a stable solution for an fSPP instance
exists is NPcomplete. 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
NPcomplete. Because fSPP can also be viewed as a
natural
multidimensional generalization of the shortest path problem,
this
result may provide clues about the complexities of
"multidimensional"
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 cnO(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 MartinLof 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 PayPerBid Auctions
Abstract:
Recently, some mainstream ecommerce web sites have begun using
"payperbid"
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 payperbid auction site.
While previous modeling work predicts profitfree 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
payperbid
auctioneers.
Joint work with John Byers and Michael Mitzenmacher
 March 5, 2010  Philipp Weis (UMass Amherst)
Expressiveness and Succinctness of FirstOrder 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
finitevariable fragments of firstorder logic, and only consider word
structures and linear orders.
We present an expressiveness result for firstorder 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 NEXPcomplete, is NPcomplete 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 tradeoff 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 polynomialtime 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 polynomialtime hierarchy is infinite there are no
subexponentialsize NPcomplete sets (BuhrnanHitchcock).
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 BodlaenderDowneyFellowsHermelin and HarnikNaor.
4 is from a CCC '08 paper by Buhrman and Hitchcock building on 3.
 January 14  Bodo Manthey (Saarland U.)
Approximating MultiCriteria 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 socalled 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
multicriteria 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
multicriteria
MinATSP with an approximation ratio of log n + eps, where eps
is
arbitrarily small. Second, we present a randomized 1/2  eps
approximation algorithm for multicriteria MaxATSP. This
algorithms can
be turned into a 2/3  eps approximation for multicriteria
MaxSTSP.
Finally, we devise a deterministic 1/4 approximation algorithm
for
bicriteria MaxSTSP.
 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 fanin 2 which are in turn connected
with the
inputs. We also prove that the suboptimal circuits of this type
exhibit a
``stepped" behavior: any suboptimal 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 constantdepth circuits and the size
of proofs
in important proofsystems.
Recently, Shi and Zhu (2008), and Sherstov (2008) independently
introduced
two closely related techniques for proving lower bounds on 2party
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 kparty communication complexity of Disjointness as long
as k is a
constant. No superlogarithmic lower bounds were known previously
on the
threeparty 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 constantdepth 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 fixedvalues 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 constantdepth 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)
kMeans has Polynomial Smoothed Complexity
Abstract:
The kmeans 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 worstcase running time. In order to
close
the gap between practical performance and theoretical analysis, the
kmeans method has been studied in the model of smoothed analysis. But
even the smoothed analyses so far are unsatisfactory as the bounds are
still superpolynomial in the number n of data points.
We settle the smoothed running time of the kmeans 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 kmeans 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 polynomialtime 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 polynomialtime hierarchy is infinite there are no
subexponentialsize NPcomplete sets (BuhrnanHitchcock).
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 BodlaenderDowneyFellowsHermelin and HarnikNaor.
4 is from a CCC '08 paper by Buhrman and Hitchcock building on 3.


