Sanjeev Khanna
Orcid: 0009-0000-2601-1689Affiliations:
- University of Pennsylvania, Philadelphia, PA, USA
According to our database1,
Sanjeev Khanna
authored at least 225 papers
between 1990 and 2024.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2018, "For contributions to approximation algorithms, hardness of approximation, and sublinear algorithms".
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:
-
on id.loc.gov
On csauthors.net:
Bibliography
2024
CoRR, 2024
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024
2023
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023
2022
Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022
2021
SIAM J. Comput., 2021
Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling.
Math. Program., 2021
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection.
CoRR, 2021
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021
Proceedings of the 29th Annual European Symposium on Algorithms, 2021
2020
ACM Trans. Algorithms, 2020
Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020
Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020
Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions.
Proceedings of the 37th International Conference on Machine Learning, 2020
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
2019
ACM Trans. Economics and Comput., 2019
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019
2018
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
2017
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
Proceedings of the 2017 ACM Conference on Economics and Computation, 2017
StreamQRE: modular specification and efficient evaluation of quantitative queries over streaming data.
Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2017
Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons.
Proceedings of the 30th Conference on Learning Theory, 2017
2016
Future Gener. Comput. Syst., 2016
Algorithmic Finance, 2016
Proceedings of the Web and Internet Economics - 12th International Conference, 2016
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016
Proceedings of the 35th Annual IEEE International Conference on Computer Communications, 2016
Proceedings of the 19th International Conference on Database Theory, 2016
Proceedings of the Data Stream Management - Processing High-Speed Data Streams, 2016
2015
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
Proceedings of the IEEE International Conference on Robotics and Automation, 2015
Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches.
Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015
2014
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Proceedings of the Machine Learning and Interpretation in Neuroimaging, 2014
Proceedings of the Language and Automata Theory and Applications, 2014
Proceedings of the Integer Programming and Combinatorial Optimization, 2014
Layer Decomposition: An Effective Structure-Based Approach for Scientific Workflow Similarity.
Proceedings of the 10th IEEE International Conference on e-Science, 2014
Proceedings of the IEEE 27th Computer Security Foundations Symposium, 2014
2013
SIAM J. Comput., 2013
SIAM J. Comput., 2013
Proceedings of the Algorithms and Models for the Web Graph - 10th International Workshop, 2013
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013
Proceedings of the In Search of Elegance in the Theory and Practice of Computation, 2013
2012
Adaptive Selective Verification: An Efficient Adaptive Countermeasure to Thwart DoS Attacks.
IEEE/ACM Trans. Netw., 2012
An O(k<sup>3</sup>log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.
Theory Comput., 2012
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012
Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012
2011
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011
Compression without a common prior: an information-theoretic justification for ambiguity in language.
Proceedings of the Innovations in Computer Science, 2011
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
Proceedings of the Fifth Biennial Conference on Innovative Data Systems Research, 2011
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011
Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011
2010
ACM Trans. Algorithms, 2010
CoRR, 2010
Proceedings of the Internet and Network Economics - 6th International Workshop, 2010
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2010
Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games.
Proceedings of the Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), 2010
Proceedings of the Behavioral and Quantitative Game Theory, 2010
2009
ACM Trans. Algorithms, 2009
Algorithmica, 2009
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009
Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2009
Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009
Proceedings of the 25th International Conference on Data Engineering, 2009
An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
2008
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008
Proceedings of the 7th International Conference on Information Processing in Sensor Networks, 2008
Proceedings of the INFOCOM 2008. 27th IEEE International Conference on Computer Communications, 2008
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
2007
J. Comput. Biol., 2007
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs.
Electron. Colloquium Comput. Complex., 2007
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007
2006
An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow.
Theory Comput., 2006
Electron. Colloquium Comput. Complex., 2006
Proceedings of the Distributed Computing, 20th International Symposium, 2006
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
2005
SIAM J. Comput., 2005
J. ACM, 2005
Comput. Vis. Image Underst., 2005
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005
2004
Proceedings of the Handbook of Scheduling - Algorithms, Models, and Performance Analysis., 2004
A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem.
SIAM J. Discret. Math., 2004
J. Comput. Syst. Sci., 2004
Proceedings of the Algorithmic Foundations of Robotics VI, 2004
Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004
Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004
Proceedings of the Network and Distributed System Security Symposium, 2004
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004
2003
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems.
J. Comput. Syst. Sci., 2003
Electron. Colloquium Comput. Complex., 2003
Algorithmica, 2003
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003
2002
Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002
2001
Electron. Colloquium Comput. Complex., 2001
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
Approximation algorithms for the metric labeling problem via a new linear programming formulation.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001
Proceedings of the 2001 ACM SIGMOD international conference on Management of data, 2001
Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS 2001), 2001
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001
Proceedings of the Database Theory, 2001
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001
Complexity classifications of Boolean constraint satisfaction problems.
SIAM monographs on discrete mathematics and applications 7, SIAM, ISBN: 978-0-89871-479-1, 2001
2000
Electron. Colloquium Comput. Complex., 2000
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000
1999
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Proceedings IEEE INFOCOM '99, 1999
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
1998
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998
Proceedings of the Proceedings IEEE INFOCOM '98, The Conference on Computer Communications, Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, Gateway to the 21st Century, San Francisco, CA, USA, March 29, 1998
1997
Chic. J. Theor. Comput. Sci., 1997
Bell Labs Tech. J., 1997
A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997
1996
Electron. Colloquium Comput. Complex., 1996
A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction
Electron. Colloquium Comput. Complex., 1996
Electron. Colloquium Comput. Complex., 1996
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996
1995
J. Parallel Distributed Comput., 1995
1992
Multiprocessor Architectures for High Speed Networks: A Performance Study.
Proceedings of the Algorithms, Software, Architecture, 1992
Concurrent Use of Parallel Communication to Enable Remote Visualization.
Proceedings of the Computing and Information, 1992
Parallel TCP/IP for Multiprocessor Workstations.
Proceedings of the High Performance Networking IV, 1992
1991
Comput. Commun. Rev., 1991
1990
Proceedings of the Advances in Computing and Information, 1990