Sanjeev Khanna | Academic Influence

Sanjeev Khanna's AcademicInfluence.com Rankings

Sanjeev Khanna

Computer Science

#1858

World Rank

#1929

Historical Rank

#888

USA Rank

Machine Learning

#3460

World Rank

#3503

Historical Rank

#150

USA Rank

Artificial Intelligence

#3760

World Rank

#3815

Historical Rank

#259

USA Rank

Database

#5451

World Rank

#5655

Historical Rank

#764

USA Rank

computer-science Degrees

Download Badge

Computer Science

Sanjeev Khanna's Degrees

PhD Computer Science Stanford University
Masters Computer Science Stanford University
Bachelors Computer Science Stanford University

Similar Degrees You Can Earn

Why Is Sanjeev Khanna Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Sanjeev Khanna is an Indian-American computer scientist. He is currently a Henry Salvatori professor of Computer and Information Science at the University of Pennsylvania. His research interests include approximation algorithms, hardness of approximation, combinatorial optimization, and sublinear algorithms.

(See a Problem?)

Sanjeev Khanna's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Why and Where: A Characterization of Data Provenance (2001) (1220)
Space-efficient online computation of quantile summaries (2001) (531)
Complexity classifications of Boolean constraint satisfaction problems (2001) (428)
On syntactic versus computational views of approximability (1994) (304)
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem (2005) (300)
A PTAS for the multiple knapsack problem (2000) (296)
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems (1999) (255)
Data Provenance: Some Basic Issues (2000) (253)
Differential Privacy: An Economic Method for Choosing Epsilon (2014) (243)
On propagation of deletions and annotations through views (2002) (230)
Randomized pursuit-evasion in a polygonal environment (2005) (217)
The Approximability of Constraint Satisfaction Problems (2001) (212)
On multi-dimensional packing problems (1999) (207)
On the Hardness of Approximating the Chromatic Number (1993) (205)
Approximation schemes for minimizing average weighted completion time with release dates (1999) (201)
Power-conserving computation of order-statistics over sensor networks (2004) (190)
Archiving scientific data (2002) (186)
On the communication and streaming complexity of maximum bipartite matching (2012) (150)
Approximation algorithms for the metric labeling problem via a new linear programming formulation (2001) (141)
Design networks with bounded pairwise distance (1999) (129)
Using the crowd for top-k and group-by queries (2013) (127)
Reconstructing strings from random traces (2004) (123)
On approximating rectangle tiling and packing (1998) (110)
The all-or-nothing multicommodity flow problem (2004) (108)
Distributed Private Heavy Hitters (2012) (107)
Algorithms for minimizing weighted flow time (2001) (106)
A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem (2005) (105)
Towards a syntactic characterization of PTAS (1996) (103)
Improved approximation results for stochastic knapsack problems (2011) (103)
On Allocating Goods to Maximize Fairness (2009) (101)
Page replacement for general caching problems (1999) (100)
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model (2016) (99)
Approximating matching size from random streams (2014) (96)
On the Hardness of Approximating Max k-Cut and its Dual (1997) (96)
On Multidimensional Packing Problems (2004) (95)
Multi-processor scheduling to minimize flow time with ε resource augmentation (2004) (93)
Randomized Pursuit-Evasion with Local Visibility (2006) (92)
Edge disjoint paths revisited (2003) (90)
Hardness of the undirected edge-disjoint paths problem with congestion (2005) (89)
On provenance and privacy (2010) (87)
The angular-metric traveling salesman problem (1997) (86)
On the hardness of 4-coloring a 3-collorable graph (2000) (86)
Sublinear Algorithms for (Δ+ 1) Vertex Coloring (2019) (83)
On Estimating Maximum Matching Size in Graph Streams (2017) (83)
An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design (2008) (83)
Perfect matchings in o(n log n) time in regular bipartite graphs (2009) (82)
Target tracking with distributed sensors: the focus of attention problem (2003) (82)
Archiving scientific data (2004) (82)
An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow (2006) (81)
A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction (1997) (77)
Edge-disjoint paths in planar graphs (2004) (73)
Provenance views for module privacy (2010) (73)
Integrated scheduling of unicast and multicast traffic in an input-queued switch (1999) (72)
Asymmetric k-center is log* n-hard to approximate (2005) (72)
Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons (2017) (69)
Differencing Provenance in Scientific Workflows (2009) (69)
Approximation algorithms for data placement on parallel disks (2000) (68)
Approximating Longest Directed Paths and Cycles (2004) (66)
Fair real-time traffic scheduling over a wireless LAN (2001) (65)
Constraint satisfaction: the approximability of minimization problems (1997) (65)
A polynomial time approximation scheme for the SONET ring loading problem (1997) (63)
Edge-disjoint paths in Planar graphs with constant congestion (2006) (62)
Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs (2010) (61)
Efficient Array Partitioning (1997) (59)
Polynomial flow-cut gaps and hardness of directed cut problems (2007) (59)
Network design for vertex connectivity (2008) (57)
Approximation schemes for preemptive weighted flow time (2002) (55)
DoS Protection for Reliably Authenticated Broadcast (2004) (55)
The Power of Local Information in Social Networks (2012) (53)
On wireless spectrum estimation and generalized graph coloring (1998) (52)
On computing functions with uncertainty (2001) (52)
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling (2018) (52)
Watermarking maps: hiding information in structured data (2000) (51)
Machine minimization for scheduling jobs with interval constraints (2004) (50)
Approximation Algorithms for Minimizing AverageWeighted Completion Time (2004) (48)
A Graph Partitioning Approach to Sequential Diagnosis (1997) (48)
A deterministic algorithm for the cost-distance problem (2001) (47)
The Stochastic Matching Problem with (Very) Few Queries (2016) (46)
Algorithms for Single-Source Vertex Connectivity (2008) (46)
Adaptive Selective Verification: An Efficient Adaptive Countermeasure to Thwart DoS Attacks (2012) (46)
Social Welfare in One-Sided Matching Markets without Money (2011) (45)
Streaming Lower Bounds for Approximating MAX-CUT (2014) (45)
Randomized Composable Coresets for Matching and Vertex Cover (2017) (45)
Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games (2010) (45)
Randomized pursuit-evasion with limited visibility (2004) (45)
Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply (2012) (44)
Hardness of routing with congestion in directed graphs (2007) (43)
Time-Constrained Scheduling of Weighted Packets on Trees and Meshes (1999) (43)
On indexed data broadcast (1998) (43)
Tight bounds for single-pass streaming complexity of the set cover problem (2016) (43)
Control Message Aggregation in Group Communication Protocols (2002) (42)
Locating and Capturing an Evader in a Polygonal Environment (2004) (41)
Automatic construction of a minimum size motion graph (2009) (40)
On broadcast disk paging (1998) (40)
On Certificates and Lookahead in Dynamic Graph Problems (1996) (39)
Better and simpler error analysis of the Sinkhorn–Knopp algorithm for matrix scaling (2018) (38)
StreamQRE: modular specification and efficient evaluation of quantitative queries over streaming data (2017) (37)
Formal Modeling and Analysis of DoS Using Probabilistic Rewrite Theories (2005) (37)
Enabling Privacy in Provenance-Aware Workflow Systems (2011) (37)
Dynamic and Non-uniform Pricing Strategies for Revenue Maximization (2009) (37)
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems (2019) (36)
Approximating the average response time in broadcast scheduling (2005) (34)
Top-k and Clustering with Noisy Comparisons (2014) (34)
Approximability of Capacitated Network Design (2010) (33)
The ratio index for budgeted learning, with applications (2008) (33)
A Formal Investigation of (2007) (32)
Strategic Network Formation with Attack and Immunization (2015) (32)
Compression without a common prior: an information-theoretic justification for ambiguity in language (2011) (32)
On (1, ∊)-Restricted Assignment Makespan Minimization (2014) (30)
The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm (2017) (28)
(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space (2017) (28)
A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines (2001) (27)
The Network as a Storage Device: Dynamic Routing with Bounded Buffers (2005) (27)
Optimizing user views for workflows (2009) (26)
Hardness of cut problems in directed graphs (2006) (26)
Complexity of the Minimum Input Selection Problem for Structural Controllability (2015) (26)
Network bargaining: algorithms and structural results (2009) (26)
A Linear Time Algorithm for Sequential Diagnosis in Hypercubes (1995) (25)
On Diameter Verification and Boolean Matrix Multiplication. (1995) (25)
Privacy issues in scientific workflow provenance (2010) (25)
Adaptive Selective Verification (2008) (24)
An optimal labeling scheme for workflow provenance using skeleton labels (2010) (24)
Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing (2009) (23)
Influence Maximization in Undirected Networks (2014) (21)
Approximation Algorithms for the Largest Common Subtree Problem. (1995) (21)
Sensitivity and Computational Complexity in Financial Networks (2015) (20)
Graph Sparsification via Refinement Sampling (2010) (20)
3. Boolean Constraint Satisfaction Problems (2001) (20)
Effective and efficient similarity search in scientific workflow repositories (2016) (20)
Layer Decomposition: An Effective Structure-Based Approach for Scientific Workflow Similarity (2014) (20)
Mitigating DoS attack through selective bin verification (2005) (20)
Algorithms for the Generalized Sorting Problem (2011) (20)
Directed network design with orientation constraints (2000) (19)
Testing Graph Clusterability: Algorithms and Lower Bounds (2018) (19)
Polynomial pass lower bounds for graph streaming algorithms (2019) (19)
SIGMOD Conference 2002 (2002) (19)
Tight Bounds for Linear Sketches of Approximate Matchings (2015) (19)
Polynomial flow-cut gaps and hardness of directed cut problems (2009) (19)
On the Network Coding Advantage for Wireless Multicast in Euclidean Space (2008) (18)
Perfect matchings via uniform sampling in regular bipartite graphs (2008) (18)
Selection with monotone comparison costs (2003) (18)
Quantiles and Equi-depth Histograms over Streams (2016) (18)
StreamQRE: modular specification and efficient evaluation of quantitative queries over streaming data (2017) (18)
Near-linear Size Hypergraph Cut Sparsifiers (2020) (17)
Mechanism Design for a Risk Averse Seller (2012) (17)
Connectivity in Random Forests and Credit Networks (2015) (16)
Space Time Tradeoffs for Graph Properties (1999) (16)
Preserving Module Privacy in Workflow Provenance (2010) (15)
Urban Traffic Control (2009) (15)
Stochastic Submodular Cover with Limited Adaptivity (2018) (15)
Graph Connectivity and Single Element Recovery via Linear and OR Queries (2020) (14)
The 2-catalog segmentation problem (1999) (14)
FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science (2000) (14)
The Optimization Complexity of Constraint Satisfaction Problems (1995) (14)
An energy measurement based collision resolution protocol (2003) (13)
Logic Programming for Software Verification and Testing (1991) (13)
Disjoint Set Union with Randomized Linking (2014) (13)
Queries with difference on probabilistic databases (2011) (12)
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem (2018) (12)
A Note on Multiflows and Treewidth (2009) (12)
Algorithms for Provisioning Queries and Analytics (2015) (11)
Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data (2006) (11)
Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs (2010) (11)
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation (2020) (11)
Hardness of Directed Routing with Congestion (2006) (10)
AF ormal Investigation ofDiff3 (2007) (10)
Approximating Longest Directed Path (2003) (10)
Nash Dynamics in Congestion Games with Similar Resources (2009) (10)
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS (2022) (10)
Japan Advanced Institute of Science and Technology (2015) (9)
On embeddability of modular robot designs (2015) (9)
Asymmetric k-center is log* n-hard to approximate (2004) (9)
Randomized Pursuit-Evasion in a (2005) (9)
Adaptive SelectiveVerification (2008) (9)
Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions (2020) (8)
A Formal Investigation of Diff 3 (2007) (8)
New Hardness Results for Undirected Edge Disjoint Paths (2005) (8)
Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches (2015) (8)
Algorithms for 2-Route Cut Problems (2008) (7)
A greedy approximation algorithm for minimum-gap scheduling (2013) (7)
A Faster Algorithm for Minimum-cost Bipartite Perfect Matching in Planar Graphs (2018) (7)
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013 (2013) (7)
On the complexity of graph self-assembly in accretive systems (2006) (6)
Efficient Enumeration of Phylogenetically Informative Substrings (2006) (6)
Data annotations, provenance, and archiving (2002) (6)
The Stochastic Matching Problem with (Very) Few Queries (2019) (6)
11 Approximation Algorithms for Minimizing Average Weighted Completion Time (2004) (6)
STCON in Directed Unique-Path Graphs (2008) (5)
On $(1,\epsilon)$-Restricted Assignment Makespan Minimization (2014) (5)
Sublinear Algorithms for Hierarchical Clustering (2022) (5)
Network Formation under Random Attack and Probabilistic Spread (2019) (5)
Graph certificates, lookahead in dynamic graph problems, and assembly planning in robotics (1994) (4)
An O( v n)-approximation and integrality gap for EDP and UFP in undirected graphs and DAGs (2005) (4)
Multi-processor Scheduling to Minimize Flow Time with epsilon Resource Augmentation (2021) (4)
Selection with monotone comparison cost (2003) (4)
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics (2022) (4)
On Regularity Lemma and Barriers in Streaming and Dynamic Matching (2022) (4)
An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs (2020) (4)
Fast Convergence in the Double Oral Auction (2015) (3)
A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits (2022) (3)
On Weighted Graph Sparsification by Linear Sketching (2022) (3)
Perfect Matchings in Õ (n1.5) Time in Regular Bipartite Graphs (2009) (3)
To Show or Not to Show in Workflow Provenance (2013) (3)
Genome Identification and Classification by Short Oligo Arrays (2004) (3)
Nash Dynamics in Constant Player and Bounded Jump Congestion Games (2009) (3)
Complexity Theory Column 34 (2007) (3)
A Utility Equivalence Theorem for Concave Functions (2014) (3)
Mechanism Design with Risk Aversion (2011) (2)
Near-Perfect Recovery in the One-Dimensional Latent Space Model (2020) (2)
Sublinear Algorithms for $(\Delta + 1)$ Vertex Coloring (2018) (2)
A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction (1996) (2)
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization (2021) (2)
The Optimization Complexity of Structure Maximization Problems (1996) (2)
A polynomial time approximation scheme for the SONET ring loading problem : Packet networking (1997) (2)
An LP Formulation and Approximation Algorithms for the Metric Labeling Problem (2004) (1)
Delays and the Capacity of Continuous-Time Channels (2011) (1)
On the Power of Adversarial Infections in Networks (2013) (1)
D S ] 2 4 Ju l 2 01 8 Sublinear Algorithms for ( ∆ + 1 ) Vertex Coloring (2018) (1)
Water Hyacinth Identification Using CART Modeling With Hyperspectral Data in the Sacramento-San Joaquin River Delta of California (2007) (1)
Space-efficient Query Evaluation over Probabilistic Event Streams (2020) (1)
Hardness of Approximation for Orienteering with Multiple Time Windows (2021) (1)
Bargaining and pricing in networked economic systems (2011) (1)
Approximability of Capacitated Network Design (2014) (1)
Approximate optimization of convex functions with outlier noise (2021) (1)
New Algorithms for Sequential Diagnosis (1992) (1)
Optimal Bounds for Dominating Set in Graph Streams (2022) (1)
Nearly Tight Bounds for Discrete Search under Outlier Noise (2022) (1)
Rapid convergence versus policy expressiveness in interdomain routing (2016) (1)
Space-Time Tradeo s for Graph (1999) (1)
Provenance and uncertainty (2012) (1)
Species Identification From Spatial Analysis of Digital Imagery (2007) (0)
Session details: Session 5B (2003) (0)
9. The Complexity of the Meta-Problems (2001) (0)
4. Characterizations of Constraint Functions (2001) (0)
Approximating Pure Nash Equilibrium in Cut, Party Affiliation, and Satisfying Games (2021) (0)
A greedy approximation algorithm for minimum-gap scheduling (2016) (0)
Mechanism Design and Risk Aversion (2011) (0)
Perfect Matchings in Õ (n1.5) Time in Regular Bipartite Graphs (2018) (0)
D S ] 5 J an 2 01 9 Sublinear Algorithms for ( ∆ + 1 ) Vertex Coloring (2019) (0)
Algorithms for Minimizing Weighted Flow Time [ Extended (2015) (0)
Logic Programming for Software Testing (1991) (0)
Fair Real-Time Scheduling over a Wireless LAN (2005) (0)
Fair Schedulingof Real-timeTraffic overWirelessLANs (2000) (0)
7. Classification Theorems for Optimization Problems (2001) (0)
PAC Top-k Identification under SST in Limited Rounds (2022) (0)
Session details: Session 10B (2003) (0)
On the Power of Planned Infections in Networks (2015) (0)
Query Complexity of the Metric Steiner Tree Problem (2022) (0)
Public Abstract (2005) (0)
Matchings, Random Walks, and Sampling (2014) (0)
10. Concluding Remarks (2001) (0)
5. Implementation of Functions and Reductions (2001) (0)
Robust self-assembly of graphs (2009) (0)
sODA cOMMIttees Program committee chair (2012) (0)
6. Classification Theorems for Decision, Counting and Quantified Problems (2001) (0)
Mechanism Design for Risk Averse Sellers (2011) (0)
A PTAS for Minimizing Average Weighted Completion Time With Release Dates on Uniformly Related Machines (2000) (0)
Single pass graph sparsification in distributed stream processing systems ∗ (0)
8. Input-Restricted Constrained Satisfaction Problems (2001) (0)
Special issue: 35th Annual ACM Symposium on Theory of Computing (2004) (0)
How Much Bandwidth Can Attack Bots Commandeer? (2007) (0)
A structural view of approximation (1996) (0)
News Complexity Theory Column 34 (2010) (0)
University of Pennsylvania ScholarlyCommons Departmental Papers ( CIS ) Department of Computer & Information Science May 2001 On Computing Functions with Uncertainty (2015) (0)
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries (2021) (0)
Analysis for chaos and fractals in nonlinear dynamical systems (1990) (0)
ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences (2004) (0)
2. Complexity Classes (2001) (0)
Privacy Issues in Scientific Workflow Provenance [ Position Paper ] (2010) (0)

This paper list is powered by the following services:

Other Resources About Sanjeev Khanna

en.wikipedia.org

What Schools Are Affiliated With Sanjeev Khanna?

Sanjeev Khanna is affiliated with the following schools: