Logic and Complexity Student Seminar

Logic & Complexity Student Seminar/Reading Group (2015/2016)

Location: MFF UK - Sokolovska 83, 186 75 Praha 8 (3rd floor, room 358).
Time: Tuesday 2pm.

Reference	Date	Speaker
On the Constant-Depth Complexity of k-Clique [Rossman, 2008]	October 13	Igor Oliveira
Lower Bounds in a Parallel Model without Bit Operations [Mulmuley, 1999].	October 20	Bruno Loff
Proof Complexity Generators	October 27	Jan Krajicek
Pseudorandomness and Explicit Constructions: Part I (References: [BKSSW, 2010] [BRSW, 2012])	November 3	Jan Hladky
Pseudorandomness and Explicit Constructions: Part II (References: [BKSSW, 2010] [BRSW, 2012])	November 10	Jan Hladky
[Public Holiday]	November 17	-
An Exponential Lower Bound for a Constraint Propagation Proof System Based on OBDDs [Krajicek, 2008]	November 24	Mateus de Oliveira Oliveira
The KRW Composition Conjecture (References: [KRW, 1995] [GMWW, 2015])	December 1	Igor Oliveira and Bruno Loff
Bounded Arithmetic: Part I	December 8	Amir Tabatabai
Bounded Arithmetic: Part II	December 15	Amir Tabatabai
Some Consequences of Cryptographical Conjectures for S12 and EF [Krajicek and Pudlak, 1998]	January 12	Raheleh Jalali

Additional works that have been suggested by the participants:

Finite Functions and the Necessary use of Large Cardinals [H. Friedman, 1998].

The Average Sensitivity of Bounded-Depth Formulas [B. Rossman, 2015].

The PCP Theorem by Gap Amplification [I. Dinur, 2007].

Correlation Bounds for Poly-Size AC^0 Circuits with n^{1 - o(1)} Symmetric Gates [S. Lovett and S. Srinivasan, 2011].

Deterministic Communication Versus Partition Number [M. Goos, T. Pitassi, and T. Watson, 2015].

Multiparty Communication Complexity and Threshold Circuit Size of AC^0 [P. Beame and T. Huynh, 2012].

Correlation Bounds against Monotone NC^1 [B. Rossman, 2015].

Amplifying Lower Bounds by Means of Self-Reducibility [E. Allender and M. Koucky, 2010].

Top-Down Lower Bounds for Depth-Three Circuits [J. Hastad, S. Jukna, and P. Pudlak, 1995].

Random Walks that Find Perfect Objects and the Lovasz Local Lemma [D. Achlioptas and F. Iliopoulos, 2014].

Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries [A. Atserias, 2006].

On Uniformity and Circuit Lower Bounds [R. Santhanam and R. Williams, 2014].

Uniform Proofs of ACC Representations [S. Buss, 2015].

Rectangles are Nonnegative Juntas [M. Goos, S. Lovett, R. Meka, T. Watson, D. Zuckerman, 2014].

Consequences of the Provability of NP \subseteq P/poly [S. Cook and J. Krajicek, 2007].

Simplified Separation of Information and Communication [A. Rao and M. Sinha, 2015].

The Monotone Complexity of k-Clique on Random Graphs [B. Rossman, 2014].

The Complexity of Proving that a Gaph is Ramsey [M. Lauria, P. Pudlak, V. Rodl, and N. Thapen, 2013].

Expansions of Pseudofinites Structures and Circuit and Proof Complexity [J. Krajicek, 2015].

Short Proofs are Narrow - Resolutation Made Simple [E. Ben-Sasson and A. Wigderson, 2001].

Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution [A. Razborov, 2015].

Structured Pigeonhole Principle, Search Problems and Hard Tautologies [J. Krajicek, 2005].

Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold [D. Achlioptas and C. Moore, 2006].

Homomorphism Preservation Theorems [B. Rossman, 2008].

Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic [J. Krajicek, 1997].

Random Graphs and the Parity Quantifier [P. Kolaitis and S. Kopparty, 2013].

On the Complexity of Finding Narrow Proofs [C. Berkholz, 2012].

A Form of Feasible Interporlation for Constant Depth Frege Systems [J. Krajicek, 2010].

Determinism versus Nondeterminism with Arithmetic Tests and Computation [M. Ajtai, 2012].

On the Method of Approximations [A. Razborov, 1989].

Faster All-Pairs Shortest Paths via Circuit Complexity [R. Williams, 2014].

Limits on Alternation Trading Proofs for Time-Space Lower Bounds [S. Buss and R. Williams, 2015].

Propositinal Proof Systems, the Consistency of First-Order Theories and the Complexity of Computations [J. Krajicek and P. Pudlak, 1989].

Explicit Two-Source Extractors and Resilient Functions [E. Chattopadhyay and D. Zuckerman, 2015].

If you have questions or would like to suggest a reference, please contact Igor C. Oliveira.