3 papers
cs.GT2022
An Improved Lower Bound for Matroid Intersection Prophet Inequalities
Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg
We consider prophet inequalities subject to feasibility constraints that are the intersection of matroids. The best-known algorithms achieve a -approximation, even when r…
math.NT2021
Elementary analysis of isolated zeroes of a polynomial system
Mitali Bafna, Madhu Sudan, Santhoshini Velusamy +1
Wooley ({\em J. Number Theory}, 1996) gave an elementary proof of a Bezout like theorem allowing one to count the number of isolated integer roots of a system of polynomial equatio…
cs.CC2020
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an…