| Does co-NP have short interactive proofs? RB Boppana, J Hastad, S Zachos Information Processing Letters 25 (2), 127-132, 1987 | 523 | 1987 |
| Approximating maximum independent sets by excluding subgraphs R Boppana, MM Halldórsson BIT Numerical Mathematics 32 (2), 180-196, 1992 | 514 | 1992 |
| Eigenvalues and graph bisection: An average-case analysis RB Boppana 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), 280-285, 1987 | 513 | 1987 |
| The monotone circuit complexity of Boolean functions N Alon, RB Boppana Combinatorica 7, 1-22, 1987 | 445 | 1987 |
| The complexity of finite functions RB Boppana, M Sipser Algorithms and complexity, 757-804, 1990 | 439 | 1990 |
| The average sensitivity of bounded-depth circuits RB Boppana Information processing letters 63 (5), 257-261, 1997 | 155 | 1997 |
| Amplification of probabilistic Boolean formulas R Boppana Advances in Computing Research 5, 1-26, 1989 | 92* | 1989 |
| The Complexity of Finite Functions, in “The Handbook of Theoretical Computer science”, Vol. A R Boppana, M Sipser Elsevier Science Publishers, 1990 | 79 | 1990 |
| A useful elementary correlation inequality R Boppana, J Spencer Journal of Combinatorial Theory, Series A 50 (2), 305-307, 1989 | 74 | 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 | 54 | 1984 |
| One-way functions and circuit complexity RB Boppana, JC Lagarias Information and Computation 74 (3), 226-240, 1987 | 51 | 1987 |
| An asymptotic isoperimetric inequality N Alon, R Boppana, J Spencer Geometric & Functional Analysis GAFA 8 (3), 411-436, 1998 | 40 | 1998 |
| Perfect-information leader election with optimal resilience RB Boppana, BO Narayanan SIAM Journal on Computing 29 (4), 1304-1320, 2000 | 39* | 2000 |
| The biased coin problem RB Boppana, BO Narayanan Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing …, 1993 | 29 | 1993 |
| MM Halld orsson R Boppana Approximating maximum independent sets by excluding subgraphs. BIT 32 (2 …, 1992 | 25 | 1992 |
| The average-case parallel complexity of sorting RB Boppana Information Processing Letters 33 (3), 145-146, 1989 | 18 | 1989 |
| Simple and local independent set approximation RB Boppana, MM Halldórsson, D Rawitz International Colloquium on Structural Information and Communication …, 2018 | 11 | 2018 |
| Tomaszewski's problem on randomly signed sums: Breaking the 3/8 barrier RB Boppana, R Holzman arXiv preprint arXiv:1704.00350, 2017 | 11 | 2017 |
Magnús M. HalldórssonProfessor of Computer Science, Reykjavik UniversityDirección de correo verificada de ru.is