Ravi B. Boppana

According to our database, Ravi B. Boppana authored at least 26 papers between 1982 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2025

Approximating Independent Sets in Constant Distributed Rounds.

Ravi B. Boppana, Magnús M. Halldórsson

Proceedings of the Structural Information and Communication Complexity, 2025

2023

A Useful Inequality for the Binary Entropy Function.

Ravi B. Boppana

CoRR, 2023

2021

Tomaszewski's Problem on Randomly Signed sums, Revisited.

Ravi B. Boppana, Harrie Hendriks, Martien C. A. van Zuijlen

Electron. J. Comb., 2021

2020

The tree search game for two players.

Ravi B. Boppana, Joel Brewster Lewis

CoRR, 2020

2019

Bounded Independence versus Symmetric Tests.

Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

ACM Trans. Comput. Theory, 2019

2018

Simple and Local Independent Set Approximation.

Ravi B. Boppana, Magnús M. Halldórsson, Dror Rawitz

Proceedings of the Structural Information and Communication Complexity, 2018

Brief Announcement: Simple and Local Independent Set Approximation.

Ravi B. Boppana, Magnús M. Halldórsson, Dror Rawitz

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

2017

Tomaszewski's Problem on Randomly Signed Sums: Breaking the 3/8 Barrier.

Ravi B. Boppana, Ron Holzman

Electron. J. Comb., 2017

2016

Bounded Independence vs. Moduli.

Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

Proceedings of the Approximation, 2016

2000

Perfect-Information Leader Election with Optimal Resilience.

Ravi B. Boppana, Babu O. Narayanan

SIAM J. Comput., 2000

1997

The Average Sensitivity of Bounded-Depth Circuits.

Ravi B. Boppana

Inf. Process. Lett., 1997

1995

Smoothness laws for random ordered graphs.

Ravi Bopu Boppana, Joel Spencer

Proceedings of the Logic and Random Structures, 1995

1994

The Decision-Tree Complexity of Element Distinctness.

Ravi B. Boppana

Inf. Process. Lett., 1994

1993

The biased coin problem.

Ravi B. Boppana, Babu O. Narayanan

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1990

Approximating Maximum Independent Sets by Excluding Subgraphs.

Ravi B. Boppana, Magnús M. Halldórsson

Proceedings of the SWAT 90, 1990

The Complexity of Finite Functions.

Ravi B. Boppana, Michael Sipser

Proceedings of the Handbook of Theoretical Computer Science, 1990

1989

The Average-Case Parallel Complexity of Sorting.

Ravi B. Boppana

Inf. Process. Lett., 1989

Pseudorandom Generators and Complexity Classes.

Ravi B. Boppana, Rafael Hirschfeld

Adv. Comput. Res., 1989

Optimal Separations Between Concurrent-Write Parallel Machines

Ravi B. Boppana

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1987

Does co-NP Have Short Interactive Proofs?

Ravi B. Boppana, Johan Håstad, Stathis Zachos

Inf. Process. Lett., 1987

The monotone circuit complexity of Boolean functions.

Noga Alon, Ravi B. Boppana

Comb., 1987

Eigenvalues and Graph Bisection: An Average-Case Analysis (Extended Abstract)

Ravi B. Boppana

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986

One- Way Functions and Circuit Complexity.

Ravi B. Boppana, J. C. Lagarias

Proceedings of the Structure in Complexity Theory, 1986

1985

Amplification of Probabilistic Boolean Formulas

Ravi B. Boppana

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

Threshold Functions and Bounded Depth Monotone Circuits

Ravi B. Boppana

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1982

Some properties of Hueckel-type edge operators.

Ravi B. Boppana, Azriel Rosenfeld

Pattern Recognit. Lett., 1982