Aduri Pavan

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 25

Top Topics

Influence Maximization

Constraint Optimization

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Aduri Pavan, Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel
On the Feasibility of Forgetting in Data Streams. Proc. ACM Manag. Data 2 (2) (2024)
Aduri Pavan, Kuldeep S. Meel, N. V. Vinodchandran, Arnab Bhattacharyya
Constraint Optimization over Semirings. CoRR (2023)
Jason Vander Woude, Peter Dixon, Aduri Pavan, Jamie Radcliffe, N. V. Vinodchandran
Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma. CoRR (2023)
Peter Dixon, Aduri Pavan, Jason Vander Woude, N. V. Vinodchandran
List and Certificate Complexities in Replicable Learning. NeurIPS (2023)
Aduri Pavan, Kuldeep S. Meel, N. V. Vinodchandran, Arnab Bhattacharyya
Constraint Optimization over Semirings. AAAI (2023)
Madhavan R. Padmanabhan, Yanhui Zhu, Samik Basu, Aduri Pavan
Maximizing submodular functions under submodular constraints. UAI (2023)
Peter Dixon, Aduri Pavan, Jason Vander Woude, N. V. Vinodchandran
Pseudodeterminism: promises and lowerbounds. STOC (2022)
Jason Vander Woude, Peter Dixon, Aduri Pavan, Jamie Radcliffe, N. V. Vinodchandran
Geometry of Rounding. CoRR (2022)
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, Aduri Pavan, N. V. Vinodchandran
On Approximating Total Variation Distance. CoRR (2022)
Xiaoyun Fu, Rishabh Rajendra Bhatt, Samik Basu, Aduri Pavan
Multi-Objective Submodular Optimization with Approximate Oracles and Influence Maximization. IEEE BigData (2021)
Aduri Pavan, N. V. Vinodchandran, Arnab Bhattacharya, Kuldeep S. Meel
Estimation. PODS (2021)
Peter Dixon, Aduri Pavan, N. V. Vinodchandran
Promise Problems Meet Pseudodeterminism. Electron. Colloquium Comput. Complex. 28 (2021)
Aduri Pavan, N. V. Vinodchandran, Arnab Bhattacharyya, Kuldeep S. Meel
Model Counting meets F0 Estimation. CoRR (2021)
Peter Dixon, Aduri Pavan, N. V. Vinodchandran
Promise Problems Meet Pseudodeterminism. CoRR (2021)
Raj Gaurav Kumar, Preeti Bhardwaj, Samik Basu, Aduri Pavan
Disrupting Diffusion: Critical Nodes in Network. WI/IAT (2020)
Peter Dixon, Sutanu Gayen, Aduri Pavan, N. V. Vinodchandran
Perfect Zero Knowledge: New Upperbounds and Relativized Separations. TCC (1) (2020)
Xiaoyun Fu, Madhavan Rajagopal Padmanabhan, Raj Gaurav Kumar, Samik Basu, Shawn Dorius, Aduri Pavan
Measuring the Impact of Influence on Individuals: Roadmap to Quantifying Attitude. CoRR (2020)
Xiaoyun Fu, Madhavan R. Padmanabhan, Raj Gaurav Kumar, Samik Basu, Shawn Dorius, Aduri Pavan
Measuring the Impact of Influence on Individuals: Roadmap to Quantifying Attitude. ASONAM (2020)
Peter Dixon, Aduri Pavan, N. V. Vinodchandran
On Pseudodeterministic Approximation Algorithms. MFCS (2018)
Andrew Hughes, Debasis Mandal, Aduri Pavan, Nathan Russell, Alan L. Selman
A thirty Year old conjecture about promise problems. Comput. Complex. 25 (4) (2016)
Peter Dixon, Debasis Mandal, Aduri Pavan, N. V. Vinodchandran
A Note on the Advice Complexity of Multipass Randomized Logspace. MFCS (2016)
Aduri Pavan, Paul Quint, Stephen D. Scott, N. V. Vinodchandran, J. Smith
Computing triangle and open-wedge heavy-hitters in large networks. IEEE BigData (2016)
Myra B. Cohen, Aduri Pavan, N. V. Vinodchandran
Budgeted testing through an algorithmic lens. SIGSOFT FSE (2016)
John M. Hitchcock, Aduri Pavan
On the NP-Completeness of the Minimum Circuit Size Problem. FSTTCS (2015)
Debasis Mandal, Aduri Pavan, N. V. Vinodchandran
On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape. MFCS (2) (2015)
Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. Variyam Vinodchandran, Lin F. Yang
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. Electron. Colloquium Comput. Complex. 21 (2014)
Ryan C. Harkins, John M. Hitchcock, Aduri Pavan
Strong Reductions and Isomorphism of Complete Sets. Comput. 3 (2) (2014)
Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin F. Yang
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. FSTTCS (2014)
Debasis Mandal, Aduri Pavan, Rajeswari Venugopalan
Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis. FSTTCS (2014)
Christian Glaßer, John M. Hitchcock, Aduri Pavan, Stephen D. Travers
Unions of Disjoint NP-Complete Sets. ACM Trans. Comput. Theory 6 (1) (2014)
Debasis Mandal, Aduri Pavan, Rajeswari Venugopalan
Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis. Electron. Colloquium Comput. Complex. 21 (2014)
John M. Hitchcock, Aduri Pavan
Length-Increasing Reductions for PSPACE-Completeness. MFCS (2013)
Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, Osamu Watanabe
An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability. Computational Complexity Conference (2013)
Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran
On the power of unambiguity in log-space. Comput. Complex. 21 (4) (2012)
Andrew Hughes, Aduri Pavan, Nathan Russell, Alan L. Selman
A Thirty Year Old Conjecture about Promise Problems. ICALP (1) (2012)
Xiaoyang Gu, John M. Hitchcock, Aduri Pavan
Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses. Theory Comput. Syst. 51 (2) (2012)
Christian Glaßer, John M. Hitchcock, Aduri Pavan, Stephen D. Travers
Unions of Disjoint NP-Complete Sets. COCOON (2011)
John M. Hitchcock, Aduri Pavan, N. Variyam Vinodchandran
Kolmogorov Complexity in Randomness Extraction. ACM Trans. Comput. Theory 3 (1) (2011)
Christian Glaßer, Aduri Pavan, Stephen D. Travers
The fault tolerance of NP-hard problems. Inf. Comput. 209 (3) (2011)
Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang
Extracting Kolmogorov complexity with applications to dimension zero-one laws. Inf. Comput. 209 (4) (2011)
Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran
On the Power of Unambiguity in Logspace CoRR (2010)
Xiaoyang Gu, John M. Hitchcock, Aduri Pavan
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses. STACS (2010)
Xiaoyang Gu, John M. Hitchcock, Aduri Pavan
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses CoRR (2010)
Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran
On the Power of Unambiguity in Logspace. Electron. Colloquium Comput. Complex. 17 (2010)
Christian Glaßer, Aduri Pavan, Stephen D. Travers
The Fault Tolerance of NP-Hard Problems. LATA (2009)
John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran
Kolmogorov Complexity in Randomness Extraction. FSTTCS (2009)
John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran
Kolmogorov Complexity in Randomness Extraction. Electron. Colloquium Comput. Complex. 16 (2009)
John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran
Partial Bi-immunity, Scaled Dimension, and NP-Completeness. Theory Comput. Syst. 42 (2) (2008)
Aduri Pavan, N. V. Vinodchandran
2-Local Random Reductions to 3-Valued Functions. Comput. Complex. 17 (4) (2008)
Lance Fortnow, Aduri Pavan, Samik Sengupta
Proving SAT does not have small circuits with an application to the two queries problem. J. Comput. Syst. Sci. 74 (3) (2008)
John M. Hitchcock, Aduri Pavan
Hardness Hypotheses, Derandomization, and Circuit Complexity. Comput. Complex. 17 (1) (2008)
Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
Splitting NP-Complete Sets. SIAM J. Comput. 37 (5) (2008)
Aduri Pavan, N. V. Vinodchandran
Relations between Average-Case and Worst-Case Complexity. Theory Comput. Syst. 42 (4) (2008)
John M. Hitchcock, Aduri Pavan
Comparing reductions to NP-complete sets. Inf. Comput. 205 (5) (2007)
Aduri Pavan, Fengming Wang
Robustness of PSPACE-complete sets. Inf. Process. Lett. 103 (3) (2007)
Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang
Autoreducibility, mitoticity, and immunity. J. Comput. Syst. Sci. 73 (5) (2007)
Aduri Pavan, Alan L. Selman, Samik Sengupta, N. V. Vinodchandran
Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy. Theor. Comput. Sci. 385 (1-3) (2007)
Ryan C. Harkins, John M. Hitchcock, Aduri Pavan
Strong Reductions and Isomorphism of Complete Sets. FSTTCS (2007)
Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
Mitosis in Computational Complexity. TAMC (2006)
John M. Hitchcock, Aduri Pavan
Comparing Reductions to NP-Complete Sets. Electron. Colloquium Comput. Complex. 13 (039) (2006)
Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. ICALP (1) (2006)
Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
Redundancy in Complete Sets. STACS (2006)
Aduri Pavan, Rahul Santhanam, N. V. Vinodchandran
Some Results on Average-Case Hardness Within the Polynomial Hierarchy. FSTTCS (2006)
Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta
Properties of NP-Complete Sets. SIAM J. Comput. 36 (2) (2006)
John M. Hitchcock, Aduri Pavan
Comparing Reductions to NP-Complete Sets. ICALP (1) (2006)
John M. Hitchcock, Aduri Pavan
Hardness Hypotheses, Derandomization, and Circuit Complexity. Electron. Colloquium Comput. Complex. 13 (071) (2006)
Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang
Autoreducibility, Mitoticity, and Immunity. MFCS (2005)
Aduri Pavan, Srikanta Tirthapura
over Massive Data Streams. ICDE (2005)
Aduri Pavan, N. V. Vinodchandran
Relations Between Average-Case and Worst-Case Complexity. FCT (2005)
Harry Buhrman, Lance Fortnow, Aduri Pavan
Some Results on Derandomization. Theory Comput. Syst. 38 (2) (2005)
John M. Hitchcock, Aduri Pavan
Resource-bounded strong dimension versus resource-bounded category. Inf. Process. Lett. 95 (3) (2005)
Aduri Pavan, N. V. Vinodchandran
2-Local Random Reductions to 3-Valued Functions Electron. Colloquium Comput. Complex. (062) (2005)
Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang
Autoreducibility, Mitoticity, and Immunity Electron. Colloquium Comput. Complex. (011) (2005)
Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws Electron. Colloquium Comput. Complex. (105) (2005)
Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
Redundancy in Complete Sets Electron. Colloquium Comput. Complex. (068) (2005)
Aduri Pavan, Alan L. Selman
Bi-immunity separates strong NP-completeness notions. Inf. Comput. 188 (1) (2004)
Aduri Pavan, N. V. Vinodchandran
Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility Electron. Colloquium Comput. Complex. (053) (2004)
John M. Hitchcock, Aduri Pavan
Hardness Hypotheses, Derandomization, and Circuit Complexity. FSTTCS (2004)
Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta
Properties of NP-Complete Sets. Computational Complexity Conference (2004)
John M. Hitchcock, Aduri Pavan, Pramodchandran N. Variyam
Partial Bi-Immunity and NP-Completeness Electron. Colloquium Comput. Complex. (025) (2004)
Jin-yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta
On Higher Arthur-Merlin Classes. Int. J. Found. Comput. Sci. 15 (1) (2004)
John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran
Partial Bi-immunity and NP-Completeness. Computational Complexity Conference (2004)
Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta
Properties of NP-Complete Sets Electron. Colloquium Comput. Complex. (019) (2004)
Lance Fortnow, Aduri Pavan, Samik Sengupta
Proving SAT does not have Small Circuits with an Application to the Two. Computational Complexity Conference (2003)
Harry Buhrman, Lance Fortnow, Aduri Pavan
Some Results on Derandomization. STACS (2003)
Jin-yi Cai, Denis Charles, Aduri Pavan, Samik Sengupta
On Higher Arthur-Merlin Classes. COCOON (2002)
Aduri Pavan, Alan L. Selman
Bi-Immunity Separates Strong NP-Completeness Notions Electron. Colloquium Comput. Complex. (005) (2002)
Aduri Pavan, Alan L. Selman
Bi-Immunity Separates Strong NP-Completeness Notions. STACS (2002)
Aduri Pavan, Alan L. Selman
Separation of NP-Completeness Notions. SIAM J. Comput. 31 (3) (2001)
Aduri Pavan, Alan L. Selman
Separation of NP-Completeness Notions. Computational Complexity Conference (2001)
Aduri Pavan, Alan L. Selman
Separation of NP-completeness Notions Electron. Colloquium Comput. Complex. 8 (32) (2001)
Lance Fortnow, Aduri Pavan, Alan L. Selman
Distributionally Hard Languages. Theory Comput. Syst. 34 (3) (2001)
Aduri Pavan, Alan L. Selman
Complete distributional problems, hard languages, and resource-bounded measure. Theor. Comput. Sci. 234 (1-2) (2000)
Jay Belanger, Aduri Pavan, Jie Wang
Reductions Do Not Preserve Fast Convergence Rates in Average Time. Algorithmica 23 (4) (1999)
Jin-yi Cai, Aduri Pavan, D. Sivakumar
On the Hardness of Permanent. STACS (1999)
Lance Fortnow, Aduri Pavan, Alan L. Selman
Distributionally-Hard Languages. COCOON (1999)