Sampath Kannan

According to our database1, Sampath Kannan authored at least 119 papers between 1985 and 2019.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2019
Downstream Effects of Affirmative Action.
Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019

2018
Graph Reconstruction and Verification.
ACM Trans. Algorithms, 2018

A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Linear Sketching over F_2.
Proceedings of the 33rd Computational Complexity Conference, 2018

2017
Game Theory in AI, Logic, and Algorithms (Dagstuhl Seminar 17111).
Dagstuhl Reports, 2017

Fairness Incentives for Myopic Agents.
Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

2016
DASHR: database of small human noncoding RNAs.
Nucleic Acids Research, 2016

Detecting Character Dependencies in Stochastic Models of Evolution.
Journal of Computational Biology, 2016

Linear Sketching over 𝔽2.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Hedging Bets in Markov Decision Processes.
Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

2015
Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy).
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Private Pareto Optimal Exchange.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Near-Linear Query Complexity for Graph Inference.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Optimal provision-after-wait in healthcare.
Proceedings of the Innovations in Theoretical Computer Science, 2014

2013
Finding Optimal 1-Endpoint-Crossing Trees.
TACL, 2013

AS-CRED: Reputation and Alert Service for Interdomain Routing.
IEEE Systems Journal, 2013

On the Complexity of Shortest Path Problems on Discounted Cost Graphs.
Proceedings of the Language and Automata Theory and Applications, 2013

2012
The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Dynamic Programming for Higher Order Parsing of Gap-Minding Trees.
Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, 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
AS-TRUST: A Trust Quantification Scheme for Autonomous Systems in BGP.
Proceedings of the Trust and Trustworthy Computing - 4th International Conference, 2011

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

On Sampling from Multivariate Distributions.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
STiki: an anti-vandalism tool for Wikipedia using spatio-temporal analysis of revision metadata.
Proceedings of the 6th International Symposium on Wikis and Open Collaboration, 2010

Spatio-temporal analysis of Wikipedia metadata and the STiki anti-vandalism tool.
Proceedings of the 6th International Symposium on Wikis and Open Collaboration, 2010

Detecting Wikipedia vandalism via spatio-temporal analysis of revision metadata?
Proceedings of the Third European Workshop on System Security, 2010

2009
Dynamic Trust Management.
IEEE Computer, 2009

Reconstructing Numbers from Pairwise Function Values.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

QuanTM: a quantitative trust management system.
Proceedings of the Second European Workshop on System Security, 2009

2008
Graph Distances in the Data-Stream Model.
SIAM J. Comput., 2008

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

2007
Checking and Spot-Checking the Correctness of Priority Queues.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

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

Security Protocols with Isotropic Channels.
IACR Cryptology ePrint Archive, 2006

Steering of Discrete Event Systems: Control Theory Approach.
Electr. Notes Theor. Comput. Sci., 2006

Simulation-Based Graph Similarity.
Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2006

Weighted isotonic regression under the L1 norm.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

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

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

Better Alternatives to OSPF Routing.
Algorithmica, 2005

Computing Diameter in the Streaming and Sliding-Window Models.
Algorithmica, 2005

Graph distances in the streaming model: the value of space.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

More on reconstructing strings from random traces: insertions and deletions.
Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005

Approximating the Best-Fit Tree Under Lp Norms.
Proceedings of the Approximation, 2005

2004
A bound on the capacity of backoff and acknowledgment-based protocols.
SIAM J. Comput., 2004

VC-Dimension of Exterior Visibility.
IEEE Trans. Pattern Anal. Mach. Intell., 2004

Guest Editors' foreword.
J. Comput. Syst. Sci., 2004

Java-MaC: A Run-Time Assurance Approach for Java Programs.
Formal Methods in System Design, 2004

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

Genome Identification and Classification by Short Oligo Arrays.
Proceedings of the Algorithms in Bioinformatics, 4th International Workshop, 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

Sampling based sensor-network deployment.
Proceedings of the 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendai, Japan, September 28, 2004

On Graph Problems in a Semi-streaming Model.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Inferring Mixtures of Markov Chains.
Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

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

Local exploration: online algorithms and a probabilistic framework.
Proceedings of the 2003 IEEE International Conference on Robotics and Automation, 2003

2002
An Approximate L1-Difference Algorithm for Massive Data Streams.
SIAM J. Comput., 2002

Computational Analysis of Run-time Monitoring - Fundamentals of Java-MaC.
Electr. Notes Theor. Comput. Sci., 2002

Testing and Spot-Checking of Data Streams.
Algorithmica, 2002

