# Semináø z výpoèetní slo¾itosti

## Pavel Pudlák, Jiøí Sgall

### 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)

Abstract: We prove that the sum of d small-bias generators L fools degree-d polynomials in n variables over a prime field F, for any fixed degree d and field F, including F = F2 = {0, 1}. Our result builds on, simplifies, and improves on both the work by Bogdanov and Viola (FOCS ’07) and the beautiful follow-up by Lovett (STOC ’08). The first relies on a conjecture that turned out to be true only for some degrees and fields, while the latter considers the sum of 2d small-bias generators (as opposedto d in our result).

16. 12. 2008 (úterý [Tuesday], 11:00, MÚ ®itná 25, seminární místnost v prvním patøe zadní budovy)

Pavel Pudlák

Abstract: I will show a small result that we obtained with Mohan Paturi concerning the complexity of satisfiability. Roughly, we shall show thatcircuit satisfiability is either very hard or fairly easy.

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.