Sanjeev Khanna

According to our database1, Sanjeev Khanna authored at least 235 papers between 1990 and 2018.

Collaborative distances :
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Sublinear Algorithms for (Δ+ 1) Vertex Coloring.
CoRR, 2018

Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem.
CoRR, 2018

Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling.
CoRR, 2018

Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling.
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
Fast Convergence in the Double Oral Auction.
ACM Trans. Economics and Comput., 2017

A greedy approximation algorithm for minimum-gap scheduling.
J. Scheduling, 2017

The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm.
CoRR, 2017

On Estimating Maximum Matching Size in Graph Streams.
CoRR, 2017

Randomized Composable Coresets for Matching and Vertex Cover.
CoRR, 2017

Randomized Composable Coresets for Matching and Vertex Cover.
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On Estimating Maximum Matching Size in Graph Streams.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm.
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
Effective and efficient similarity search in scientific workflow repositories.
Future Generation Comp. Syst., 2016

Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem.
CoRR, 2016

Sensitivity and computational complexity in financial networks.
Algorithmic Finance, 2016

Strategic Network Formation with Attack and Immunization.
Proceedings of the Web and Internet Economics - 12th International Conference, 2016

Tight bounds for single-pass streaming complexity of the set cover problem.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

The Stochastic Matching Problem with (Very) Few Queries.
Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Rapid convergence versus policy expressiveness in interdomain routing.
Proceedings of the 35th Annual IEEE International Conference on Computer Communications, 2016

Algorithms for Provisioning Queries and Analytics.
Proceedings of the 19th International Conference on Database Theory, 2016

Quantiles and Equi-depth Histograms over Streams.
Proceedings of the Data Stream Management - Processing High-Speed Data Streams, 2016

2015
On the Power of Planned Infections in Networks.
Internet Mathematics, 2015

Strategic Network Formation with Attack and Immunization.
CoRR, 2015

Tight Bounds for Linear Sketches of Approximate Matchings.
CoRR, 2015

Fast Convergence in the Double Oral Auction.
CoRR, 2015

Algorithms for Provisioning Queries and Analytics.
CoRR, 2015

Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches.
CoRR, 2015

Approximability of Capacitated Network Design.
Algorithmica, 2015

Fast Convergence in the Double Oral Auction.
Proceedings of the Web and Internet Economics - 11th International Conference, 2015

Streaming Lower Bounds for Approximating MAX-CUT.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Connectivity in Random Forests and Credit Networks.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

On (1, )-Restricted Assignment Makespan Minimization.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

On embeddability of modular robot designs.
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
Top-k and Clustering with Noisy Comparisons.
ACM Trans. Database Syst., 2014

Streaming Lower Bounds for Approximating MAX-CUT.
CoRR, 2014

Differential Privacy: An Economic Method for Choosing Epsilon.
CoRR, 2014

On $(1, ε)$-Restricted Assignment Makespan Minimization.
CoRR, 2014

Influence Maximization in Undirected Networks.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Approximating matching size from random streams.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Disjoint Set Union with Randomized Linking.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Fast and Improved SLEX Analysis of High-Dimensional Time Series.
Proceedings of the Machine Learning and Interpretation in Neuroimaging, 2014

Matchings, Random Walks, and Sampling.
Proceedings of the Language and Automata Theory and Applications, 2014

A Utility Equivalence Theorem for Concave Functions.
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

Differential Privacy: An Economic Method for Choosing Epsilon.
Proceedings of the IEEE 27th Computer Security Foundations Symposium, 2014

2013
Perfect Matchings in O(nlog n) Time in Regular Bipartite Graphs.
SIAM J. Comput., 2013

The All-or-Nothing Multicommodity Flow Problem.
SIAM J. Comput., 2013

Dynamic and Nonuniform Pricing Strategies for Revenue Maximization.
SIAM J. Comput., 2013

On the Power of Adversarial Infections in Networks.
Proceedings of the Algorithms and Models for the Web Graph - 10th International Workshop, 2013

