Research Contributions

Home

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.

Scheduling

ResVMAC: A Novel Medium Access Control Protocol for Vehicular Ad hoc Networks

Every Deterministic Nonclairvoyant Scheduler has a Suboptimal Load Threshold

Online Scalable Scheduling for the ell_k-norms of Flow Time Without Conservation of Work

Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor

Nonclairvoyant Speed Scaling for Flow and Energy

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

A Maiden Analysis of Longest Wait First

On the Competitiveness of AIMD-TCP within a General Network

TCP is Competitive with Resource Augmentation (Against a Limited Adversary)

RQM: A new rate-based active queue management algorithm.

Multicast Pull Scheduling: When Fairness Is Fine

Scheduling in the Dark

Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics

Algorithms

Random Polyhedral Scenes: An Image Generator for Active Vision System Experiments
Branching Width when Solving Random Jigsaw Puzzles with a Planted Solution
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
Balanced Allocations of Cake
Cake Cutting Really is Not a Piece of Cake

Data Bases

Mining for Empty Rectangles in Large Data Sets

Data Transmission

Erasure Codes with a Hierarchical Bundle Structure
An Efficient MAC protocol for Wireless Sensor and Ad Hoc Networks
Towards Asymptotic Optimality in Probabilistic Packet Marking
Linear Time Erasure Codes with Nearly Optimal Recovery
Prioritized Encoding Transmission

Time-Space Trade-off Lower Bounds

Super Poly Time-Space Lower Bounds for Directed st-Connectivity on an NNJAG

Time-Space Lower Bounds for Directed st-Connectivity on JAG Models

Time-Space Trade-offs for Undirected st-Connectivity on a JAG

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

Complexity Classes

Improved Results on Models of Greedy and Primal-Dual Algorithms
The Power of Free Branching in a General Model of Backtracking and Dynamic Programming Algorithms
The relative complexity of NP search problems

Geometry

Hardness of Embedding into R^2 with Constant Distortion
Embedding into l^2_{\infty} is Easy Embedding into l^3_{\infty} is NP-Complete

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

Communication Complexity: Towards Lower Bounds on Circuit Depth

Lower Bounds with Smaller Domain Size on Concurrent Write Parallel Machines