Aduri Pavan

CoRR, 2024

Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024

Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024

Total Variation Distance Meets Probabilistic Inference.

[BibT_eX]

[DOI]

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Regularized Unconstrained Weakly Submodular Maximization.

[BibT_eX]

[DOI]

Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, 2024

Fairness in Monotone k-submodular Maximization: Algorithms and Applications.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference on Big Data, 2024

2023

Model Counting Meets F0 Estimation.

[BibT_eX]

[DOI]

N. Variyam Vinodchandran

Arnab Bhattacharyya

Kuldeep S. Meel

ACM Trans. Database Syst., September, 2023

Model Counting Meets Distinct Elements.

[BibT_eX]

[DOI]

Commun. ACM, September, 2023

Total Variation Distance Estimation Is as Easy as Probabilistic Inference.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma.

[BibT_eX]

[DOI]

CoRR, 2023

Brief Announcement: Relations Between Space-Bounded and Adaptive Massively Parallel Computations.

[BibT_eX]

[DOI]

Michael Chen

Proceedings of the 37th International Symposium on Distributed Computing, 2023

Maximizing submodular functions under submodular constraints.

[BibT_eX]

[DOI]

Madhavan R. Padmanabhan

Proceedings of the Uncertainty in Artificial Intelligence, 2023

Size-constrained k-submodular maximization in near-linear time.

[BibT_eX]

[DOI]

Christopher John Quinn

Proceedings of the Uncertainty in Artificial Intelligence, 2023

List and Certificate Complexities in Replicable Learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

On Approximating Total Variation Distance.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Constraint Optimization over Semirings.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

Model Counting Meets Distinct Elements in a Data Stream.

[BibT_eX]

[DOI]

SIGMOD Rec., 2022

The Geometry of Rounding.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Pseudodeterminism: promises and lowerbounds.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Promise Problems Meet Pseudodeterminism.

[BibT_eX]

[DOI]

Peter Dixon

Electron. Colloquium Comput. Complex., 2021

Model Counting meets F0 Estimation.

[BibT_eX]

[DOI]

CoRR, 2021

Model Counting meets F0 Estimation.

[BibT_eX]

[DOI]

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

Complete Problems for Multi-Pseudodeterministic Computations.

[BibT_eX]

[DOI]

Peter Dixon

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Multi-Objective Submodular Optimization with Approximate Oracles and Influence Maximization.

[BibT_eX]

[DOI]

Xiaoyun Fu

Rishabh Rajendra Bhatt

Proceedings of the 2021 IEEE International Conference on Big Data (Big Data), 2021

2020

Disrupting Diffusion: Critical Nodes in Network.

[BibT_eX]

[DOI]

Proceedings of the IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, 2020

Perfect Zero Knowledge: New Upperbounds and Relativized Separations.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 18th International Conference, 2020

Measuring the Impact of Influence on Individuals: Roadmap to Quantifying Attitude.

[BibT_eX]

[DOI]

Xiaoyun Fu

Madhavan R. Padmanabhan

Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2020

2019

A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

2018

On Pseudodeterministic Approximation Algorithms.

[BibT_eX]

[DOI]

Peter Dixon

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Influence Maximization in Social Networks With Non-Target Constraints.

[BibT_eX]

[DOI]

Madhavan R. Padmanabhan

Naresh Somisetty

Neeraj Kavassery-Parakkat

Proceedings of the IEEE International Conference on Big Data (IEEE BigData 2018), 2018

Improved Triangle Counting in Graph Streams: Power of Multi-Sampling.

[BibT_eX]

[DOI]

Kiana Mousavi Hanjani

Proceedings of the IEEE/ACM 2018 International Conference on Advances in Social Networks Analysis and Mining, 2018

2016

A thirty Year old conjecture about promise problems.

[BibT_eX]

[DOI]

Comput. Complex., 2016

Budgeted testing through an algorithmic lens.

[BibT_eX]

[DOI]

Myra B. Cohen

Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2016

A Note on the Advice Complexity of Multipass Randomized Logspace.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Computing triangle and open-wedge heavy-hitters in large networks.

[BibT_eX]

[DOI]

Proceedings of the 2016 IEEE International Conference on Big Data (IEEE BigData 2016), 2016

2015

On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape.

[BibT_eX]

