2025
Leveraging parameterized Chernoff bounds for simplified algorithm analyses.
Inf. Process. Lett., 2025
2024
Fast Inference for Augmented Large Language Models.
CoRR, 2024
Don't Stop Me Now: Embedding Based Scheduling for LLMs.
CoRR, 2024
Learning-Augmented Frequency Estimation in Sliding Windows.
CoRR, 2024
Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams.
CoRR, 2024
SkipPredict: When to Invest in Predictions for Scheduling.
CoRR, 2024
Optimal and Near-Optimal Adaptive Vector Quantization.
CoRR, 2024
THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression.
Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation, 2024
Accelerating Federated Learning with Quick Distributed Mean Estimation.
Proceedings of the Forty-first International Conference on Machine Learning, 2024
Beyond Throughput and Compression Ratios: Towards High End-to-end Utility of Gradient Compression.
Proceedings of the 23rd ACM Workshop on Hot Topics in Networks, 2024
2023
Separating <i>k</i>-Player from <i>t</i>-Player One-Way Communication, with Applications to Data Streams.
Theory Comput., 2023
THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression.
CoRR, 2023
Proceedings of the ACM SIGCOMM 2023 Conference, 2023
2022
The Supermarket Model With Known and Predicted Service Times.
IEEE Trans. Parallel Distributed Syst., 2022
SNARF: A Learning-Enhanced Range Filter.
Proc. VLDB Endow., 2022
Can Learned Models Replace Hash Functions?
Proc. VLDB Endow., 2022
QUIC-FL: Quick Unbiased Compression for Federated Learning.
CoRR, 2022
FRANCIS: Fast Reaction Algorithms for Network Coordination In Switches.
CoRR, 2022
Tabula: Efficiently Computing Nonlinear Activation Functions for Secure Neural Network Inference.
CoRR, 2022
Incentive Compatible Queues Without Money.
CoRR, 2022
Algorithms with predictions.
Commun. ACM, 2022
Proteus: A Self-Designing Range Filter.
Proceedings of the SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022
Algorithmic Tools for Understanding the Motif Structure of Networks.
Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2022
Uniform Bounds for Scheduling with Job Size Estimates.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022
EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning.
Proceedings of the International Conference on Machine Learning, 2022
2021
Communication-Efficient Federated Learning via Robust Distributed Mean Estimation.
CoRR, 2021
Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning Problem.
CoRR, 2021
Improved Sublinear Time Algorithm for Longest Increasing Subsequence.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
DRIVE: One-bit Distributed Mean Estimation.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021
Gradient Disaggregation: Breaking Privacy in Federated Learning by Reconstructing the User Participant Matrix.
Proceedings of the 38th International Conference on Machine Learning, 2021
Putting the "Learning" into Learning-Augmented Algorithms for Frequency Estimation.
Proceedings of the 38th International Conference on Machine Learning, 2021
Partitioned Learned Bloom Filters.
Proceedings of the 9th International Conference on Learning Representations, 2021
SALSA: Self-Adjusting Lean Streaming Analytics.
Proceedings of the 37th IEEE International Conference on Data Engineering, 2021
How to Send a Real Number Using a Single Bit (And Some Shared Randomness).
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021
Zero-CPU Collection with Direct Telemetry Access.
Proceedings of the HotNets '21: The 20th ACM Workshop on Hot Topics in Networks, 2021
Queues with Small Advice.
Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms, 2021
2020
ACM J. Exp. Algorithmics, 2020
Erdös-Szekeres Partitioning Problem.
CoRR, 2020
Partitioned Learned Bloom Filter.
CoRR, 2020
Clustering with a faulty oracle.
Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020
Dynamic algorithms for LIS and distance to monotonicity.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020
PINT: Probabilistic In-band Network Telemetry.
Proceedings of the SIGCOMM '20: Proceedings of the 2020 Annual conference of the ACM Special Interest Group on Data Communication on the applications, 2020
Optimal Learning of Joint Alignments with a Faulty Oracle.
Proceedings of the IEEE International Symposium on Information Theory, 2020
Scheduling with Predictions and the Price of Misprediction.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020
Faster and More Accurate Measurement through Additive-Error Counters.
Proceedings of the 39th IEEE Conference on Computer Communications, 2020
DISCOvering the heavy hitters with disaggregated sketches.
Proceedings of the CoNEXT '20: The 16th International Conference on emerging Networking EXperiments and Technologies, 2020
Detecting routing loops in the data plane.
Proceedings of the CoNEXT '20: The 16th International Conference on emerging Networking EXperiments and Technologies, 2020
Prophets, Secretaries, and Maximizing the Probability of Choosing the Best.
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020
Algorithms with Predictions.
Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020
When Simple Hash Functions Suffice.
Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020
2019
The Supermarket Model with Known and Predicted Service Times.
CoRR, 2019
A digital fountain retrospective.
Comput. Commun. Rev., 2019
Robust Set Reconciliation via Locality Sensitive Hashing.
Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019
Arithmetic Progression Hypergraphs: Examining the Second Moment Method.
Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics, 2019
Online Pandora's Boxes and Bandits.
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019
2018
Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018
Better Bounds for Coalescing-Branching Random Walks.
ACM Trans. Parallel Comput., 2018
EMOMA: Exact Match in One Memory Access.
IEEE Trans. Knowl. Data Eng., 2018
Simple multi-party set reconciliation.
Distributed Comput., 2018
Directory Reconciliation.
CoRR, 2018
Optimizing Learned Bloom Filters by Sandwiching.
CoRR, 2018
A Model for Learned Bloom Filters and Related Structures.
CoRR, 2018
Joint Alignment from Pairwise Differences with a Noisy Oracle.
Proceedings of the Algorithms and Models for the Web Graph - 15th International Workshop, 2018
Load Thresholds for Cuckoo Hashing with Double Hashing.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018
Reconciling Graphs and Sets of Sets.
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018
A Model for Learned Bloom Filters and Optimizing by Sandwiching.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018
A Bayesian Nonparametric View on Count-Min Sketch.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018
Weightless: Lossy weight encoding for deep neural network compression.
Proceedings of the 35th International Conference on Machine Learning, 2018
Metric Sublinear Algorithms via Linear Sampling.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
Simulated Annealing for JPEG Quantization.
Proceedings of the 2018 Data Compression Conference, 2018
2017
Theory and Applications of Hashing (Dagstuhl Seminar 17181).
Dagstuhl Reports, 2017
Predicting Positive and Negative Links with Noisy Queries: Theory & Practice.
CoRR, 2017
Technical Perspective: Building a better hash function.
Commun. ACM, 2017
Scalable Motif-aware Graph Clustering.
Proceedings of the 26th International Conference on World Wide Web, 2017
2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection.
Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017
Compresso: Efficient Compression of Segmentation Data for Connectomics.
Proceedings of the Medical Image Computing and Computer Assisted Intervention - MICCAI 2017, 2017
2016
Parallel Peeling Algorithms.
ACM Trans. Parallel Comput., 2016
OMASS: One Memory Access Set Separation.
IEEE Trans. Knowl. Data Eng., 2016
Measuring Dependence Powerfully and Equitably.
J. Mach. Learn. Res., 2016
Hardness of peeling with stashes.
Inf. Process. Lett., 2016
Auditable Data Structures.
IACR Cryptol. ePrint Arch., 2016
More Practical and Secure History-Independent Hash Tables.
IACR Cryptol. ePrint Arch., 2016
Predicting Signed Edges with O(n log n) Queries.
CoRR, 2016
2-Bit Random Projections, NonLinear Estimators, and Approximate Near Neighbor Search.
CoRR, 2016
Technical Perspective: Catching lies (and mistakes) in offloaded computation.
Commun. ACM, 2016
Space Lower Bounds for Itemset Frequency Sketches.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016
Quantized Random Projections and Non-Linear Estimation of Cosine Similarity.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016
Models and Algorithms for Graph Watermarking.
Proceedings of the Information Security - 19th International Conference, 2016
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
A New Approach to Analyzing Robin Hood Hashing.
Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics, 2016
More Analysis of Double Hashing for Balanced Allocations.
Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics, 2016
Analyzing distributed Join-Idle-Queue: A fluid limit approach.
Proceedings of the 54th Annual Allerton Conference on Communication, 2016
2015
An Empirical Study of Leading Measures of Dependence.
CoRR, 2015
Equitability, interval estimation, and statistical power.
CoRR, 2015
Theory without experiments: have we gone too far?
Commun. ACM, 2015
Scaling Up Clustered Network Appliances with ScaleBricks.
Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, 2015
Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling.
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015
2014
Improving the performance of Invertible Bloom Lookup Tables.
Inf. Process. Lett., 2014
Theoretical Foundations of Equitability and the Maximal Information Coefficient.
CoRR, 2014
Space Lower Bounds for Itemset Frequency Sketches.
CoRR, 2014
Coding for Random Projections and Approximate Near Neighbor Search.
CoRR, 2014
Efficient estimation for high similarities using odd sketches.
Proceedings of the 23rd International World Wide Web Conference, 2014
Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket.
Proceedings of the Experimental Algorithms - 13th International Symposium, 2014
Balanced allocations and double hashing.
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014
Repeated deletion channels.
Proceedings of the 2014 IEEE Information Theory Workshop, 2014
Coding for Random Projections.
Proceedings of the 31th International Conference on Machine Learning, 2014
Cuckoo Filter: Practically Better Than Bloom.
Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies, 2014
Multi-party set reconciliation using characteristic polynomials.
Proceedings of the 52nd Annual Allerton Conference on Communication, 2014
Some Practical Randomized Algorithms and Data Structures.
Proceedings of the Computing Handbook, 2014
2013
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream.
Theory Comput., 2013
Equitability Analysis of the Maximal Information Coefficient, with Comparisons
CoRR, 2013
External-Memory Multimaps.
Algorithmica, 2013
2012
The daily deals marketplace: empirical observations and managerial implications.
SIGecom Exch., 2012
Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009).
SIAM J. Comput., 2012
An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets.
J. ACM, 2012
Daily deals: prediction, social diffusion, and reputational ramifications.
Proceedings of the Fifth International Conference on Web Search and Web Data Mining, 2012
An Economic Analysis of User-Privacy Options in Ad-Supported Services.
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012
Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012
Information dissemination via random walks in <i>d</i>-dimensional space.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
Privacy-preserving group data access via stateless oblivious RAM simulation.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
The groupon effect on yelp ratings: a root cause analysis.
Proceedings of the 13th ACM Conference on Electronic Commerce, 2012
Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability.
Proceedings of the Design and Analysis of Algorithms, 2012
Biff (Bloom filter) codes: Fast error correction for large data sets.
Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012
Continuous time channels with interference.
Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012
Practical verified computation with streaming interactive proofs.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012
Anonymous Card Shuffling and Its Applications to Parallel Mixnets.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012
Verifiable Computation with Massively Parallel Interactive Proofs.
Proceedings of the 4th USENIX Workshop on Hot Topics in Cloud Computing, 2012
Practical oblivious storage.
Proceedings of the Second ACM Conference on Data and Application Security and Privacy, 2012
The complexity of object reconciliation, and open problems related to set difference and coding.
Proceedings of the 50th Annual Allerton Conference on Communication, 2012
Peeling arguments and double hashing.
Proceedings of the 50th Annual Allerton Conference on Communication, 2012
Hierarchical Heavy Hitters with the Space Saving Algorithm.
Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, 2012
2011
An Analysis of Random-Walk Cuckoo Hashing.
SIAM J. Comput., 2011
Network Coding Meets TCP: Theory and Implementation.
Proc. IEEE, 2011
Streaming Graph Computations with a Helpful Advisor.
Electron. Colloquium Comput. Complex., 2011
Oblivious Storage with Low I/O Overhead
CoRR, 2011
Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps
CoRR, 2011
A Month in the Life of Groupon
CoRR, 2011
Information Dissemination via Random Walks in d-Dimensional Space
CoRR, 2011
Graption: A graph-based P2P traffic classification framework for the internet backbone.
Comput. Networks, 2011
Brief announcement: large-scale multimaps.
Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011
On the zero-error capacity threshold for deletion channels.
Proceedings of the Information Theory and Applications Workshop, 2011
Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011
Cuckoo Hashing with Pages.
Proceedings of the Algorithms - ESA 2011, 2011
Oblivious RAM simulation with efficient worst-case access overhead.
Proceedings of the 3rd ACM Cloud Computing Security Workshop, 2011
Heapable Sequences and Subsequences.
Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics, 2011
Invertible bloom lookup tables.
Proceedings of the 49th Annual Allerton Conference on Communication, 2011
Codes - Protecting Data Against Errors and Loss.
Proceedings of the Algorithms Unplugged, 2011
2010
Hash-Based Techniques for High-Speed Packet Processing.
Proceedings of the Algorithms for Next Generation Networks, 2010
The Power of One Move: Hashing Schemes for Hardware.
IEEE/ACM Trans. Netw., 2010
Codes for deletion and insertion channels with segmented errors.
IEEE Trans. Inf. Theory, 2010
Designing floating codes for expected performance.
IEEE Trans. Inf. Theory, 2010
An introduction to human-guided search.
XRDS, 2010
MapReduce Parallel Cuckoo Hashing and Oblivious RAM Simulations
CoRR, 2010
Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank
CoRR, 2010
An improved analysis of the lossy difference aggregator.
Comput. Commun. Rev., 2010
Adaptive weighing designs for keyword value computation.
Proceedings of the Third International Conference on Web Search and Web Data Mining, 2010
Popularity Is Everything: A New Approach to Protecting Passwords from Statistical-Guessing Attacks.
Proceedings of the 5th USENIX Workshop on Hot Topics in Security, 2010
AMS Without 4-Wise Independence on Product Domains.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010
Information asymmetries in pay-per-bid auctions.
Proceedings of the Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), 2010
Carousel: Scalable Logging for Intrusion Prevention Systems.
Proceedings of the 7th USENIX Symposium on Networked Systems Design and Implementation, 2010
Tight asymptotic bounds for the deletion channel with small deletion probabilities.
Proceedings of the IEEE International Symposium on Information Theory, 2010
Tight Thresholds for Cuckoo Hashing via XORSAT.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010
2009
Proceedings of the Encyclopedia of Database Systems, 2009
Real-time parallel hashing on the GPU.
ACM Trans. Graph., 2009
More Robust Hashing: Cuckoo Hashing with a Stash.
SIAM J. Comput., 2009
The Hiring Problem and Lake Wobegon Strategies.
SIAM J. Comput., 2009
Interfacing network coding with TCP: an implementation
CoRR, 2009
On compressing social networks.
Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28, 2009
Network Coding Meets TCP.
Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009
An Economically-Principled Generative Model of AS Graph Connectivity.
Proceedings of the INFOCOM 2009. 28th IEEE International Conference on Computer Communications, 2009
Some Open Questions Related to Cuckoo Hashing.
Proceedings of the Algorithms, 2009
Exploiting dynamicity in graph-based traffic analysis: techniques and applications.
Proceedings of the 2009 ACM Conference on Emerging Networking Experiments and Technology, 2009
2008
Simple summaries for hashing with choices.
IEEE/ACM Trans. Netw., 2008
Capacity Bounds for Sticky Channels.
IEEE Trans. Inf. Theory, 2008
Less hashing, same performance: Building a better Bloom filter.
Random Struct. Algorithms, 2008
A Survey of Results for Deletion Channels and Related Synchronization Channels.
Proceedings of the Algorithm Theory, 2008
Why simple hash functions work: exploiting the entropy in a data stream.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
Trace reconstruction with constant deletion probability and related results.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
Distributed beamforming with binary signaling.
Proceedings of the 2008 IEEE International Symposium on Information Theory, 2008
On the performance of multiple choice hash tables with moves on deletes and inserts.
Proceedings of the 46th Annual Allerton Conference on Communication, 2008
Designing floating codes for expected performance.
Proceedings of the 46th Annual Allerton Conference on Communication, 2008
2007
Improved Lower Bounds for the Capacity of i.i.d. Deletion and Duplication Channels.
IEEE Trans. Inf. Theory, 2007
Using the Power of Two Choices to Improve Bloom Filters.
Internet Math., 2007
Capacity Upper Bounds for the Deletion Channel.
Proceedings of the IEEE International Symposium on Information Theory, 2007
Proceedings of the 6th International workshop on Peer-To-Peer Systems, 2007
Network monitoring using traffic dispersion graphs (tdgs).
Proceedings of the 7th ACM SIGCOMM Internet Measurement Conference, 2007
HEXA: Compact Data Structures for Faster Packet Processing.
Proceedings of the IEEE International Conference on Network Protocols, 2007
2006
Fine-grained layered multicast with STAIR.
IEEE/ACM Trans. Netw., 2006
A Simple Lower Bound for the Capacity of the Deletion Channel.
IEEE Trans. Inf. Theory, 2006
Polynomial Time Low-Density Parity-Check Codes With Rates Very Close to the Capacity of the q-ary Random Deletion Channel for Large q.
IEEE Trans. Inf. Theory, 2006
On Lower Bounds for the Capacity of Deletion Channels.
IEEE Trans. Inf. Theory, 2006
Towards a theory of networked computation.
SIGACT News, 2006
BubbleSearch: A simple heuristic for improving priority-based greedy algorithms.
Inf. Process. Lett., 2006
Beyond bloom filters: from approximate membership checks to approximate state machines.
Proceedings of the ACM SIGCOMM 2006 Conference on Applications, 2006
On the Theory and Practice of Data Recovery with Multiple Versions.
Proceedings of the Proceedings 2006 IEEE International Symposium on Information Theory, 2006
Network-Aware Overlays with Network Coordinates.
Proceedings of the 26th International Conference on Distributed Computing Systems Workshops (ICDCS 2006 Workshops), 2006
Stochastic Shortest Paths Via Quasi-convex Maximization.
Proceedings of the Algorithms, 2006
An Improved Construction for Counting Bloom Filters.
Proceedings of the Algorithms, 2006
New Results and Open Problems for Deletion Channels.
Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006
Distance-Sensitive Bloom Filters.
Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments, 2006
2005
Verification-based decoding for packet-based low-density parity-check codes.
IEEE Trans. Inf. Theory, 2005
New heuristic and interactive approaches to 2D rectangular strip packing.
ACM J. Exp. Algorithmics, 2005
Editorial: The Future of Power Law Research.
Internet Math., 2005
X-Tolerant Test Response Compaction.
IEEE Des. Test Comput., 2005
Digital Fountains and Their Application to Informed Content Delivery over Adaptive Overlay Networks.
Proceedings of the Distributed Computing, 19th International Conference, 2005
Multidimensional balanced allocations.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
The Markov Expert for Finding Episodes in Time Series.
Proceedings of the 2005 Data Compression Conference (DCC 2005), 2005
A Case Study in Large-Scale Interactive Optimization.
Proceedings of the IASTED International Conference on Artificial Intelligence and Applications, 2005
Probability and Computing: Randomized Algorithms and Probabilistic Analysis.
Cambridge University Press, ISBN: 9780511813603, 2005
2004
Informed content delivery across adaptive overlay networks.
IEEE/ACM Trans. Netw., 2004
On the hardness of finding optimal multiple preset dictionaries.
IEEE Trans. Inf. Theory, 2004
Power laws for monkeys typing randomly: the case of unequal probabilities.
IEEE Trans. Inf. Theory, 2004
Theory Comput. Syst., 2004
Exhaustive approaches to 2D rectangular perfect packings.
Inf. Process. Lett., 2004
Privacy Preserving Keyword Searches on Remote Encrypted Data.
IACR Cryptol. ePrint Arch., 2004
A Scaling Result for Explosive Processes.
Electron. J. Comb., 2004
Geometric generalizations of the power of two choices.
Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004
Digital fountains: a survey and look forward.
Proceedings of the 2004 IEEE Information Theory Workshop, 2004
X-Tolerant Signature Analysis.
Proceedings of the Proceedings 2004 International Test Conference (ITC 2004), 2004
Interactive data summarization: an example application.
Proceedings of the working conference on Advanced visual interfaces, 2004
2003
Binary intersymbol interference channels: Gallager codes, density evolution, and code performance bounds.
IEEE Trans. Inf. Theory, 2003
A derandomization using min-wise independent permutations.
J. Discrete Algorithms, 2003
Dynamic Models for File Sizes and Double Pareto Distributions.
Internet Math., 2003
A Brief History of Generative Models for Power Law and Lognormal Distributions.
Internet Math., 2003
Survey: Network Applications of Bloom Filters: A Survey.
Internet Math., 2003
A complete and effective move set for simplified protein folding.
Proceedings of the Sventh Annual International Conference on Computational Biology, 2003
Simple Load Balancing for Distributed Hash Tables.
Proceedings of the Peer-to-Peer Systems II, Second International Workshop, 2003
Estimating and Comparing Entropies Across Written Natural Languages Using PPM Compression.
Proceedings of the 2003 Data Compression Conference (DCC 2003), 2003
2002
Compressed bloom filters.
IEEE/ACM Trans. Netw., 2002
Linear waste of best fit bin packing on skewed distributions.
Random Struct. Algorithms, 2002
A digital fountain approach to asynchronous reliable multicast.
IEEE J. Sel. Areas Commun., 2002
FLID-DL: congestion control for layered multicast.
IEEE J. Sel. Areas Commun., 2002
Balls and bins models with feedback.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002
Optmial plans for aggregation.
Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, 2002
Exact sampling of TCP Window States.
Proceedings of the Proceedings IEEE INFOCOM 2002, 2002
Load Balancing with Memory.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
The HuGS platform: a toolkit for interactive optimization.
Proceedings of the Working Conference on Advanced Visual Interfaces, 2002
Human-Guided Tabu Search.
Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28, 2002
2001
The Power of Two Choices in Randomized Load Balancing.
IEEE Trans. Parallel Distributed Syst., 2001
Towards More Complete Models of TCP Latency and Throughput.
J. Supercomput., 2001
Improved low-density parity-check codes using irregular graphs.
IEEE Trans. Inf. Theory, 2001
Efficient erasure correcting codes.
IEEE Trans. Inf. Theory, 2001
An experimental assignment on random processes.
SIGACT News, 2001
Challenging students with creative assignments.
SIGACT News, 2001
Analysis of Timing-Based Mutual Exclusion with Random Times.
SIAM J. Comput., 2001
Completeness and robustness properties of min-wise independent permutations.
Random Struct. Algorithms, 2001
Analyses of Load Stealing Models Based on Families of Differential Equations.
Theory Comput. Syst., 2001
Delayed Information and Action in On-Line Algorithms.
Inf. Comput., 2001
IMproved results for route planning in stochastic transportation.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001
Fine-Grained Layered Multicast.
Proceedings of the Proceedings IEEE INFOCOM 2001, 2001
Using Multiple Hash Functions to Improve IP Lookups.
Proceedings of the Proceedings IEEE INFOCOM 2001, 2001
Towards Compressing Web Graphs.
Proceedings of the Data Compression Conference, 2001
Estimating Resemblance of MIDI Documents.
Proceedings of the Algorithm Engineering and Experimentation, Third International Workshop, 2001
2000
How Useful Is Old Information?
IEEE Trans. Parallel Distributed Syst., 2000
An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings.
SIAM J. Comput., 2000
Average-case analyses of first fit and random fit bin packing.
Random Struct. Algorithms, 2000
Min-Wise Independent Permutations.
J. Comput. Syst. Sci., 2000
On near-uniform URL sampling.
Comput. Networks, 2000
An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000
Improved classification via connectivity information.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000
FLID-DL: congestion control for layered multicast.
Proceedings of the Networked Group Communication, 2000
1999
On the Analysis of Randomized Load Balancing Schemes.
Theory Comput. Syst., 1999
Studying Balanced Allocations With Differential Equations.
Comb. Probab. Comput., 1999
Measuring Index Quality Using Random Walks on the Web.
Comput. Networks, 1999
Unscrambling Address Lines.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads.
Proceedings of the Proceedings IEEE INFOCOM '99, 1999
1998
Parallel randomized load balancing.
Random Struct. Algorithms, 1998
Average Case Analyses of List Update Algorithms, with Applications to Data Compression.
Algorithmica, 1998
Analysis of Low Density Codes and Improved Designs Using Irregular Graphs.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Min-Wise Independent Permutations (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Analyses of Load Stealing Models Based on Differential Equations.
Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, 1998
Analysis of Random Processes via And-Or Tree Evaluation.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998
A Digital Fountain Approach to Reliable Distribution of Bulk Data.
Proceedings of the ACM SIGCOMM 1998 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, August 31, 1998
On Balls and Bins with Deletions.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998
1997
Revisiting the Counter Algorithms for List Update.
Inf. Process. Lett., 1997
Constant Time per Edge is Optimal on Rooted Tree Networks.
Distributed Comput., 1997
Practical Loss-Resilient Codes.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
How Useful Is Old Information? (Extended Abstract).
Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, 1997
1996
Designing stimulating programming assignments for an algorithms course: a collection of exercises based on random graphs.
ACM SIGCSE Bull., 1996
Bounds on the Greedy Routing Algorithm for Array Networks.
J. Comput. Syst. Sci., 1996
Load Balancing and Density Dependent Jump Markov Processes (extended abstract).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
Pattern-based Compression of Text Images.
Proceedings of the 6th Data Compression Conference (DCC '96), Snowbird, Utah, USA, March 31, 1996
1995
Parallel randomized load balancing (Preliminary Version).
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995
1994
Computational Complexity of Loss Networks.
Theor. Comput. Sci., 1994