The weekly Theory seminar provides an opportunity to get exposed to
cutting edge research in theoretical computer science, to learn to
understand technical material from talks and to give technical
presentations. Graduate students interested in doing research in
algorithms, complexity theory, cryptography, quantum
computing and related areas are strongly encouraged to attend.

All talks will be at 2:30 pm on Mondays in 203 Leonhard Building (unless they
are part of the departmental colloquium). Any unusual date/time/location is highlighted in the schedule.

If you would like to speak,
please email us at: theory [at] cse [dot] psu [dot] edu.

If you want to receive announcements of upcoming talks, please
join the theory
mailing list.

The speaker will be presenting new (probably optimal) results on monotonicity
testing for functions with hypercube ({0,1}^d) and hypergrid
({1,..,n}^d ) domain. Monotonicity testing is a problem that lies in the
realm of property testing of functions where one has to decide with high
probability of correctness, if the given function satisfies the property
or is "far" from it, i.e. one has to change a lot of points to make it
satisfy the property. The tester is allowed to sample only a sublinear
number of input points and query those. Recently, Chakrabarty and
Seshadhri have shown in STOC '13 the optimal results for hypercube and
hypergrid domain when the points are distributed according to the
uniform distribution.

The speaker will show the results when the points are sampled according to some
product distribution. If the distribution is known for hypergrid domain,
our tester will test with high probability whether the function is
monotone or is \epsilon-far from it, by querying O(H/\epsilon) points. Here
"H" is the Shannon entropy of distribution.

Also, the domain is hypercube and if the distribution is unknown then
our tester will have the query complexity O(d/\epsilon), which matches
the query complexity of the optimal tester for the uniform distribution.

Large Neighborhood Local Search for the Maximum Set Packing Problem

The speaker will talk about the paper,
Maxim Sviridenko and Justin Ward, Large Neighborhood Local Search for the Maximum
Set Packing Problem. ICALP (1) 2013: 792-803.

In this paper authors consider the classical maximum set packing problem where set cardinality
is upper bounded by k. They show how to design a variant of a polynomial-time local search
algorithm with performance guarantee (k + 2)/3. This local search algorithm is a special
case of a more general procedure that allows to swap up to Theta(log n) elements per iteration.
They also design problem instances with locality gap k/3 even for a wide class of exponential
time local search procedures, which can swap up to cn elements for a constant c. This shows
that their analysis of this class of algorithms is almost tight.

Space Lower Bounds for Random Formulae in Algebraic Proof Systems

The study of space measure in Proof Complexity has a gained in the last
years
more and more importance: first it is clearly of theoretical importance
in the study of complexity of proofs;
second it is connected with SAT solving, since it might provide
theoretical explanations of efficiency or inefficiency of
specific Theorem Provers or SAT-solvers; finally it is connected with
important characterizations studied in Finite Model Theory, thus
providing a solid link between the two research fields.

In the talk we will present a recent work where we devise a new
general combinatorial framework for proving space
lower bounds in algebraic proof systems like Polynomial Calculus (PC) and
Polynomial Calculus with Resolution (PCR). Our method can be view as a
Spoiler-Duplicator game, which is capturing boolean reasoning on
polynomials. Hence, for the first time, we move the problem of
studying the space complexity for algebraic proof systems in the range
of 2-players games, as is the case for Resolution. This can be seen as a
first step towards a precise
characterization of the space for algebraic systems in terms of
combinatorial games, like
Ehrenfeucht-Fraisse , which are used in Finite Model Theory.

A simple application of our method allows us to obtain all the
currently known space lower bounds for PCR, like the Pigeonhole
Principle. But more importantly, using our approach in its full
potentiality, we answer to the open problem of proving space lower
bounds in Polynomial Calculus and Polynomials Calculus with Resolution
for the polynomial encoding of randomly chosen $k$-CNF formulas. Our
method also applies to the the well studied Graph Pigeonhole Principle
which is a Pigeonhole principle over a constant (left) degree bipartite
expander graph.

In the talk we will discuss a number of important open problems which
arise form our works which might be
solved generalizing our approach.