9 citations · 20 across the 7 of their papers we have counts for
9 papers
Verification under TSO with an infinite Data Domain
Parosh Aziz Abdulla, Mohamed Faouzi Atig, Florian Furbach +1
We examine verification of concurrent programs under the total store ordering (TSO) semantics used by the x86 architecture. In our model, threads manipulate variables over infinite…
Quasi-PTAS for Scheduling with Precedences using LP Hierarchies
Shashwat Garg
A central problem in scheduling is to schedule unit size jobs with precedence constraints on identical machines so as to minimize the makespan. For , it is not even kn…
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg +1
An important result in discrepancy due to Banaszczyk states that for any set of vectors in of norm at most and any convex body in …
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
Daniel Dadush, Shashwat Garg, Shachar Lovett +1
An important theorem of Banaszczyk (Random Structures & Algorithms `98) states that for any sequence of vectors of norm at most and any convex body of Gaussian m…
Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems
Nikhil Bansal, Shashwat Garg, Jesper Nederlof +1
We present space efficient Monte Carlo algorithms that solve Subset Sum and Knapsack instances with items using time and polynomial space, where the $O^*(\cdot…
Algorithmic Discrepancy Beyond Partial Coloring
Nikhil Bansal, Shashwat Garg
The partial coloring method is one of the most powerful and widely used method in combinatorial discrepancy problems. However, in many cases it leads to sub-optimal bounds as the p…