David R. Karger

Affiliations:
  • MIT, Cambridge, US


According to our database1, David R. Karger authored at least 220 papers between 1993 and 2021.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
Exploring Lightweight Interventions at Posting Time to Reduce the Sharing of Misinformation on Social Media.
Proc. ACM Hum. Comput. Interact., 2021

Pano: Engaging with News using Moral Framing towards Bridging Ideological Divides.
CoRR, 2021

MedKnowts: Unified Documentation and Information Retrieval for Electronic Health Records.
Proceedings of the UIST '21: The 34th Annual ACM Symposium on User Interface Software and Technology, 2021

Shapir: Standardizing and Democratizing Access to Web APIs.
Proceedings of the UIST '21: The 34th Annual ACM Symposium on User Interface Software and Technology, 2021

Recursive Random Contraction Revisited.
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Seeding Course Forums using the Teacher-in-the-Loop.
Proceedings of the LAK'21: 11th International Learning Analytics and Knowledge Conference, 2021

Do We Fix it or Burn it Down? Towards Practicable Critique at CSCW.
Proceedings of the Companion Publication of the 2021 ACM Conference on Computer Supported Cooperative Work and Social Computing, 2021

2020
A benchmark for end-user structured data exploration and search user interfaces.
J. Web Semant., 2020

ARDA: Automatic Relational Data Augmentation for Machine Learning.
Proc. VLDB Endow., 2020

A System for Interleaving Discussion and Summarization in Online Collaboration.
Proc. ACM Hum. Comput. Interact., 2020

A phase transition and a quadratic time unbiased estimator for network reliability.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Fast, Structured Clinical Documentation via Contextual Autocomplete.
Proceedings of the Machine Learning for Healthcare Conference, 2020

#Confused and beyond: detecting confusion in course forums using students' hashtags.
Proceedings of the LAK '20: 10th International Conference on Learning Analytics and Knowledge, 2020

A System for Interleaving Discussion and Summarization in Collaborative Document Writing.
Proceedings of the Companion Publication of the 2020 ACM Conference on Computer Supported Cooperative Work and Social Computing, 2020

Dark Patterns after the GDPR: Scraping Consent Pop-ups and Demonstrating their Influence.
Proceedings of the CHI '20: CHI Conference on Human Factors in Computing Systems, 2020

ScrAPIr: Making Web Data APIs Accessible to End Users.
Proceedings of the CHI '20: CHI Conference on Human Factors in Computing Systems, 2020

2019
Opportunities for Automating Email Processing: A Need-Finding Study.
Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems, 2019

2018
Deliberation and Resolution on Wikipedia: A Case Study of Requests for Comments.
Proc. ACM Hum. Comput. Interact., 2018

A Structured Response to Misinformation: Defining and Annotating Credibility Indicators in News Articles.
Proceedings of the Companion of the The Web Conference 2018 on The Web Conference 2018, 2018

Extending a Reactive Expression Language with Data Update Actions for End-User Application Authoring.
Proceedings of the 31st Annual ACM Symposium on User Interface Software and Technology, 2018

Post-literate Programming: Linking Discussion and Code in Software Development Teams.
Proceedings of the 31st Annual ACM Symposium on User Interface Software and Technology Adjunct Proceedings, 2018

Classifying and visualizing students' cognitive engagement in course readings.
Proceedings of the Fifth Annual ACM Conference on Learning at Scale, 2018

Squadbox: A Tool To Combat Online Harassment Using Friendsourced Moderation.
Proceedings of the Extended Abstracts of the 2018 CHI Conference on Human Factors in Computing Systems, 2018

Squadbox: A Tool to Combat Email Harassment Using Friendsourced Moderation.
Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems, 2018

2017
Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections.
SIGIR Forum, 2017

Matroids Hitting Sets and Unsupervised Dependency Grammar Induction.
CoRR, 2017

