Sanjeev Khanna
Orcid: 0009000026011689Affiliations:
 University of Pennsylvania, Philadelphia, PA, USA
According to our database^{1},
Sanjeev Khanna
authored at least 222 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
CoRR, 2024
Proceedings of the 2024 ACMSIAM Symposium on Discrete Algorithms, 2024
Proceedings of the 2024 ACMSIAM Symposium on Discrete Algorithms, 2024
Proceedings of the 2024 ACMSIAM Symposium on Discrete Algorithms, 2024
2023
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023
Proceedings of the 2023 ACMSIAM Symposium on Discrete Algorithms, 2023
Proceedings of the 42nd ACM SIGMODSIGACTSIGAI 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 ACMSIAM 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, 25 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 SinkhornKnopp 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 ACMSIAM 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 2024, 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
Comb., 2019
A new algorithm for decremental singlesource shortest paths with applications to vertexcapacitated 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 ACMSIAM Symposium on Discrete Algorithms, 2019
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
A Simple SublinearTime Algorithm for Counting Arbitrary Subgraphs via Edge Sampling.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
Proceedings of the TwentyEighth International Joint Conference on Artificial Intelligence, 2019
2018
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
2017
ACM Trans. Economics and Comput., 2017
J. Sched., 2017
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017
Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, 2017
Proceedings of the TwentyEighth Annual ACMSIAM 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, MultiArmed 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
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model.
Proceedings of the TwentySeventh Annual ACMSIAM 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 HighSpeed Data Streams, 2016
2015
Internet Math., 2015
CoRR, 2015
Algorithmica, 2015
Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, 2015
Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, 2015
Proceedings of the TwentySixth Annual ACMSIAM 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 CutPreserving Sketches.
Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015
2014
ACM Trans. Database Syst., 2014
CoRR, 2014
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
Proceedings of the TwentyFifth Annual ACMSIAM 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 StructureBased Approach for Scientific Workflow Similarity.
Proceedings of the 10th IEEE International Conference on eScience, 2014
Proceedings of the IEEE 27th Computer Security Foundations Symposium, 2014
2013
SIAM J. Comput., 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 VertexConnectivity 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 TwentyThird Annual ACMSIAM 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
Proc. VLDB Endow., 2011
CoRR, 2011
Proceedings of the TwentySecond Annual ACMSIAM Symposium on Discrete Algorithms, 2011
Proceedings of the 30th ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems, 2011
Compression without a common prior: an informationtheoretic justification for ambiguity in language.
Proceedings of the Innovations in Computer Science, 2011
Proceedings of the Database Theory, 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
Nat. Comput., 2010
Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP
CoRR, 2010
CoRR, 2010
CoRR, 2010
Inapproximability of EdgeDisjoint Paths and low congestion routing on undirected graphs.
Comb., 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 (EC2010), 2010
2009
ACM Trans. Algorithms, 2009
SIAM J. Comput., 2009
J. ACM, 2009
CoRR, 2009
CoRR, 2009
CoRR, 2009
Algorithmica, 2009
Algorithmica, 2009
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009
Proceedings of the Twentieth Annual ACMSIAM Symposium on Discrete Algorithms, 2009
Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC2009), 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 Database Theory, 2009
Proceedings of the 25th International Conference on Data Engineering, 2009
An O(k^3 log n)Approximation Algorithm for VertexConnectivity 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
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
2008
Nat. Comput., 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
ACM Trans. Algorithms, 2007
J. Comput. Biol., 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
SIAM J. Discret. Math., 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
IEEE Trans. Robotics, 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 ACMSIAM 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
ACM Trans. Database Syst., 2004
SIAM J. Discret. Math., 2004
A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem.
SIAM J. Discret. Math., 2004
SIAM J. Comput., 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
Multiprocessor scheduling to minimize flow time with epsilon resource augmentation.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004
Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2004
Proceedings of the Fifteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2004
Proceedings of the Twentythird ACM SIGACTSIGMODSIGART 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
Nearoptimal hardness results and approximation algorithms for edgedisjoint paths and related problems.
J. Comput. Syst. Sci., 2003
Electron. Colloquium Comput. Complex., 2003
Electron. Colloquium Comput. Complex., 2003
Algorithmica, 2003
Proceedings of the Fourteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2003
2002
J. Comput. Syst. Sci., 2002
Proceedings of the Twentyfirst ACM SIGACTSIGMODSIGART 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 RealTime Systems Symposium (RTSS 2001), 2001
Proceedings of the Twentieth ACM SIGACTSIGMODSIGART 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: 9780898714791, 2001
2000
SIAM J. Comput., 2000
SIAM J. Comput., 2000
J. Comput. Syst. Sci., 2000
Comb., 2000
Proceedings of the Eleventh Annual ACMSIAM Symposium on Discrete Algorithms, 2000
Proceedings of the Eleventh Annual ACMSIAM Symposium on Discrete Algorithms, 2000
Proceedings of the Eleventh Annual ACMSIAM Symposium on Discrete Algorithms, 2000
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000
1999
SIAM J. Comput., 1999
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Proceedings IEEE INFOCOM '99, 1999
Proceedings of the Automata, 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
Algorithmica, 1998
Proceedings of the Ninth Annual ACMSIAM 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
IEEE Trans. Computers, 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 TwentyNinth Annual ACM Symposium on the Theory of Computing, 1997
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997
1996
PhD thesis, 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 TwentyEighth Annual ACM Symposium on the Theory of Computing, 1996
1995
J. Parallel Distributed Comput., 1995
Electron. Colloquium Comput. Complex., 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. J., 1991
Comput. Commun. Rev., 1991
1990
Proceedings of the Advances in Computing and Information, 1990