Using the crowd for top-k and group-by queries.
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

A Greedy Approximation Algorithm for Minimum-Gap Scheduling.
Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

To Show or Not to Show in Workflow Provenance.
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(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design.
Theory of Computing, 2012

The Power of Local Information in Social Networks
CoRR, 2012

Distributed Private Heavy Hitters
CoRR, 2012

The Power of Local Information in Social Networks.
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

Mechanism Design for a Risk Averse Seller.
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

On the communication and streaming complexity of maximum bipartite matching.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Distributed Private Heavy Hitters.
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
Queries with Difference on Probabilistic Databases.
PVLDB, 2011

Mechanism Design with Risk Aversion
CoRR, 2011

Delays and the Capacity of Continuous-time Channels
CoRR, 2011

Social Welfare in One-sided Matching Markets without Money
CoRR, 2011

Improved Approximation Results for Stochastic Knapsack Problems.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Provenance views for module privacy.
Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

Approximability of Capacitated Network Design.
Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Compression without a common prior: an information-theoretic justification for ambiguity in language.
Proceedings of the Innovations in Computer Science, 2011

On provenance and privacy.
Proceedings of the Database Theory, 2011

Delays and the Capacity of Continuous-Time Channels.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Algorithms for the Generalized Sorting Problem.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Enabling Privacy in Provenance-Aware Workflow Systems.
Proceedings of the CIDR 2011, 2011

Social Welfare in One-Sided Matching Markets without Money.
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
Perfect matchings via uniform sampling in regular bipartite graphs.
ACM Trans. Algorithms, 2010

Robust self-assembly of graphs.
Natural Computing, 2010

Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP
CoRR, 2010

Approximability of Capacitated Network Design
CoRR, 2010

Preserving Module Privacy in Workflow Provenance
CoRR, 2010

Graph Sparsification via Refinement Sampling
CoRR, 2010

Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs.
Combinatorica, 2010

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing.
Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

Perfect matchings in o(n log n) time in regular bipartite graphs.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

An optimal labeling scheme for workflow provenance using skeleton labels.
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

Dynamic and non-uniform pricing strategies for revenue maximization.
Proceedings of the Behavioral and Quantitative Game Theory, 2010

2009
Approximation algorithms for data placement on parallel disks.
ACM Trans. Algorithms, 2009

Edge-Disjoint Paths in Planar Graphs with Constant Congestion.
SIAM J. Comput., 2009

Polynomial flow-cut gaps and hardness of directed cut problems.
J. ACM, 2009

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing
CoRR, 2009

Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs
CoRR, 2009

Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization
CoRR, 2009

Perfect Matchings in Õ(n1.5) Time in Regular Bipartite Graphs
CoRR, 2009

On Allocating Goods to Maximize Fairness
CoRR, 2009

A Note on Multiflows and Treewidth.
Algorithmica, 2009

The Network as a Storage Device: Dynamic Routing with Bounded Buffers.
Algorithmica, 2009

Nash Dynamics in Congestion Games with Similar Resources.
Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

The ratio index for budgeted learning, with applications.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Perfect matchings via uniform sampling in regular bipartite graphs.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Network bargaining: algorithms and structural results.
Proceedings of the Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), 2009

Automatic construction of a minimum size motion graph.
Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2009

Nash Dynamics in Constant Player and Bounded Jump Congestion Games.
Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009

Optimizing user views for workflows.
Proceedings of the Database Theory, 2009

Differencing Provenance in Scientific Workflows.
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

Dynamic and Non-uniform Pricing Strategies for Revenue Maximization.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

On Allocating Goods to Maximize Fairness.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008
On the complexity of graph self-assembly in accretive systems.
Natural Computing, 2008

