14 citations · 51 across the 29 of their papers we have counts for
6 papers · 1 filter
Global and fixed-terminal cuts in digraphs
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +2
The computational complexity of multicut-like problems may vary significantly depending on whether the terminals are fixed or not. In this work we present a comprehensive study of…
Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami +2
We consider the following basic problem: given an -variate degree- homogeneous polynomial with real coefficients, compute a unit vector that maximize…
LP-branching algorithms based on biased graphs
Euiwoong Lee, Magnus Wahlström
We give a combinatorial condition for the existence of efficient, LP-based FPT algorithms for a broad class of graph-theoretical optimisation problems. Our condition is based on th…
Improved Hardness for Cut, Interdiction, and Firefighter Problems
Euiwoong Lee
We study variants of the classic - cut problem and prove the following improved hardness results assuming the Unique Games Conjecture (UGC). - For any constant and…
Partitioning a Graph into Small Pieces with Applications to Path Transversal
Euiwoong Lee
Given a graph and an integer , we study -Vertex Seperator (resp. -Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) su…
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee
For an -variate order- tensor , define to be the maximum value taken by the tensor on the unit sphere…