Research Contributions
Home
Scheduling
-
Every Deterministic Nonclairvoyant Scheduler has a Suboptimal Load Threshold
-
Online Scalable Scheduling for the ell_k-norms of Flow Time
Without Conservation of Work
(with Sungjin Im and Benjamin Moseley)
SODA 2011
pdf
-
Speed Scaling of Processes with Arbitrary Speedup Curves on a
Multiprocessor
(with Ho Leung Chan and Kirk Pruhs)
SPAA09 ACM Symp. of Parallelism in Algorithms and Architectures
& Theory of Computing Systems 2011 pdf
-
Nonclairvoyant Speed Scaling for Flow and Energy
(with Ho-Leung Chan,
Tak-Wah Lam,
Lap-Kei Lee,
Alberto Marchetti-Spaccamela,
and Kirk Pruhs)
STACS 2009, Symposium on Theoretical Aspects of Computer Science
& Submitted to Algorithmica pdf
-
Scalably Scheduling Processes with Arbitrary Speedup Curves
(Better Scheduling in the Dark)
-
Online Algorithms To Minimize Resource Reallocations and
Network Communication
(with S. Davis and R. Impagliazzo)
Approx06: 9th International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems pdf
-
A Maiden Analysis of Longest Wait First
(with Kirk Pruhs)
SODA 2004 & ACM Transactions on Algorithms
pdf
talk.ppt
-
On the Competitiveness of AIMD-TCP within a General Network
Latin American Theoretical Informatics 2004 pdf
-
TCP is Competitive with Resource Augmentation (Against a Limited Adversary)
(with Suprakash Datta and Patrick Dymond)
ACM Symp. of Parallelism in Algorithms and Achitectures 2003
& Theory of Computing Systems 2010
pdf
talk.ppt
-
RQM: A new rate-based active queue management algorithm.
(with Suprakash Datta, Patrick Dymond, and Kashif Ali)
York University Technical Report CSE-2006-09. pdf
-
Multicast Pull Scheduling: When Fairness Is Fine
(with Kirk Pruhs)
SODA 2002 & Special Issue Algorithmica on Online Algorithms 2003
pdf
-
Scheduling in the Dark
STOC 1999, Journal of Theoretic Computer Science 1999,
& Springer ``Encyclopedia of
Algorithms'' 2008
pdf
talk.pdf
pdf
-
Non-clairvoyant Multiprocessor Scheduling of Jobs
with Changing Execution Characteristics
(with D. Chinn, T. Brecht, and X. Deng)
STOC 1997 & Special Issue of Journal of Scheduling on
Online Problems 2003
pdf
Longer.pdf
Algorithms
-
Bounding Variance and Expectation of Longest Path Lengths in DAGs from
Variance and Expectation of Edge Lengths
-
Confidently Cutting a Cake into Approximately Fair Pieces
(with Kirk Pruhs and Jai Solanki)
Conference on Algorithmic Aspects in Information and Management (AAIM), 2008.
pdf
-
Balanced Allocations of Cake
-
Cake Cutting Really is Not a Piece of Cake
Data Bases
-
Mining for Empty Rectangles in Large Data Sets
(with J. Gryz, R Miller, and D. Liang)
International Conference on Database Theory
2001 & Journal Theoretical Computer Science 2003
pdf
talk.ppt
Patented.
Data Transmission
-
Towards Asymptotic Optimality in Probabilistic Packet Marking
(with M. Adler and J. Matousek)
STOC05 pdf
-
Linear Time Erasure Codes with Nearly Optimal Recovery
(with N. Alon and M. Luby)
FOCS 95 pdf
Journal Submission pdf
-
Prioritized Encoding Transmission
(with A. Albanese, J. Blömer, M. Luby, and M. Sudan)
FOCS 1994 &
IEEE Transactions on Information Theory 1996
pdf
Time-Space Trade-off Lower Bounds
-
Super Poly Time-Space Lower Bounds for Directed st-Connectivity on an NNJAG
(with C. K. Poon and D. Achlioptas)
Si-Comp Journal pdf
talk.pdf
-
Time-Space Lower Bounds for Directed st-Connectivity on JAG Models
(with G. Barnes)
FOCS 93 & SIAM Journal on Computing pdf
-
Time-Space Trade-offs for Undirected st-Connectivity on a JAG
STOC 93 & SIAM Journal on Computing pdf
-
Towards Time-Space Lower Bounds on Branching Programs
-
Ph.D. Thesis, JAGs.
pdf
Proof Systems
-
Using the Groebner basis algorithm to find proofs of unsatisfiability
(with M. Clegg, R. Impagliazzo)
STOC 95 pdf
Complexity Classes
-
Improved Results on Models of Greedy and Primal-Dual Algorithms
(with Allan Borodin and James Kwon)
To be submitted
pdf
- The
Power of Free Branching in a General Model of Backtracking and Dynamic
Programming Algorithms
(with S. Davis and R. Impagliazzo)
To be submitted
pdf
-
The relative complexity of NP search problems
(with P. Beame, S. Cook, R. Impagliazzo, and T. Pitassi)
STOC 95 & Journal of Computer System Sciences, 1998
pdf
Geometry
-
Hardness of Embedding into R^2 with Constant
Distortion
(with Anastasios Sidiropoulos, and Anastasios Zouzias)
SODA 2010.
pdf
talk.pdf
-
Embedding into l^2_{\infty} is Easy
Embedding into l^3_{\infty} is NP-Complete
(Thanks goes to Steve Watson and Jiri Matousek)
SODA 2007 & Journal of Discrete and Computational Geometry. pdf
General Lower Bounds
-
A Little Advice Can Be Very Helpful
(With A. Chattopadhyay, F. Ellen, and T. Pitassi)
SODA 2012
pdf
Communication Complexity: Towards Lower Bounds on Circuit Depth
(with R. Impagliazzo, S. Rudich, and J. Sgall)
FOCS 1991 & Journal of Computational Complexity pdf
Lower Bounds with Smaller Domain Size on Concurrent Write Parallel Machines
Structures in Complexity Theory & Journal of Theoretic Computer
Science 1997 pdf