An O(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
CoRR, 2008

Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs
CoRR, 2008

Network design for vertex connectivity.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

On the Network Coding Advantage for Wireless Multicast in Euclidean Space.
Proceedings of the 7th International Conference on Information Processing in Sensor Networks, 2008

Adaptive SelectiveVerification.
Proceedings of the INFOCOM 2008. 27th IEEE International Conference on Computer Communications, 2008

Algorithms for 2-Route Cut Problems.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

STCON in Directed Unique-Path Graphs.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

Algorithms for Single-Source Vertex Connectivity.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Robust Self-assembly of Graphs.
Proceedings of the DNA Computing, 14th International Meeting on DNA Computing, 2008

2007
Edge-disjoint paths revisited.
ACM Trans. Algorithms, 2007

Efficient Enumeration of Phylogenetically Informative Substrings.
Journal of Computational Biology, 2007

Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Polynomial flow-cut gaps and hardness of directed cut problems.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Hardness of routing with congestion in directed graphs.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

A Formal Investigation of.
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 of Computing, 2006

Randomized Pursuit-Evasion with Local Visibility.
SIAM J. Discrete Math., 2006

Hardness of Directed Routing with Congestion.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data.
Proceedings of the Distributed Computing, 20th International Symposium, 2006

Hardness of cut problems in directed graphs.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Edge-disjoint paths in Planar graphs with constant congestion.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Efficient Enumeration of Phylogenetically Informative Substrings.
Proceedings of the Research in Computational Molecular Biology, 2006

On the Complexity of Graph Self-assembly in Accretive Systems.
Proceedings of the DNA Computing, 12th International Meeting on DNA Computing, 2006

2005
Randomized pursuit-evasion in a polygonal environment.
IEEE Trans. Robotics, 2005

A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem.
SIAM J. Comput., 2005

Asymmetric k-center is log* n-hard to approximate.
J. ACM, 2005

Target tracking with distributed sensors: The focus of attention problem.
Computer Vision and Image Understanding, 2005

Multicommodity flow, well-linked terminals, and routing problems.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Approximating the average response time in broadcast scheduling.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

The Network as a Storage Device: Dynamic Routing with Bounded Buffers.
Proceedings of the Approximation, 2005

2004
Approximation Algorithms for Minimizing AverageWeighted Completion Time.
Proceedings of the Handbook of Scheduling - Algorithms, Models, and Performance Analysis., 2004

Archiving scientific data.
ACM Trans. Database Syst., 2004

On the Hardness of 4-Coloring a 3-Colorable Graph.
SIAM J. Discrete Math., 2004

A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem.
SIAM J. Discrete Math., 2004

On Multidimensional Packing Problems.
SIAM J. Comput., 2004

Special issue: 35th Annual ACM Symposium on Theory of Computing.
J. Comput. Syst. Sci., 2004

Locating and Capturing an Evader in a Polygonal Environment.
Proceedings of the Algorithmic Foundations of Robotics VI, 2004

ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences.
Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004

Genome Identification and Classification by Short Oligo Arrays.
Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 2004

Asymmetric k-center is log* n-hard to approximate.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

The all-or-nothing multicommodity flow problem.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Multi-processor scheduling to minimize flow time with epsilon resource augmentation.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Randomized pursuit-evasion with limited visibility.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Reconstructing strings from random traces.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Power-Conserving Computation of Order-Statistics over Sensor Networks.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

DoS Protection for Reliably Authenticated Broadcast.
Proceedings of the Network and Distributed System Security Symposium, 2004

Approximating Longest Directed Paths and Cycles.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Machine Minimization for Scheduling Jobs with Interval Constraints.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Edge-Disjoint Paths in Planar Graphs.
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

Asymmetric k-center is log*n-hard to Approximate
Electronic Colloquium on Computational Complexity (ECCC), 2003

Approximating Longest Directed Path
Electronic Colloquium on Computational Complexity (ECCC), 2003

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes.
Algorithmica, 2003

Selection with monotone comparison cost.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Edge disjoint paths revisited.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Target tracking with distributed sensors: the focus of attention problem.
Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, Las Vegas, Nevada, USA, October 27, 2003

2002
Guest Editor's Foreword.
J. Comput. Syst. Sci., 2002

Approximation schemes for preemptive weighted flow time.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Archiving scientific data.
Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002

On Propagation of Deletions and Annotations Through Views.
Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002

Control Message Aggregation in Group Communication Protocols.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001
Approximation Schemes for Preemptive Weighted Flow Time
Electronic Colloquium on Computational Complexity (ECCC), 2001

Algorithms for minimizing weighted flow time.
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

A deterministic algorithm for the cost-distance problem.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Space-Efficient Online Computation of Quantile Summaries.
Proceedings of the 2001 ACM SIGMOD international conference on Management of data, 2001

Fair Real-Time Traffic Scheduling over a Wireless LA.
Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS 2001), 2001

