Ravi B. Boppana

33 papers A* 6B 2Journal 21Unranked 3
YearRankTypeTitle / Venue / Authors
2025 B conf
Approximating Independent Sets in Constant Distributed Rounds.
SIROCCO
Ravi B. Boppana, Magnús M. Halldórsson
2023 J jnl
A Useful Inequality for the Binary Entropy Function.
CoRR
Ravi B. Boppana
2021 J jnl
Tomaszewski's Problem on Randomly Signed sums, Revisited.
Electron. J. Comb.
Ravi B. Boppana, Harrie Hendriks, Martien C. A. van Zuijlen
2020 J jnl
Simple and local independent set approximation.
Theor. Comput. Sci.
Ravi B. Boppana, Magnús M. Halldórsson, Dror Rawitz
2020 J jnl
The tree search game for two players.
CoRR
Ravi B. Boppana, Joel Brewster Lewis
2019 J jnl
Bounded Independence versus Symmetric Tests.
ACM Trans. Comput. Theory
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
2018 A* conf
Brief Announcement: Simple and Local Independent Set Approximation.
PODC
Ravi B. Boppana, Magnús M. Halldórsson, Dror Rawitz
2018 B conf
Simple and Local Independent Set Approximation.
SIROCCO
Ravi B. Boppana, Magnús M. Halldórsson, Dror Rawitz
2018 J jnl
Simple and Local Independent Set Approximation.
CoRR
Ravi B. Boppana, Magnús M. Halldórsson, Dror Rawitz
2017 J jnl
Tomaszewski's Problem on Randomly Signed Sums: Breaking the 3/8 Barrier.
Electron. J. Comb.
Ravi B. Boppana, Ron Holzman
2016 — conf
Bounded Independence vs. Moduli.
APPROX-RANDOM
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
2016 J jnl
Bounded independence vs. moduli.
Electron. Colloquium Comput. Complex.
Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola
2000 J jnl
Perfect-Information Leader Election with Optimal Resilience.
SIAM J. Comput.
Ravi B. Boppana, Babu O. Narayanan
1997 J jnl
The Average Sensitivity of Bounded-Depth Circuits.
Inf. Process. Lett.
Ravi B. Boppana
1996 J jnl
The Biased Coin Problem.
SIAM J. Discret. Math.
Ravi B. Boppana, Babu O. Narayanan
1994 J jnl
The Decision-Tree Complexity of Element Distinctness.
Inf. Process. Lett.
Ravi B. Boppana
1993 A* conf
The biased coin problem.
STOC
Ravi B. Boppana, Babu O. Narayanan
1992 J jnl
Approximating Maximum Independent Sets by Excluding Subgraphs.
BIT
Ravi B. Boppana, Magnús M. Halldórsson
1990 — conf
Approximating Maximum Independent Sets by Excluding Subgraphs.
SWAT
Ravi B. Boppana, Magnús M. Halldórsson
1990 — ch.
The Complexity of Finite Functions.
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A)
Ravi B. Boppana, Michael Sipser
1989 J jnl
Amplification of Probabilistic Boolean Formulas.
Adv. Comput. Res.
Ravi B. Boppana
1989 A* conf
Optimal Separations Between Concurrent-Write Parallel Machines
STOC
Ravi B. Boppana
1989 J jnl
Pseudorandom Generators and Complexity Classes.
Adv. Comput. Res.
Ravi B. Boppana, Rafael Hirschfeld
1989 J jnl
The Average-Case Parallel Complexity of Sorting.
Inf. Process. Lett.
Ravi B. Boppana
1987 J jnl
Does co-NP Have Short Interactive Proofs?
Inf. Process. Lett.
Ravi B. Boppana, Johan Håstad, Stathis Zachos
1987 A* conf
Eigenvalues and Graph Bisection: An Average-Case Analysis (Extended Abstract)
FOCS
Ravi B. Boppana
1987 J jnl
One-Way Functions and Circuit Complexity
Inf. Comput.
Ravi B. Boppana, J. C. Lagarias
1987 J jnl
The monotone circuit complexity of Boolean functions.
Comb.
Noga Alon, Ravi B. Boppana
1986 — conf
One- Way Functions and Circuit Complexity.
SCT
Ravi B. Boppana, J. C. Lagarias
1986 J jnl
Threshold Functions and Bounded Depth Monotone Circuits.
J. Comput. Syst. Sci.
Ravi B. Boppana
1985 A* conf
Amplification of Probabilistic Boolean Formulas
FOCS
Ravi B. Boppana
1984 A* conf
Threshold Functions and Bounded Depth Monotone Circuits
STOC
Ravi B. Boppana
1982 J jnl
Some properties of Hueckel-type edge operators.
Pattern Recognit. Lett.
Ravi B. Boppana, Azriel Rosenfeld