Volume 19; Issue 3

Combinatorica

Volume 19; Issue 3
1

Superpolynomial Lower Bounds for Monotone Span Programs

László Babai, Anna Gál, Avi Wigderson
Journal:
Combinatorica
Year:
1999
Language:
english
File:
PDF, 290 KB
english, 1999
2

Isomorphism of Coloured Graphs with Slowly Increasing Multiplicity of Jordan Blocks

Sergei Evdokimov, Ilia Ponomarenko
Journal:
Combinatorica
Year:
1999
Language:
english
File:
PDF, 228 KB
english, 1999
3

A Sublinear Bipartiteness Tester for Bounded Degree Graphs

Oded Goldreich, Dana Ron
Journal:
Combinatorica
Year:
1999
Language:
english
File:
PDF, 443 KB
english, 1999
4

Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules

Tom Leighton, Bruce Maggs, Andréa W. Richa
Journal:
Combinatorica
Year:
1999
Language:
english
File:
PDF, 364 KB
english, 1999
5

Separation of the Monotone NC Hierarchy

Ran Raz, Pierre McKenzie
Journal:
Combinatorica
Year:
1999
Language:
english
File:
PDF, 371 KB
english, 1999
6

Perfect Matchings in ε-Regular Graphs and the Blow-Up Lemma

Vojtech Rödl, Andrzej Ruciński
Journal:
Combinatorica
Year:
1999
Language:
english
File:
PDF, 278 KB
english, 1999