An ?(n 5/4) lower bound on the randomized complexity of graph properties
- 1 March 1991
- journal article
- research article
- Published by Springer Nature in Combinatorica
- Vol. 11 (1) , 23-32
- https://doi.org/10.1007/bf01375470
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- Lower bounds to randomized algorithms for graph propertiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- A topological approach to evasivenessCombinatorica, 1984
- Further results on the Aanderaa-Rosenberg conjectureJournal of Combinatorial Theory, Series B, 1980
- Edge disjoint placement of graphsJournal of Combinatorial Theory, Series B, 1978
- Probabilistic computations: Toward a unified measure of complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- On recognizing graph properties from adjacency matricesTheoretical Computer Science, 1976
- On the time required to recognize properties of graphsACM SIGACT News, 1973
- On the theory of graphsColloquium Mathematicum, 1954