The complexity of the Pigeonhole Principle
- Miklos Ajtai
- 1994
- Combinatorica
Paper
Publications
23 results at Combinatorica
The influence of large coalitions
- Miklós Ajtai
- Nathan Linial
- 1993
- Combinatorica
PaperBalancing extensions via Brunn-Minkowski
- Jeff Kahn
- Nathan Linial
- 1991
- Combinatorica
PaperApproximate Inclusion-Exclusion
- Nathan Linial
- Noam Nisan
- 1990
- Combinatorica
PaperConstructing disjoint paths on expander graphs
- David Peleg
- E. Upfal
- 1989
- Combinatorica
PaperA lower bound for finding predecessors in Yao's cell probe model
- Miklos Ajtai
- 1988
- Combinatorica
PaperA lower bound on strictly non-blocking networks
- J. Friedman
- 1988
- Combinatorica
PaperA random 1-011-011-01algorithm for depth first search
- Alok Aggarwal
- R.J. Anderson
- 1988
- Combinatorica
PaperBounds on the convex label number of trees
- Marshall Bern
- Alice Wong
- et al.
- 1987
- Combinatorica
PaperThe monotone circuit complexity of boolean functions
- Noga Alon
- Ravi B. Boppana
- 1987
- Combinatorica
Paper