Theory Seminar Schedule for Fall 2013
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.
| Date | Speaker | Title |
|---|---|---|
| Sep 2 | PSU holiday, no seminar | |
| Sep 9 | Kashyap Dixit | Monotonicity testing with product distributions |
| Sep 16 | Huiwen Yu | Large Neighborhood Local Search for the Maximum Set Packing Problem |
| Sep 23 | Nicola Galesi | Space Lower Bounds for Random Formulae in Algebraic Proof Systems |
- 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.
Monotonicity testing with product distributions
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.
Recent Comments