Research Contributions

Home

Entropy

A Physical Framework for Algorithmic Entropy

Why Turing's Computable Numbers Are Only Non-Constructively Closed Under Addition
    Entropy 2026, 28(1), 71, Special Issue pdf

Machine Learning

``All'' Critical Gradient Decent Solutions Are Optimal (Given Minimal Over-Parameterization) pdf, (slides)

Logarithmic Gradient Descent Running time (Given Minimal Over-Parameterization and crazy assumptions) pdf

Implications of Modeled Beliefs for Algorithmic Fairness in Machine Learning.
    (with Ruth Urner & Karan Singh)
    Workshop on Algorithmic Fairness through the Lens of Causality and Robustness - Workshop @ NeurIPS 2021. pdf

Scheduling

ResVMAC: A Novel Medium Access Control Protocol for Vehicular Ad hoc Networks
    (with Md Kowsar Hossain, Suprakash Datta, Sk Imran Hossain)
    Journal Procedia Computer Science pdf

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 & Algorithmica 2011 pdf

Scalably Scheduling Processes with Arbitrary Speedup Curves (LAPS is Latest Arrival Processor Sharing or 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 & Journal Theoretical Computer Science 2012 pdf
    * Warning: I do not do TCP AT ALL. I am a theory person. I prove theorems.

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

Random Polyhedral Scenes: An Image Generator for Active Vision System Experiments
    (With Markus Solbach, Stephen Voland, and John K Tsotsos)
    arXiv preprint arXiv:1803.10100} 2018/3/27 pdf
Branching Width when Solving Random Jigsaw Puzzles with a Planted Solution
    (With Alex Edmonds)
    submitted to Algorithmica. pdf
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
    (with Kirk Pruhs)
    SODA 2006 pdf ACM Transactions on Algorithms 2011   talk.ppt

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

Erasure Codes with a Hierarchical Bundle Structure
    (with M. Luby)
    IEEE Transactions on Information Theory 2017 pdf
An Efficient MAC protocol for Wireless Sensor and Ad Hoc Networks
    (with S. Datta and K. Hossain)
    ANT15 pdf
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
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)
    Master's Thesis 2008 pdf
The Power of Free Branching in a General Model of Backtracking and Dynamic Programming Algorithms
    (with S. Davis and R. Impagliazzo)
    Algorithmica 2015 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

Beating Neciporuk on the Tree Evaluation Problem
    (with Stephen Cook, Venkatesh Medabalimi, Ian Mertz, Toniann Pitassi)
    To be solved pdf
Hardness of Function Composition for Semantic Read once Branching Programs
    (with Venkatesh Medabalimi, Toniann Pitassi)
    Computational Complexity Conference, 2018. pdf
Improved Analysis of the Online Set Cover Problem with Advice
    (with Dobreva, Kommc Kralovic, Kralovic, Krug, and Momke)
    Submitted to Journal of Theoretic Computer Science. pdf

Lower Bounds for Nondeterministic Semantic Read-Once Branching
    (with Stephen Cook, Venkatesh Medabalimi, Toniann Pitassi)
    ICALP 2016 pdf

A Little Advice Can Be Very Helpful or Upper and Lower Bounds on the Power of Advice
    (With A. Chattopadhyay, F. Ellen, and T. Pitassi)
    SODA 2012 & SIAM Journal on Computing (SICOMP), 2016 pdf Video

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