Random Contractions and Sampling for Hypergraph and Hedge Connectivity.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Using Student Annotated Hashtags and Emojis to Collect Nuanced Affective States.
Proceedings of the Fourth ACM Conference on Learning @ Scale, 2017

Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Wikum: Bridging Discussion Forums and Wikis Using Recursive Summarization.
Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing, 2017

2016
Mavo: Creating Interactive Data-Driven Web Applications by Authoring HTML.
Proceedings of the 29th Annual Symposium on User Interface Software and Technology, 2016

Enumerating parametric global minimum cuts by random interleaving.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Expressive Query Construction through Direct Manipulation of Nested Relational Results.
Proceedings of the 2016 International Conference on Management of Data, 2016

BESDUI: A Benchmark for End-User Structured Data User Interfaces.
Proceedings of the Semantic Web - ISWC 2016, 2016

A Fast and Simple Unbiased Estimator for Network (Un)reliability.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Eyebrowse: Selective and Public Web Activity Sharing.
Proceedings of the 19th ACM Conference on Computer Supported Cooperative Work and Social Computing, 2016

Confer: A Conference Recommendation and Meetup Tool.
Proceedings of the 19th ACM Conference on Computer Supported Cooperative Work and Social Computing, 2016

Opportunities and Challenges Around a Tool for Social and Public Web Activity Tracking.
Proceedings of the 19th ACM Conference on Computer-Supported Cooperative Work & Social Computing, 2016

2015
Fast Augmenting Paths by Random Sampling from Residual Graphs.
SIAM J. Comput., 2015

Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs.
SIAM J. Comput., 2015

Collaborative Data Analytics with DataHub.
Proc. VLDB Endow., 2015

Soylent: a word processor with a crowd inside.
Commun. ACM, 2015

Kibitz: End-to-End Recommendation System Builder.
Proceedings of the 9th ACM Conference on Recommender Systems, 2015

Mailing Lists: Why Are They Still Here, What's Wrong With Them, and How Can We Fix Them?
Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, 2015

2014
Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems.
Oper. Res., 2014

The Semantic Web and End Users: What's Wrong and How to Fix It.
IEEE Internet Comput., 2014

Spreadsheet driven web applications.
Proceedings of the 27th Annual ACM Symposium on User Interface Software and Technology, 2014

Improving online class forums by seeding discussions and managing section size.
Proceedings of the First (2014) ACM Conference on Learning @ Scale, 2014

Attendee-Sourcing: Exploring The Design Space of Community-Informed Conference Scheduling.
Proceedings of the Seconf AAAI Conference on Human Computation and Crowdsourcing, 2014

End-users publishing structured information on the web: an observational study of what, why, and how.
Proceedings of the CHI Conference on Human Factors in Computing Systems, 2014

2013
Automatic Layout of Structured Hierarchical Reports.
IEEE Trans. Vis. Comput. Graph., 2013

Cascading tree sheets and recombinant HTML: better encapsulation and retargeting of web content.
Proceedings of the 22nd International World Wide Web Conference, 2013

Efficient crowdsourcing for multi-class labeling.
Proceedings of the ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, 2013

Cobi: Community-Informed Conference Scheduling.
Proceedings of the Human Computation and Crowdsourcing: Works in Progress and Demonstration Abstracts, 2013

2012
Sorting it All Out with Humans in the Loop.
Tiny Trans. Comput. Sci., 2012

Counting with the Crowd.
Proc. VLDB Endow., 2012

Analytic Methods for Optimizing Realtime Crowdsourcing
CoRR, 2012

Tie strength in question & answer on social network sites.
Proceedings of the CSCW '12 Computer Supported Cooperative Work, 2012

Successful classroom deployment of a social document annotation system.
Proceedings of the CHI Conference on Human Factors in Computing Systems, 2012

Reject me: peer review and SIGCHI.
Proceedings of the CHI Conference on Human Factors in Computing Systems, 2012

2011
Processing and visualizing the data in tweets.
SIGMOD Rec., 2011

Human-powered Sorts and Joins.
Proc. VLDB Endow., 2011

Linear-Time Poisson-Disk Patterns.
J. Graphics, GPU, & Game Tools, 2011

Crowds in two seconds: enabling realtime crowd-powered interfaces.
Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology, 2011

Demonstration of Qurk: a query processor for humanoperators.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2011

Tweets as data: demonstration of TweeQL and Twitinfo.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2011

Faster information dissemination in dynamic networks via network coding.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Iterative Learning for Reliable Crowdsourcing Systems.
Proceedings of the Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, 2011

Creating user interfaces that entice people to manage better information.
Proceedings of the 20th ACM Conference on Information and Knowledge Management, 2011

Twitinfo: aggregating and visualizing microblogs for event exploration.
Proceedings of the International Conference on Human Factors in Computing Systems, 2011

Finders/keepers: a longitudinal study of people managing information scraps in a micro-note tool.
Proceedings of the International Conference on Human Factors in Computing Systems, 2011

A spreadsheet-based user interface for managing plural relationships in structured data.
Proceedings of the International Conference on Human Factors in Computing Systems, 2011

Budget-optimal crowdsourcing using low-rank matrix approximations.
Proceedings of the 49th Annual Allerton Conference on Communication, 2011

2010
DDoS defense by offense.
ACM Trans. Comput. Syst., 2010

Breaking local symmetries can dramatically reduce the length of propositional refutations.
Electron. Colloquium Comput. Complex., 2010

Atomate it! end-user context-sensitive automation using heterogeneous information sources on the web.
Proceedings of the 19th International Conference on World Wide Web, 2010

Sync kit: a persistent client-side database caching toolkit for data intensive websites.
Proceedings of the 19th International Conference on World Wide Web, 2010

Talking about Data: Sharing Richly Structured Information through Blogs and Wikis.
Proceedings of the Semantic Web - ISWC 2010 - 9th International Semantic Web Conference, 2010

Eyebrowse: real-time web activity sharing and visualization.
Proceedings of the 28th International Conference on Human Factors in Computing Systems, 2010

Enhancing directed content sharing on the web.
Proceedings of the 28th International Conference on Human Factors in Computing Systems, 2010

2009
Content Modeling Using Latent Permutations.
J. Artif. Intell. Res., 2009

The web page as a WYSIWYG end-user customizable database-backed information management application.
Proceedings of the 22nd Annual ACM Symposium on User Interface Software and Technology, 2009

A nearly optimal oracle for avoiding failed vertices and edges.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

A near-linear time algorithm for constructing a cactus representation of minimum cuts.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Watching Through the Web: Building Personal Activity and Context-Aware Interfaces using Web Activity Streams.
Proceedings of the Workshop on Understanding the User, 2009

Global Models of Document Structure using Latent Permutations.
Proceedings of the Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, May 31, 2009

Scaling all-pairs overlay routing.
Proceedings of the 2009 ACM Conference on Emerging Networking Experiments and Technology, 2009

Note to self: examining personal information keeping in a lightweight note-taking tool.
Proceedings of the 27th International Conference on Human Factors in Computing Systems, 2009

2008
Potluck: Data mash-up tool for casual users.
J. Web Semant., 2008

Information scraps: How and why information eludes our personal information management tools.
ACM Trans. Inf. Syst., 2008

Byzantine Modification Detection in Multicast Networks With Random Network Coding.
IEEE Trans. Inf. Theory, 2008

Inky: a sloppy command line for the web with rich visual feedback.
Proceedings of the 21st Annual ACM Symposium on User Interface Software and Technology, 2008

Improved approximations for multiprocessor scheduling under uncertainty.
Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

Improved distance sensitivity oracles via random sampling.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Understanding code architectures via interactive exploration and layout of layered diagrams.
Proceedings of the Companion to the 23rd Annual ACM SIGPLAN Conference on Object-Oriented Programming, 2008

Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP.
Proceedings of the Approximation, 2008

Route Planning under Uncertainty: The Canadian Traveller Problem.
Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008

2007
Piggy Bank: Experience the Semantic Web inside your web browser.
J. Web Semant., 2007

Subjective-cost policy routing.
Theor. Comput. Sci., 2007

