## Předchozí program semináře, letní semestr 2008 [Previous program, Spring 2008]

**13. 5. 2008 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**, velká posluchárna v přízemí)

Harry Buhrman and John M.
Hitchcock: NP-Hard Sets are Exponentially Dense Unless coNP ⊆
NP/poly. CCC 2008.

(referuje Michal Koucký)

**Abstract**. We show that hard sets S for NP must have
exponential density,
i.e. |S_{=n}| ≥ 2^{nε} for some
ε > 0 and infinitely many n, unless coNP ⊆ NP\poly and
the polynomial-time hierarchy collapses. This result holds for Turing
reductions that make n^{1-ε} queries.

In addition we study the instance complexity of NP-hard problems and
show that hard sets also have an exponential amount of instances that
have instance complexity n^{δ} for some δ > 0. This result
also holds for Turing reductions that make n^{1-ε} queries.

**6. 5., 20. 5. 2008 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**, velká posluchárna v přízemí)

**S. Aaronson and A. Wigderson. Algebrization: A
New Barrier in Complexity Theory**. STOC'2008. Conference
version.

(referuje Jiří Sgall)

**Abstract. **Any proof of P=?NP will have to overcome two
barriers: relativization and natural proofs. Yet over the last decade,
we have seen circuit lower bounds (for example, that PP does not have
linear-size circuits) that overcome both barriers simultaneously. So
the question arises of whether there is a third barrier to progress on
the central questions in complexity theory. In this paper we present
such a barrier, which we call algebraic relativization or
algebrization. The idea is that, when we relativize some complexity
class inclusion, we should give the simulating machine access not only
to an oracle A, but also to a low-degree extension of A over a finite
field or ring. We systematically go through basic results and open
problems in complexity theory to delineate the power of the new
algebrization barrier. First, we show that all known non-relativizing
results based on arithmetization do indeed algebrize. Second, we show
that almost all of the major open problems—including P versus NP, P
versus RP, and NEXP versus P/poly—will require non-algebrizing
techniques. In some cases algebrization seems to explain exactly why
progress stopped where it did: for example, why we have superlinear
circuit lower bounds for PromiseMA but not for NP.

**22. 4., 29.4. 2008 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**, velká posluchárna v přízemí)

**A. A. Sherstov:
Separating
AC_0 from depth-2 majority circuits.
**STOC 2007.

(referuje Tomáš Ebenlendr)

Abstract. We construct a function in AC0 that cannot be computed by a
depth-2 majority circuit of size less than exp((n1/5)). This solves an
open problem due to Krause and Pudl´ak (1994) and matches Allender’s
classic result (1989) that AC0 can be efficiently simulated by depth-3
majority circuits. To obtain our result, we develop a novel technique
for proving lower bounds on communication complexity. This technique,
the Degree/Discrepancy Theorem, is of independent interest. It
translates lower bounds on the threshold degree of a Boolean function
into upper bounds on the discrepancy of a related function. Upper
bounds on the discrepancy, in turn, immediately imply lower bounds on
communication and circuit size. In particular, our work yields the
first known function in AC0 with exponentially small discrepancy,
exp(−(n1/5)).

**15. 4. 2008 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**, velká posluchárna v přízemí)

**
L. Fortnow and R. Santhanam.
Infeasibility
of instance compression and succinct PCPs for NP**. STOC 2008.

(referuje Ondřej Zajíček)

**Abstract: **The OR-SAT problem asks, given Boolean formulae
phi_1,...,phi_m each of size at most n, whether at least one of the
phi_i's is satisable. We show that there is no reduction from OR-SAT to
any set A where the length of the output is bounded by a polynomial in
n, unless NP Time Hierarchy collapses. This result settles an open
problem proposed by Bodlaender et. al. [4] and Harnik and Naor [15] and
has a number of implications.**
8. 4. 2008 **(úterý [Tuesday],

(referuje Tomáš Dzetkulič)

**25. 3., 1. 4. 2008 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**, velká posluchárna v přízemí)

**Sergey Yekhanin: New Locally Decodable Codes and Private
Information Retrieval Schemes**. ECCC
TR06-127

**Prasad Raghavendra: A Note on Yekhanin's Locally Decodable Codes**.
ECCC
TR07-016

(referuje Tomáš Ebenlendr)

**18. 3. 2008 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**, velká posluchárna v přízemí)

**Laplante, Lee, Szegedy: The quantum adversary method and
classical formula size lower bounds**

(referuje Pavel Pudlák)

Nenechte se odradit "kvantovou metodou". Bude se jednat o klasicke
odhady pro formulovou slozitost zalozene na jistych algebraickych
normach na obdelnicich. Je to zajmiave v souvislosti s normami, ktere
jsme zkoumali, protoze jejich metoda udajne pokryva vsechny dosavadni
dolni odhady pro formulovou slozitost.

Pavel Pudlák: Exponential
Separation of Quantum and Classical Non-Interactive Multi-Party
Communication Complexity

(joint work with D. Gavinski - dokončení)

**26. 2., 11. 3. 2008 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**, velká posluchárna v přízemí)

Pavel Pudlák: Exponential
Separation of Quantum and Classical Non-Interactive Multi-Party
Communication Complexity

(joint work with D. Gavinski)