Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel-Access Attempts, and Robustness.
Deterministic Edge Connectivity in Near-Linear Time.
Engineering with Logic: Rigorous Test-Oracle Specification and Validation for TCP/IP and the Sockets API.
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning.
The PCL Theorem: Transactions cannot be Parallel, Consistent, and Live.
Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time.
Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems.