Oznámení o seminářích se distribuuje pomocí mailing listu, do
kterého se
můžete zapsat na adrese
http://list.math.cas.cz/listinfo/complexity-seminar.
27. 4. a 19.5. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25, seminární místnost v přízemí zadní budovy)
Pavel Pudlák: On pseudorandom generators for read-once permutation branching programs of constant width
Abstract: I will report on the progress we have achieved working on this problem with Michal Koucký and Prajakta Nimbhorkar.
12. 5. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25
Frank J. Hall (Georgia State University, Atlanta, USA): Some Connections Between Boolean and Nonnegative Sign Pattern Matrices
Abstract: A {nonnegative sign pattern matrix} is a matrix whose entries are from the set $\{+, 0\}$. A nonnegative sign pattern matrix can also be viewed as a Boolean matrix, by replacing each + entry with 1. In this talk, some interesting connections between nonnegative sign pattern matrices and Boolean matrices are investigated. In particular, the relations between the minimum rank, the Boolean row (or column) rank, and the Schein rank are explored. The idempotent Boolean matrices that allow idempotence are also identified.
14. 3. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25
Dmitry Gavinsky (NEC Research, Princeton): Quantum Fingerprints that Keep Secrets
Abstract: A quantum fingerprinting scheme is a mapping that translates a binary string of length n to a quantum state over d qubits, d<<n, such that given any string y one can measure the fingerprint of x in order to decide, with high accuracy, whether x=y.
Very efficient classical fingerprinting schemes are known; however, it cat be seen that a classical scheme cannot hide information about x (the recipient of a fingerprint learns a lot about x). We show that this limitation can be overcome by quantum schemes. One of our quantum schemes will be presented and analysed during the talk.
Joint work with Tsuyoshi Ito from the University of Waterloo.
14. 4. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25)
Raghu Meka and David Zuckerman: Small-Bias Spaces for Group Products
(referuje Prajakta Nimbhorkar)
Abstract: Small-bias, or eps-biased, spaces have found many applications in complexity theory, coding theory, and derandomization. We generalize the notion of small-bias spaces to the setting of group products. Besides being natural, our extension captures some of the difficulties in constructing pseudorandom generators for constant-width branching programs - a longstanding open problem. We provide an efficient deterministic construction of small-bias spaces for solvable groups. Our construction exploits the fact that solvable groups have nontrivial normal subgroups that are abelian and builds on the construction of Azar et al. [AMN98] for abelian groups. For arbitrary finite groups, we give an efficient deterministic construction achieving constant bias. We also construct pseudorandom generators fooling linear functions mod p for primes p.
31. 3. a 7.4. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25)
Eyal Rozenman, Salil Vadhan: Derandomized Squaring of Graphs Contact
(referuje Michal Koucký)
Abstract: We introduce a "derandomized" analogue of graph squaring. This operation increases the connectivity of the graph (as measured by the second eigenvalue) almost as well as squaring the graph does, yet only increases the degree of the graph by a constant factor, instead of squaring the degree. One application of this product is an alternative proof of Reingold's recent breakthrough result that S-T Connectivity in Undirected Graphs can be solved in deterministic logspace.
24. 3. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25)
Prajakta Nimbhorkar (Institute of Mathematical Sciences, Chennai, India): A log-space algorithm for planar graph isomorphism
Abstract: Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and important special case by presenting an upper bound that matches the known log-space hardness [JKMT03]. In fact, we show the formally stronger result that planar graph canonization is in log-space. This improves the previously known upper bound of AC1 [MR91].
Our algorithm first constructs the biconnected component tree of a connected planar graph and then refines each biconnected component into a triconnected component tree. The next step is to log-space reduce the biconnected planar graph isomorphism and canonization problems to those for 3-connected planar graphs, which are known to be in log-space by [DLN08]. This is achieved by using the above decomposition, and by making modifications to Lindell's algorithm for tree canonization, along with changes in the space complexity analysis. The reduction from the connected case to the biconnected case requires further new ideas, including a case analysis and a group theoretic lemma to bound the number of automorphisms of a colored 3-connected planar graph. This lemma is crucial for the reduction to work in log-space.
Joint work with Samir Datta, Nutan Limaye, Thomas Thierauf and Fabian Wagner.
10. 3. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25, seminární místnost v přízemí zadní budovy)
Bounded depth circuit lower bounds
(referuje Pavel Pudlák)
Abstract: I will recall some earlier lower bounds on the size of small depth circuits.
13. 1. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25)
Mark Braverman:
Poly-logarithmic independence fools AC0 circuits
(referuje Pavel Pudlák)
Abstract: We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan (1990). The only prior progress on the problem was by Bazzi (2007), who showed that O(log^2 n)- independent distributions fool poly-size DNF formulas. Razborov (2008) has later given a much simpler proof for Bazzi's theorem.
16. 12. 2009 a 5.1.2010 (středa [Wednesday], 14:30, MÚ Žitná 25)
Nati Linial, Yishay Mansour and Noam Nisan:
Constant-depth circuits, Fourier transform and learnability
(referuje Iddo Tzameret)
Abstract: Boolean functions in ACO are studied using the harmonic analysis of the cube. The main result is that an ACO Boolean function has almost all of its power spectrum on the low-order coefficients. This result implies the following properties of functions in ACO: functions in ACO have low average sensitivity; they can be approximated well be a real polynomial of low degree; they cannot be pseudorandom function generators and their correlation with any polylog-wide independent probability distribution is small. An O(n^polylog(n))-time algorithm for learning functions in ACO is obtained. The algorithm observed the behavior of an ACO function on O(n^polylog(n)) randomly chosen inputs and derives a good approximation for the Fourier transform of the function. This allows it to predict with high probability the value of the function on other randomly chosen inputs.
2. a 9. 12. 2009 (středa [Wednesday], 14:30, MÚ Žitná 25)
Noam Nisan and Mario Szegedy:
On The Degree of Boolean Functions as Real Polynomials
(referuje Sebastian Muller)
Abstract: Every boolean function may be represented as a real polynomial. In this paper we characterize the de gree of this polynomial in terms of certain combinatorial properties of the boolean function. Our first result is a tight lower bound of \Omega(log n) on the degree needed to represent any boolean function that depends on n variables. Our second result states that for every boolean function f the following measures are all polynomially related:
25. 11. 2009 (středa [Wednesday], 14:30, MÚ Žitná 25)
Neil Thapen: Hastad's Switching Lemma II
Abstract: We prove the switching lemma for a different, less uniform, family of random restrictions that is designed to collapse Sipser functions by at most one level. This gives an exponential separation between depth k and depth k-1 circuits.
18. 11. 2009 (středa [Wednesday], 14:30, MÚ Žitná 25)
Neil Thapen: Hastad's Switching Lemma
Abstract: We show that no small constant depth circuit can compute parity, using Hastad's switching lemma that under a random restriction, with high probability an OR of small ANDs can be decided by a short decision tree. We give a simplified proof, based on a combination of Hastad's and Razborov's proofs.
11. 11. 2009 (středa [Wednesday], 14:30, MÚ Žitná 25)
Russell Impagliazzo (IAS Princeton and UC San Diego, host KA): Algorithmic Dense Model Theorems and Weak Regularity
Abstract: Green and Tao used a Dense Model Theorem to prove that there are arbitrarily long arithmetic progressions in the primes. The Dense Model Theorem says, intuitively, that for any class of tests, and any subset of a universe, either there is a test that ``witnesses'' that the subset is small or a large set indistinguishable from that subset. Reingold, Trevisan, Tulsiani and Vadhan gave a translation of the original Dense Model Theorem into complexity theroretic terms, and gave an improved construction (also provided by Gowers). Here, we show that the Dense Model Theorem follows directly from the Hardcore Set Theorem (Impagliazzo '95, as improved by Holenstein '05). Using the boosting based proof of the Hardcore Set Theorem, we obtain constructive and algorithmic versions. We give general decompostion theorems, along the lines of Trevisan, Tulsiani, and Vadhan '09. We use a decompostion theorem to give an improved version of the Weak Graph Regularity Theorem of Frieze and Kannan in the case of graphs of moderate density (or pseudo-density.)
4. 11. 2009 (středa [Wednesday], 14:30, MÚ Žitná 25)
Roman Smolensky: Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity
(referuje Michal Koucký)
Abstract: I will present the argument of Razborov and Smolensky that shows that bounded depth polynomial size circuits consisting of unbounded fan-in AND, OR and MOD-q gates cannot compute MOD-p if p and q are distinct primes.
14. a 21. 10. 2009 (středa [Wednesday], 14:30, MÚ Žitná 25)
James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich:
The Expressive Power of Voting Polynomials
(referuje Pavel Pudlák)
Abstract: We consider the problem of approximating a Boolean function
Vince Grolmusz:
Superpolynomial Size Set-Systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs
