27. 4. a 19.5. 2010 (středa [Wednesday], 14:30, MÚ Žitná 25)
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.
