![]() |
|
Close Help |
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| ≥ 2nε 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 n1-ε 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 n1-ε 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], 14:00,
MÚ Žitná 25, velká posluchárna v přízemí)
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)