Ravi B. Boppana

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

Collaborative distances:

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

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

Simple and local independent set approximation.

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

Theor. Comput. Sci., 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

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

Electron. Colloquium Comput. Complex., 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

1996

The Biased Coin Problem.

Ravi B. Boppana, Babu O. Narayanan

SIAM J. Discret. Math., 1996

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

1992

Approximating Maximum Independent Sets by Excluding Subgraphs.

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

BIT, 1992

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

Amplification of Probabilistic Boolean Formulas.

Ravi B. Boppana

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

One-Way Functions and Circuit Complexity

Ravi B. Boppana, J. C. Lagarias

Inf. Comput., September, 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

Threshold Functions and Bounded Depth Monotone Circuits.

Ravi B. Boppana

J. Comput. Syst. Sci., 1986

1982

Some properties of Hueckel-type edge operators.

Ravi B. Boppana, Azriel Rosenfeld

Pattern Recognit. Lett., 1982