2001
Java-MaC: a Run-time Assurance Tool for Java Programs.
Electr. Notes Theor. Comput. Sci., 2001

Thresholds and Optimal Binary Comparison Search Trees.
Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001

2000
Testing and spot-checking of data streams (extended abstract).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

The Relationship between Public Key Encryption and Oblivious Transfer.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Information Structures.
Proceedings of the Handbook of Discrete and Combinatorial Mathematics., 1999

The Complexity of Problems on Graphs Represented as OBDDs.
Chicago J. Theor. Comput. Sci., 1999

Steering of real-time systems based on monitoring and checking.
Proceedings of the Fifth International Workshop on Object-Oriented Real-Time Dependable Systems, 1999

Runtime Assurance Based On Formal Specifications.
Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 1999

Communicating Hierarchical State Machines.
Proceedings of the Automata, 1999

Polyhedral Flows in Hybrid Automata.
Proceedings of the Hybrid Systems: Computation and Control, Second International Workshop, 1999

An Approximate L1-Difference Algorithm for Massive Data Streams.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Formally specified monitoring of temporal properties.
Proceedings of the 11th Euromicro Conference on Real-Time Systems (ECRTS 1999), 1999

1998
Computing the Local Consensus of Trees.
SIAM J. Comput., 1998

Spot-Checkers.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Complexity of Problems on Graphs Represented as OBDDs (Extended Abstract).
Proceedings of the STACS 98, 1998

1997
A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies.
SIAM J. Comput., 1997

A Quasi-Polynomial-Time Algorithm for Sampling Words from a Context-Free Language.
Inf. Comput., 1997

On the complexity and approximation of syntenic distance.
Proceedings of the First Annual International Conference on Research in Computational Molecular Biology, 1997

Nearly Tight Bounds on the Learnability of Evolution.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score.
SIAM J. Comput., 1996

Oracles and Queries That Are Sufficient for Exact Learning.
J. Comput. Syst. Sci., 1996

Determining the Evolutionary Tree Using Experiments.
J. Algorithms, 1996

Efficient Algorithms for Inverting Evolution.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

A Formal Framework for Evaluating Heuristic Programs.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995
Hen's Teeth and Whale's Feet: Generalized Characters and Their Compatibility.
Journal of Computational Biology, 1995

Designing Programs that Check Their Work.
J. ACM, 1995

Oracles and Queries That Are Sufficient for Exact Learning
Electronic Colloquium on Computational Complexity (ECCC), 1995

Computing the Local Consensus of Trees.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies when the Number of Character States is Fixed.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Counting and Random Generation of Strings in Regular Languages.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Register Allocation in Structured Programs.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Minimizing Space Usage in Evaluation of Expression Trees.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995

Of Chicken Teeth and Mouse Eyes, or Generalized Character Compatibility.
CPM, 1995

1994
Short Communication: Correction to 'Producing Good Code for the case Statement'.
Softw., Pract. Exper., 1994

Inferring Evolutionary History from DNA Sequences.
SIAM J. Comput., 1994

Checking the Correctness of Memories.
Algorithmica, 1994

Matching Nuts and Bolts.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Call Forwarding: A Simple Interprocedural Optimization Technique for Dynamically Typed Languages.
Proceedings of the Conference Record of POPL'94: 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1994

Oracles and Queries that are Sufficient for Exact Learning (Extended Abstract).
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993
Tree Reconstruction from Partial Orders.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

A robust model for finding optimal evolutionary trees.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

An Algorithm for Locating Non-Overlapping Regions of Maximum Alignment Score.
Proceedings of the Combinatorial Pattern Matching, 4th Annual Symposium, 1993

On the Query Complexity of Learning.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992
Triangulating 3-Colored Graphs.
SIAM J. Discrete Math., 1992

Implicit Representation of Graphs.
SIAM J. Discrete Math., 1992

Tiling Polygons with Parallelograms.
Discrete & Computational Geometry, 1992

Weighted Decision Trees.
Proceedings of the Logic Programming, 1992

1991
Triangulating Three-Colored Graphs.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Program Checkers for Probability Generation.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Checking the Correctness of Memories
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
Determining the Evolutionary Tree.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Two Probabilistic Results on Merging.
Proceedings of the Algorithms, 1990

Inferring Evolutionary History from DNA Sequences (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Lower Bounds on Random-Self-Reducibility.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
Designing Programs That Check Their Work
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988
The Generation of Random Permutations on the Fly.
Inf. Process. Lett., 1988

Implicit Representation of Graphs
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

1985
A Framework for the Study of Cryptographic Protocols.
Proceedings of the Advances in Cryptology, 1985


  Loading...