Concepedia

Randomized Query Complexity

Randomized Query Complexity is a complexity measure in computational complexity theory that quantifies the minimum expected number of queries a randomized algorithm must make to compute a function correctly with bounded error probability.

50

Publications

1.9K

Citations

96

Authors

54

Institutions

Publications per year

2017–2026

5

Parents

Publications

50

A Randomized Algorithm for Closest-Point Queries

Kenneth L. Clarkson · SIAM Journal on Computing · 1988 · 252 citations

, , +13

Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms

Chun Lam Chan, Pak Hou, Sidharth Jaggi et al. · 2011 · 151 citations

, , +12

Regular Languages are Testable with a Constant Number of Queries

Noga Alon, Michael Krivelevich, Ilan Newman et al. · SIAM Journal on Computing · 2001 · 121 citations

, , +15

Query complexity, or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?

Gábor Tardos · COMBINATORICA · 1989 · 82 citations

, , +14

Simple analysis of graph tests for linearity and PCP

Johan Håstad, Avi Wigderson · Random Structures and Algorithms · 2003 · 75 citations

, , +16

1–5 of 50

Authors

96

  1. MS
    Márió Szegedy

    Rutgers, The State University of New Jersey, United States

    3 publications · 196 citations

    3

    h-index

  2. IN
    Ilan Newman

    University of Haifa, Israel

    3 publications · 195 citations

    3

    h-index

  3. AA
    Andris Ambainis

    University of Latvia, Latvia

    3 publications · 109 citations

    3

    h-index

  4. NN
    Noam Nisan

    Hebrew University of Jerusalem, Israel

    3 publications · 58 citations

    3

    h-index

  5. MS
    Miklós Sántha

    Centre National de la Recherche Scientifique, France

    2 publications · 54 citations

    2

    h-index

1–5 of 96

Institutions

54

  1. Massachusetts Institute of Technology

    Cambridge, United States

    6 h-index

    9 publications

    325 citations

  2. Hebrew University of Jerusalem

    Jerusalem, Israel

    4 h-index

    6 publications

    169 citations

  3. Tel Aviv University

    Tel Aviv, Israel

    4 h-index

    6 publications

    204 citations

  4. Columbia University

    New York, United States

    3 h-index

    5 publications

    190 citations

  5. University of Latvia

    Riga, Latvia

    3 h-index

    6 publications

    202 citations

  6. National University of Singapore

    Singapore, Singapore

    2 h-index

    3 publications

    130 citations

  7. University of Pennsylvania

    Philadelphia, United States

    2 h-index

    4 publications

    76 citations

  8. Université Paris-Sud

    Orsay, France

    2 h-index

    3 publications

    81 citations

1–8 of 54

Venues

  1. SIAM Journal on Computing

    6 publications · 531 citations

    6

    h-index

  2. arXiv (Cornell University)

    Repository · 5 publications · 90 citations

    5

    h-index

  3. Information Processing Letters

    3 publications · 55 citations

    3

    h-index

  4. Theoretical Computer Science

    2 publications · 70 citations

    2

    h-index

  5. Symposium on Discrete Algorithms

    Conference · 2 publications · 76 citations

    2

    h-index

1–5