Approximation Algorithms for Orienteering and Discounted-Reward TSP.
SIAM J. Comput., 2007

U-REST: an unsupervised record extraction system.
Proceedings of the 16th International Conference on World Wide Web, 2007

Exhibit: lightweight structured data publishing.
Proceedings of the 16th International Conference on World Wide Web, 2007

Gui --- phooey!: the case for text input.
Proceedings of the 20th Annual ACM Symposium on User Interface Software and Technology, 2007

Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Potluck: Semi-Ontology Alignment for Casual Users.
Proceedings of the Semantic Web Challenge 2007 co-located with ISWC 2007 + ASWC 2007, 2007

Randomized Decoding for Selection-and-Ordering Problems.
Proceedings of the Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, 2007

Management of personal information scraps.
Proceedings of the Extended Abstracts Proceedings of the 2007 Conference on Human Factors in Computing Systems, 2007

2006
Minimum-cost multicast over coded packet networks.
IEEE Trans. Inf. Theory, 2006

A Random Linear Network Coding Approach to Multicast.
IEEE Trans. Inf. Theory, 2006

Simple Efficient Load-Balancing Algorithms for Peer-to-Peer Systems.
Theory Comput. Syst., 2006

On Separation, Randomness and Linearity for Network Codes over Finite Fields
CoRR, 2006

Data unification in personal information management.
Commun. ACM, 2006

Enabling web browsers to augment web sites' filtering and sorting functionalities.
Proceedings of the 19th Annual ACM Symposium on User Interface Software and Technology, 2006

The complexity of matrix completion.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Less is more: probabilistic models for retrieving fewer relevant documents.
Proceedings of the SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2006

Fresnel: A Browser-Independent Presentation Vocabulary for RDF.
Proceedings of the Semantic Web - ISWC 2006, 5th International Semantic Web Conference, 2006

Distributed Quota Enforcement for Spam Control.
Proceedings of the 3rd Symposium on Networked Systems Design and Implementation (NSDI 2006), 2006

On the Expected VCG Overpayment in Large Networks.
Proceedings of the 45th IEEE Conference on Decision and Control, 2006

Optimal Route Planning under Uncertainty.
Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling, 2006

2005
What would it mean to blog on the semantic web?
J. Web Semant., 2005

Using linear programming to Decode Binary linear codes.
IEEE Trans. Inf. Theory, 2005

Toward Using the Network as a Switch: On the Use of TDM in Linear Optical Networks.
IEEE J. Sel. Areas Commun., 2005

Thresher: automating the unwrapping of semantic content from the World Wide Web.
Proceedings of the 14th international conference on World Wide Web, 2005

Deterministic network coding by matrix completion.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Magnet: Supporting Navigation in Semistructured Data Environments.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2005

First-price path auctions.
Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005

Personalized Semantic Web Application Development by End Users.
Proceedings of the ISWC 2005 Workshop on The Semantic Desktop, 2005

Brief announcement: on the expected overpayment of VCG mechanisms in large networks.
Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

Incremental exploratory visualization of relationships in large codebases for program comprehension.
Proceedings of the Companion to the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, 2005

OverCite: A Cooperative Digital Research Library.
Proceedings of the Peer-to-Peer Systems IV, 4th International Workshop, 2005

Arpeggio: Metadata Searching and Content Sharing with Chord.
Proceedings of the Peer-to-Peer Systems IV, 4th International Workshop, 2005

Relo: helping users manage context during interactive exploratory visualization of large codebases.
Proceedings of the 2005 OOPSLA workshop on Eclipse Technology eXchange, 2005

Haystack: A General-Purpose Information Management Tool for End Users Based on Semistructured Data.
Proceedings of the Second Biennial Conference on Innovative Data Systems Research, 2005

2004
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut.
Math. Oper. Res., 2004

Decoding turbo-like codes via linear programming.
J. Comput. Syst. Sci., 2004

Using urls and table layout for web classification tasks.
Proceedings of the 13th international conference on World Wide Web, 2004

