All reports by Author Jiri Sgall:

__
TR98-044
| 31st July 1998
__

Jiri Sgall#### Bounds on Pairs of Families with Restricted Intersections

__
TR97-042
| 22nd September 1997
__

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall#### Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

__
TR95-044
| 18th September 1995
__

Carsten Damm, Stasys Jukna, Jiri Sgall#### Some Bounds on Multiparty Communication Complexity of Pointer Jumping

__
TR95-010
| 16th February 1995
__

Pavel Pudlak, Jiri Sgall#### An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

Jiri Sgall

We study pairs of families ${\cal A},{\cal B}\subseteq

2^{\{1,\ldots,r\}}$ such that $|A\cap B|\in L$ for any

$A\in{\cal A}$, $B\in{\cal B}$. We are interested in the maximal

product $|{\cal A}|\cdot|{\cal B}|$, given $r$ and $L$. We give

asymptotically optimal bounds for $L$ containing only elements

of $s<q$ residue classes modulo ...
more >>>

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

Razborov~\cite{Razborov96} recently proved that polynomial

calculus proofs of the pigeonhole principle $PHP_n^m$ must have

degree at least $\ceiling{n/2}+1$ over any field. We present a

simplified proof of the same result. The main

idea of our proof is the same as in the original proof

of Razborov: we want to describe ...
more >>>

Carsten Damm, Stasys Jukna, Jiri Sgall

We introduce the model of conservative one-way multiparty complexity

and prove lower and upper bounds on the complexity of pointer jumping.

The pointer jumping function takes as its input a directed layered

graph with a starting node and layers of nodes, and a single edge ...
more >>>

Pavel Pudlak, Jiri Sgall

We prove an unexpected upper bound on a communication game proposed

by Jeff Edmonds and Russell Impagliazzo as an approach for

proving lower bounds for time-space tradeoffs for branching programs.

Our result is based on a generalization of a construction of Erdos,

Frankl and Rodl of a large 3-hypergraph ...
more >>>