**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.