On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Byzantine modification detection in multicast networks using randomized network coding.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks.
Proceedings of the Peer-to-Peer Systems III, Third International Workshop, 2004

The perfect search engine is not enough: a study of orienteering behavior in directed search.
Proceedings of the 2004 Conference on Human Factors in Computing Systems, 2004

Collections: flexible, essential tools for information management.
Proceedings of the Extended abstracts of the 2004 Conference on Human Factors in Computing Systems, 2004

Haystack: a user interface for creating, browsing, and organizing arbitrary semistructured information.
Proceedings of the Extended abstracts of the 2004 Conference on Human Factors in Computing Systems, 2004

2003
Chord: a scalable peer-to-peer lookup protocol for internet applications.
IEEE/ACM Trans. Netw., 2003

Techniques for scheduling with rejection.
J. Algorithms, 2003

Looking up data in P2P systems.
Commun. ACM, 2003

Assisted Browsing for Semistructured Data.
Proceedings of the Twelfth International World Wide Web Conference - Posters, 2003

A Unified Abstraction for Messaging on the Semantic Web.
Proceedings of the Twelfth International World Wide Web Conference - Posters, 2003

User Interaction Experience for Semantic Web Information.
Proceedings of the Twelfth International World Wide Web Conference - Posters, 2003

User interface continuations.
Proceedings of the 16th Annual ACM Symposium on User Interface Software and Technology, 2003

Empirical development of an exponential probabilistic model for text retrieval: using textual analysis to build a better model.
Proceedings of the SIGIR 2003: Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, July 28, 2003

Haystack: A Platform for Authoring End User Semantic Web Applications.
Proceedings of the Semantic Web, 2003

Thwarting Web Censorship with Untrusted Messenger Discovery.
Proceedings of the Privacy Enhancing Technologies, Third International Workshop, 2003

Sticky notes for the semantic web.
Proceedings of the 8th International Conference on Intelligent User Interfaces, 2003

Haystack: a platform for creating, organizing and visualizing semistructured information.
Proceedings of the 8th International Conference on Intelligent User Interfaces, 2003

On the Feasibility of Peer-to-Peer Web Indexing and Search.
Proceedings of the Peer-to-Peer Systems II, Second International Workshop, 2003

Koorde: A Simple Degree-Optimal Distributed Hash Table.
Proceedings of the Peer-to-Peer Systems II, Second International Workshop, 2003

User Interfaces for Supporting Multiple Categorization.
Proceedings of the Human-Computer Interaction INTERACT '03: IFIP TC13 International Conference on Human-Computer Interaction, 2003

What Makes a Good Answer? The Role of Context in Question Answering.
Proceedings of the Human-Computer Interaction INTERACT '03: IFIP TC13 International Conference on Human-Computer Interaction, 2003

Text Bundling: Statistics Based Data-Reduction.
Proceedings of the Machine Learning, 2003

Tackling the Poor Assumptions of Naive Bayes Text Classifiers.
Proceedings of the Machine Learning, 2003

Linear Network Codes: A Unified Framework for Source, Channel, and Network Coding.
Proceedings of the Advances in Network Information Theory, 2003

The role of context in question answering systems.
Proceedings of the Extended abstracts of the 2003 Conference on Human Factors in Computing Systems, 2003

2002
Infranet: Circumventing Web Censorship and Surveillance.
Proceedings of the 11th USENIX Security Symposium, 2002

Haystack: A Platform for Creating, Organizing and Visualizing Information Using RDF.
Proceedings of the WWW2002 International Workshop on the Semantic Web, Hawaii, May 7, 2002, 2002

Finding nearest neighbors in growth-restricted metrics.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Random sampling in residual graphs.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Analysis of the evolution of peer-to-peer systems.
Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, 2002

INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery.
Proceedings of the Pervasive Computing, 2002

Observations on the Dynamic Evolution of Peer-to-Peer Networks.
Proceedings of the Peer-to-Peer Systems, First International Workshop, 2002

2001
A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem.
SIAM Rev., 2001

