Předchozí program semináře, zimní semestr 2008 [Previous program, Fall 2008]
27. 1. 2009 (úterý [Tuesday], 11:00, MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Nikolay Vereshchagin (Moscow State University): Useful
information
Abstract: Kolmogorov complexity measures the amount of information in a given large file, such as a text of a novel, a musical record etc. It does not judge whether the information is useful or not. Is it possible to define which part of a given file, say a musical record, is useful and which part is just a noise? Surprisingly, it is. In the talk I will present the definition of useful information given by Kolmogorov of 1974 and modern developments in this area.
13. 1. 2009 (úterý [Tuesday], 11:00, MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Zeev Dvir and Amir Shpilka.Towards
Dimension Expanders Over Finite Fields. CCC 2008.
(referuje Pavel Pudlák)
6. 1. 2009 (úterý [Tuesday], 11:00, MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Emanuele Viola: The sum of d
small-bias generators fools polynomials of degree d. CCC
2008 best paper award.
(referuje Jiří Sgall)
16. 12. 2008 (úterý [Tuesday], 11:00, MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Pavel Pudlák
2. 12., 9. 12. 2008 (úterý [Tuesday], 11:00, MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Russell Impagliazzo , Ragesh Jaiswal, Valentine Kabanets, and
Avi
Wigderson:
Uniform Direct Product Theorems: Simplified, Optimized, and
Derandomized. STOC 2008.
(referuje Phuong Nguyen)
Abstract: The classical Direct-Product Theorem for circuits says that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard to compute on average by small circuits, then the corresponding $k$-wise direct product function $f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each $x_i\in\{0,1\}^n$) is significantly harder to compute on average by slightly smaller circuits. We prove a \emph{fully uniform} version of the Direct-Product Theorem with information-theoretically \emph{optimal} parameters, up to constant factors. Namely, we show that for given $k$ and $\epsilon$, there is an efficient randomized algorithm $A$ with the following property. Given a circuit $C$ that computes $f^k$ on at least $\epsilon$ fraction of inputs, the algorithm $A$ outputs with probability at least $3/4$ a list of $O(1/\epsilon)$ circuits such that at least one of the circuits on the list computes $f$ on more than $1-\delta$ fraction of inputs, for $\delta = O((\log 1/\epsilon)/k)$; moreover, each output circuit is an $\AC^0$ circuit (of size $\poly(n,k,\log 1/\delta,1/\epsilon)$), with oracle access to the circuit $C$.
Using the Goldreich-Levin decoding algorithm~\cite{GL89}, we also get a \emph{fully uniform} version of Yao's XOR Lemma~\cite{Yao} with \emph{optimal} parameters, up to constant factors. Our results simplify and improve those in~\cite{IJK06}.
Our main result may be viewed as an efficient approximate, local, list-decoding algorithm for direct-product codes (encoding a function by its values on all $k$-tuples) with optimal parameters. We generalize it to a family of ``derandomized" direct-product codes, which we call {\em intersection codes}, where the encoding provides values of the function only on a subfamily of $k$-tuples. The quality of the decoding algorithm is then determined by sampling properties of the sets in this family and their intersections. As a direct consequence of this generalization we obtain the first derandomized direct product result in the uniform setting, allowing hardness amplification with only constant (as opposed to a factor of $k$) increase in the input length. Finally, this general setting naturally allows the decoding of concatenated codes, which further yields nearly optimal derandomized amplification.
25. 11. 2008 (úterý [Tuesday], 11:00, MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Andreas Björklund, Thore Husfeldt, and Mikko Koivisto:
Set
partitioning via inclusion–exclusion.
SIAM J. Comput., Special Issue for FOCS 2006.
(referuje Jiří Sgall)
Abstract: Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2^n*n^O(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimisation versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in 2^n*n^O(1) time for several well-studied partition problems including Domatic Number, Chromatic Number, Maximum k-Cut, Bin Packing, List Colouring, and the Chromatic Polynomial. If only polynomial space is available, our algorithms run in time 3^n*n^O(1) if membership in F can be decided in polynomial time. We solve Chromatic Number in O(2.2461^n) time and Domatic Number in O(2.8718^n) time.
18. 11. 2008 (úterý [Tuesday], 11:00, MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Patrick Traxler: The Time Complexity of Constraint
Satisfaction
(referuje Mohan Paturi)
Abstract: We study the time complexity of (d,k)-CSP,
the problem of deciding satisfiability of a constraint system 
with n variables, domain
size d, and at most k variables per constraint. We are
interested in the question how the domain size d influences the
complexity of deciding satisfiability. We show, assuming the
Exponential Time Hypothesis, that two special cases, namely (d,2)-CSP
with bounded variable frequency and d-UNIQUE-CSP, already
require exponential time Ω(d c·n )
for some c > 0 independent of d.
UNIQUE-CSP is the special case for which it is guaranteed that every
input constraint system has at most 1 satisfying assignment.
11. 11. 2008 (úterý [Tuesday], 11:00,
MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Lance Fortnow, Rahul Santhanam: Infeasibility of Instance
Compression and Succinct PCPs for NP. ECCC
Report TR07-096.
(referuje Michal Koucký)
Abstract: We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there is a polynomial-time computable function $f$ and a set $A$ such that for each instance $x$ of $L$, $f(x)$ is of size polynomial in the {it witness size} of $x$, and $f$ reduces $L$ to $A$. We prove that SAT is not instance compressible unless NP is contained in coNP/poly, and the Polynomial Hierarchy collapses. This result settles an open problem posed by [Harnik-Naor06] and [Downey07], and has a number of implications: 1. A number of parametric NP problems, including SAT, Clique, DominatingSet and IntegerProgramming, are not polynomially kernelizable unless NP is contained in coNP/poly. 2. SAT does not have "succinct PCPs", i.e., PCPs of size polynomial in the number of variables, unless NP is contained in coNP/poly. 3. An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is inviable in its present form. 4. (Burhman) There are no sub-exponential size complete sets for NP or coNP unless NP is contained in coNP/poly.
4. 11. 2008 (úterý [Tuesday], 11:00, MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Ramamohan Paturi (UC San Diego, CA, USA): Computational Models
with Nontrivial Upper bounds for Satisfiability
Abstract: In this talk, we explore which computational models have nontrivial upper bounds for satisfiability. We show that certain versions of depth-3 unbounded fan-in circuits have nontrivial upper bounds for satisfiability. We also exhibit a connection between Pi Sigma k-CNF and k-CNF formulas with regards to the complexity of solving the satisfiability problem.
30. 10. 2008 (čtvrtek [Thursday], 10:00,
MÚ Žitná 25, posluchárna v přízemí zadní budovy)
Zvi Lotker (Ben-Gurion University, Israel): Rent, Lease or Buy:
Randomized Algorithms for Multislope Ski Rental.
(joint work with Boaz Patt-Shamir and Dror Rawitz)
Abstract: In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost ("buying price"), and cost proportional to the duration of the usage ("rental rate"). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best option at any point in time. Multislope Ski Rental is a natural generalization of the classical Ski Rental problem (where the only options are pure rent and pure buy), which is one of the fundamental problems of online computation. The Multislope Ski Rental problem is an abstraction of many problems where online decisions cannot be modeled by just two options, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for Multislope Ski Rental. Our results include the best possible online randomized strategy for any additive instance, where the cost of switching from one option to another is the difference in their buying prices; and an algorithm that produces an e-competitive randomized strategy for any (non-additive) instance.
21. 10. 2008 (úterý [Tuesday], 11:00,
MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Klim Efremenko: 3-Query Locally Decodable Codes of
Subexponential
Length. ECCC
Report TR08-069.
(referuje Ondřej Zajíček)
Abstract: Locally Decodable Codes (LDC) allow one to decode
any particular
symbol of the input message by making a constant number of queries to a
codeword, even if a constant fraction of the codeword is damaged. In
recent work ~cite{Yekhanin08} Yekhanin constructs a $3$-query LDC with
sub-exponential length of size $exp(exp(O(frac{log n}{loglog n})))$.
However, this construction requires a conjecture that there are
infinity many Mersenne primes. In this paper we give an unconditional
$3$-query LDC construction with shorter codeword length of
$exp(exp(O(sqrt{log n log log n })))$. We also give a $2^r$-query LDC
with length of $exp(exp(O(sqrt[r]{log n log log^{r-1} n })))$. The main
ingredient in our construction is the existence of super-polynomial
size set-systems with restricted intersections cite{Grolmusz00} which
holds only over composite numbers.
14. 10. 2008 (úterý [Tuesday], 11:00,
MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Michal Koucký: How to Explore
a Fast-Changing World
(joint work with Chen Avin and Zvi Lotker)
Abstract: Motivated by real world networks and use of algorithms based on random walks on these networks we study the simple random walks on dynamic undirected graphs, i.e., graphs which are modified by inserting or deleting edges at every step of the walk. We are interested in the expected time needed to visit all the vertices of such a dynamic graph, the cover time, under the assumption that the graph is being modified by an oblivious adversary. It is well known that on static undirected graphs the cover time is polynomial in the size of the graph, on the contrary and somewhat counter-intuitively, we show that there are adversary strategies which force the expected cover time of dynamic graphs to be exponential, and relate this result to the cover time of static directed graphs. In addition we provide a simple strategy, the lazy random walk, that guarantees polynomial cover time regardless of the changes made by the adversary.
7. 10. 2008 (úterý [Tuesday], 11:00, MÚ Žitná 25, seminární místnost v prvním patře zadní budovy)
Dima Gavinski: Quantum and Classical Communication Complexity
Abstract: We give a brief overview of results demonstrating advantages of the quantum communication model over the classical one. We concentrate on two recent results showing that classical interactive communication is sometimes exponentially weaker than (1) quantum 1-way communication, and (2) classical simultaneous message passing with shared entanglement. No prior knowledge of quantum communication complexity is assumed.