4 papers
On the Strong Converse Exponent and Error Exponent of the Classical Soft Covering
Xingyi He, S. Sandeep Pradhan, Andreas Winter
This paper establishes the exact strong converse exponent of the soft covering problem in the classical setting. This exponent characterizes the slowest achievable convergence spee…
SDPs and Robust Satisfiability of Promise CSP
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfi…
Minmax-Regret -Sink Location on a Dynamic Tree Network with Uniform Capacities
Mordecai J. Golin, Sai Sandeep
A dynamic flow network with uniform capacity is a graph in which at most units of flow can enter an edge in one time unit. If flow enters a vertex faster than it can le…
Improved Hardness of Approximation for Geometric Bin Packing
Arka Ray, Sai Sandeep
The Geometric Bin Packing (GBP) problem is a generalization of Bin Packing where the input is a set of -dimensional rectangles, and the goal is to pack them into unit -dimens…