slideshow 3

Complexity seminar

usually takes place each Friday at 13:30 in IM, rear building, ground floor
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

Entropy extractors for small zero fixing sources

Pavel Pudlák
IM
Friday, 11. January 2019 - 13:30 to 15:00
in IM, rear building, ground floor

A (k,n)-zero fixing source X is given by a subset S of [n] of size k. The source X produces 0-1 vectors that are zero outside of S each with probability 2^{-k}. An extractor for a (k,n)-zero fixing source is a mapping F:{0,1}^n\to {0,1}^l such that F(X) is close to the uniform distribution on {0,1}^l. Such extractors are known for k down to log log n with l=k-O(1). In this talk we will show some constructions for k << log log n and some upper bounds on the amount of entropy that is possible to extract for small k.

These problems are closely connected with Ramsey theory.

Joint work with Vojtěch Rodl.

The layer complexity of Arthur-Merlin-like communication

Dmitry Gavinsky
IM CAS
Friday, 4. January 2019 - 13:30 to 15:00

in IM, rear building, ground floor

In communication complexity the Arthur-Merlin (AM) model is the most natural one that allows both randomness
and non-determinism. Presently we do not have any super-logarithmic lower bound for the AM-complexity of an
explicit function. Obtaining such a bound is a fundamental challenge to our understanding of communication
phenomena. In this work we explore the gap between the known techniques and the complexity class AM.

In the first part we define a new natural class Small-advantage Layered Arthur-Merlin (SLAM) that have the
following properties:
    - SLAM is (strictly) included in AM and includes all previously known sub-AM classes with non-trivial
lower bounds.
    - SLAM is qualitatively stronger than the union of those classes.
    - SLAM is a subject to the discrepancy bound: in particular, the inner product function does not have an
efficient SLAM-protocol.

Structurally this can be summarised as
SBP... more

Hardness magnification near state-of-the-art lower bounds

Jan Pich
Oxford University
Friday, 14. December 2018 - 13:30 to 15:00

in IM, rear building, ground floor

We continue the development of hardness magnification, a strategy for deriving strong circuit
lower bounds by reducing them to a refined analysis of weaker models proposed by Oliveira and Santhanam
(2018). Specifically, we consider a gap version of the meta-computational problem MCSP which asks to
distinguish truth-tables of Boolean functions of small circuit complexity from truth-tables of a
slightly larger complexity and establish that a small improvement over the state-of-the-art lower bounds
in a variety of computational models for the gap version of MCSP would imply explicit super-polynomial
lower bounds.

This talk is based on a joint work with Igor C.Oliveira and Rahul Santhanam.

An exposition of R. Williams' "Strong ETH Breaks with Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation".

Navid Talebanfard
IM
Friday, 7. December 2018 - 13:30 to 15:00

in IM, rear building, ground floor

Variants are the Strong Exponential Time Hypothesis have been proposed. In this talk I sketch Williams'
result which asserts that Strong ETH fails when we have both non-determinism and randomization. The proof
uses arithmetization and polynomial arguments.

Pages