[DOI]

Debasis Mandal

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

On the NP-Completeness of the Minimum Circuit Size Problem.

[BibT_eX]

[DOI]

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis.

[BibT_eX]

[DOI]

Debasis Mandal

Rajeswari Venugopalan

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

2013

Counting and Sampling Triangles from a Graph Stream.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2013

Length-Increasing Reductions for PSPACE-Completeness.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability.

[BibT_eX]

[DOI]

Proceedings of the 28th Conference on Computational Complexity, 2013

Parallel triangle counting in massive streaming graphs.

[BibT_eX]

[DOI]

Kanat Tangwongsan

Srikanta Tirthapura

Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, 2013

2012

On the power of unambiguity in log-space.

[BibT_eX]

[DOI]

Raghunath Tewari

Comput. Complex., 2012

Space-efficient estimation of statistics over sub-sampled streams.

[BibT_eX]

[DOI]

Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

A Thirty Year Old Conjecture about Promise Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Unions of Disjoint NP-Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010

On the Power of Unambiguity in Logspace.

[BibT_eX]

[DOI]

Raghunath Tewari

Electron. Colloquium Comput. Complex., 2010

Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses.

[BibT_eX]

[DOI]

Xiaoyang Gu

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009

The Fault Tolerance of NP-Hard Problems.

[BibT_eX]

[DOI]

Christian Glaßer

Stephen D. Travers

Proceedings of the Language and Automata Theory and Applications, 2009

Kolmogorov Complexity in Randomness Extraction.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

2008

Splitting NP-Complete Sets.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Partial Bi-immunity, Scaled Dimension, and NP-Completeness.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2008

Proving SAT does not have small circuits with an application to the two queries problem.

[BibT_eX]

[DOI]

Samik Sengupta

J. Comput. Syst. Sci., 2008

2-Local Random Reductions to 3-Valued Functions.

[BibT_eX]

[DOI]

Comput. Complex., 2008

2007

Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Range-Efficient Counting of Distinct Elements in a Massive Data Stream.

[BibT_eX]

[DOI]

Srikanta Tirthapura

SIAM J. Comput., 2007

Robustness of PSPACE-complete sets.

[BibT_eX]

[DOI]

Fengming Wang

Inf. Process. Lett., 2007

Strong Reductions and Isomorphism of Complete Sets.

[BibT_eX]

[DOI]

Ryan C. Harkins

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

2006

Mitosis in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2006

Redundancy in Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

Comparing Reductions to NP-Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Some Results on Average-Case Hardness Within the Polynomial Hierarchy.

[BibT_eX]

[DOI]

Rahul Santhanam

Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

2005

Resource-bounded strong dimension versus resource-bounded category.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2005

Autoreducibility, Mitoticity, and Immunity.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

Range Efficient Computation of F0 over Massive Data Streams.

[BibT_eX]

[DOI]

Srikanta Tirthapura

Proceedings of the 21st International Conference on Data Engineering, 2005

Relations Between Average-Case and Worst-Case Complexity.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2004

Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Partial Bi-Immunity and NP-Completeness

[BibT_eX]

[DOI]

Pramodchandran N. Variyam

Electron. Colloquium Comput. Complex., 2004

Hardness Hypotheses, Derandomization, and Circuit Complexity.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

Partial Bi-immunity and NP-Completeness.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Properties of NP-Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Some Results on Derandomization.

[BibT_eX]

[DOI]

Harry Buhrman

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Proving SAT does not have Small Circuits with an Application to the Two.

[BibT_eX]

[DOI]

Samik Sengupta

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Bi-Immunity Separates Strong NP-Completeness Notions.

[BibT_eX]

[DOI]

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

On Higher Arthur-Merlin Classes.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001

Separation of NP-Completeness Notions.

[BibT_eX]

[DOI]

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Complete distributional problems, hard languages, and resource-bounded measure.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

1999

Reductions Do Not Preserve Fast Convergence Rates in Average Time.

[BibT_eX]

[DOI]

Jay Belanger

Jie Wang

Algorithmica, 1999

On the Hardness of Permanent.

[BibT_eX]

[DOI]

Jin-yi Cai

D. Sivakumar

Proceedings of the STACS 99, 1999

Distributionally-Hard Languages.

[BibT_eX]

[DOI]