An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms.
ACM J. Exp. Algorithmics, 2001

Wide-Area Cooperative Storage with CFS.
Proceedings of the 18th ACM Symposium on Operating System Principles, 2001

Learning Markov networks: maximum bounded tree-width graphs.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Parallel processor scheduling with delay constraints.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Chord: A scalable peer-to-peer lookup service for internet applications.
Proceedings of the ACM SIGCOMM 2001 Conference on Applications, 2001

Building peer-to-peer systems with Chord, a distributed lookup service.
Proceedings of HotOS-VIII: 8th Workshop on Hot Topics in Operating Systems, 2001

2000
Augmenting Undirected Edge Connectivity in Õ(n<sup>2</sup>) Time.
J. Algorithms, 2000

Minimum cuts in near-linear time.
J. ACM, 2000

Dynamic Graph Algorithms with Applications.
Proceedings of the Algorithm Theory, 2000

A scalable location service for geographic ad hoc routing.
Proceedings of the MOBICOM 2000, 2000

Building Steiner Trees with Incomplete Global Knowledge.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Fast Connected Components Algorithms for the EREW PRAM.
SIAM J. Comput., 1999

Random Sampling in Cut, Flow, and Network Design Problems.
Math. Oper. Res., 1999

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems.
J. Comput. Syst. Sci., 1999

Web Caching with Consistent Hashing.
Comput. Networks, 1999

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Haystack: Per-User Information Environments.
Proceedings of the 1999 ACM CIKM International Conference on Information and Knowledge Management, 1999

Scheduling Algorithms.
Proceedings of the Algorithms and Theory of Computation Handbook., 1999

1998
Random sampling and greedy sparsification for matroid optimization problems.
Math. Program., 1998

Approximate Graph Coloring by Semidefinite Programming.
J. ACM, 1998

A Fully Polynomial Randomized Approximation Scheme for the All Terminal Network Reliability Problem
CoRR, 1998

Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Better Random Sampling Algorithms for Flows in Undirected Graphs.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

1997
An NC Algorithm for Minimum Cuts.
SIAM J. Comput., 1997

Distributed Job Scheduling in Rings.
J. Parallel Distributed Comput., 1997

(De)randomized Construction of Small Sample Spaces in NC.
J. Comput. Syst. Sci., 1997

An Õ(n^{3/14})-Coloring Algorithm for 3-Colorable Graphs.
Inf. Process. Lett., 1997

On Approximating the Longest Path in a Graph.
Algorithmica, 1997

Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Implementing a Fully Polynomial Time Approximation Scheme for All Terminal Network Reliability.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Experimental Study of Minimum Cut Algorithms.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Near-optimal Intraprocedural Branch Alignment.
Proceedings of the ACM SIGPLAN '97 Conference on Programming Language Design and Implementation (PLDI), 1997

1996
A Better Algorithm for an Ancient Scheduling Problem.
J. Algorithms, 1996

A New Approach to the Minimum Cut Problem.
J. ACM, 1996

Approximating <i>s-t</i> Minimum Cuts in <i>Õ</i>(<i>n</i><sup>2</sup>) Time.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995
Prim-Dijkstra tradeoffs for improved performance-driven routing tree design.
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1995

A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.
J. ACM, 1995

Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Polynomial time approximation schemes for dense instances of <i>NP</i>-hard problems.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

1994
Job Scheduling in Rings.
Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

Using Randomized Sparsification to Approximate Minimum Cuts.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

(De)randomized Construction of Small Sample Spaces in \calNC
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths.
SIAM J. Comput., 1993

On Approximating the Longest Path in a Graph (Preliminary Version).
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

An O~(n<sup>2</sup>) algorithm for minimum cuts.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Constant Interaction-Time Scatter/Gather Browsing of Very Large Document Collections.
Proceedings of the 16th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval. Pittsburgh, PA, USA, June 27, 1993

Random Sampling in Matroids, with Applications to Graph Connectivity and Minimum Spanning Trees
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993


  Loading...