Does co-NP have short interactive proofs? RB Boppana, J Hastad, S Zachos Information Processing Letters 25 (2), 127-132, 1987 | 522 | 1987 |
Eigenvalues and graph bisection: An average-case analysis RB Boppana 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), 280-285, 1987 | 503 | 1987 |
Approximating maximum independent sets by excluding subgraphs R Boppana, MM Halldórsson BIT Numerical Mathematics 32 (2), 180-196, 1992 | 491 | 1992 |
The monotone circuit complexity of Boolean functions N Alon, RB Boppana Combinatorica 7, 1-22, 1987 | 438 | 1987 |
The complexity of finite functions RB Boppana, M Sipser Algorithms and complexity, 757-804, 1990 | 434 | 1990 |
The average sensitivity of bounded-depth circuits RB Boppana Information processing letters 63 (5), 257-261, 1997 | 151 | 1997 |
Amplification of probabilistic Boolean formulas R Boppana Advances in Computing Research 5, 1-26, 1989 | 94* | 1989 |
The Complexity of Finite Functions, in “The Handbook of Theoretical Computer science”, Vol. A R Boppana, M Sipser Elsevier Science Publishers, 1990 | 81 | 1990 |
A useful elementary correlation inequality R Boppana, J Spencer Journal of Combinatorial Theory, Series A 50 (2), 305-307, 1989 | 71 | 1989 |
Optimal separations between concurrent-write parallel machines RB Boppana Proceedings of the twenty-first annual ACM symposium on Theory of computing …, 1989 | 67 | 1989 |
Pseudorandom Generators and Complexity Classes. RB Boppana, R Hirschfeld Adv. Comput. Res. 5, 1-26, 1989 | 63 | 1989 |
Threshold functions and bounded depth monotone circuits RB Boppana Proceedings of the sixteenth annual ACM symposium on Theory of computing …, 1984 | 55 | 1984 |
One-way functions and circuit complexity RB Boppana, JC Lagarias Information and Computation 74 (3), 226-240, 1987 | 52 | 1987 |
An asymptotic isoperimetric inequality N Alon, R Boppana, J Spencer Geometric & Functional Analysis GAFA 8 (3), 411-436, 1998 | 38 | 1998 |
Perfect-information leader election with optimal resilience RB Boppana, BO Narayanan SIAM Journal on Computing 29 (4), 1304-1320, 2000 | 37* | 2000 |
The biased coin problem RB Boppana, BO Narayanan Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing …, 1993 | 28 | 1993 |
MM Halld orsson R Boppana Approximating maximum independent sets by excluding subgraphs. BIT 32 (2 …, 1992 | 24 | 1992 |
The average-case parallel complexity of sorting RB Boppana Information Processing Letters 33 (3), 145-146, 1989 | 19 | 1989 |
Tomaszewski's problem on randomly signed sums: Breaking the 3/8 barrier RB Boppana, R Holzman arXiv preprint arXiv:1704.00350, 2017 | 11 | 2017 |
Randomness and Computation S Micali, FP Preparata, RB Boppana, GL Miller, JH Reif, S Goldwasser, ... JAI Press Ltd., 1989 | 10 | 1989 |