On Computing Functions with Uncertainty.
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Why and Where: A Characterization of Data Provenance.
Proceedings of the Database Theory, 2001

A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

2000
The Approximability of Constraint Satisfaction Problems.
SIAM J. Comput., 2000

On Broadcast Disk Paging.
SIAM J. Comput., 2000

On Indexed Data Broadcast
J. Comput. Syst. Sci., 2000

On the Hardness of 4-coloring a 3-colorable Graph
Electronic Colloquium on Computational Complexity (ECCC), 2000

On the Hardness of Approximating the Chromatic Number.
Combinatorica, 2000

Watermarking maps: hiding information in structured data.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Directed network design with orientation constraints.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Approximation algorithms for data placement on parallel disks.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

A PTAS for the multiple knapsack problem.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Data Provenance: Some Basic Issues.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

On the Hardness of 4-Coloring a 3-Colorable Graph.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999
The Angular-Metric Traveling Salesman Problem.
SIAM J. Comput., 1999

Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Design Networks with Bounded Pairwise Distance.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes.
SPAA, 1999

The 2-Catalog Segmentation Problem.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

On Multi-Dimensional Packing Problems.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Page Replacement for General Caching Problems.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch.
Proceedings of the Proceedings IEEE INFOCOM '99, 1999

Space Time Tradeoffs for Graph Properties.
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
On Syntactic versus Computational Views of Approximability.
SIAM J. Comput., 1998

On Certificates and Lookahead in Dynamic Graph Problems.
Algorithmica, 1998

On Indexed Data Broadcast.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

On Broadcast Disk Paging.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

On Approximating Rectangle Tiling and Packing.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

On Wireless Spectrum Estimation and Generalized Graph Coloring.
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
A Graph Partitioning Approach to Sequential Diagnosis.
IEEE Trans. Computers, 1997

On the Hardness of Approximating Max k-Cut and its Dual.
Chicago J. Theor. Comput. Sci., 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

The Angular-Metric Traveling Salesman Problem.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Efficient Array Partitioning.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Constraint Satisfaction: The Approximability of Minimization Problems.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
Constraint satisfaction: The approximability of minimization problems.
Electronic Colloquium on Computational Complexity (ECCC), 1996

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction
Electronic Colloquium on Computational Complexity (ECCC), 1996

The Optimization Complexity of Constraint Satisfaction Problems
Electronic Colloquium on Computational Complexity (ECCC), 1996

Towards a Syntactic Characterization of PTAS.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

On Certificates and Lookahead in Dynamic Graph Problems.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

On the Hardness of Approximating Max k-Cut and Its Dual.
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

1995
A Linear Time Algorithm for Sequential Diagnosis in Hypercubes.
J. Parallel Distrib. Comput., 1995

On Syntactic versus Computational Views of Approximability
Electronic Colloquium on Computational Complexity (ECCC), 1995

1994
On Syntactic versus Computational Views of Approximability
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
On the Hardness of Approximating the Chromatic Number.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

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
Logic Programming for Software Verification and Testing.
Comput. J., 1991

1990
Logic Programming for Software Testing.
Proceedings of the Advances in Computing and Information, 1990


  Loading...