Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with rounding schemes:
TR10-106 | 17th June 2010
Yuichi Yoshida

Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP

Revisions: 1

Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it.
In this paper, we show that a ... more >>>

TR18-097 | 15th May 2018
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Approximating Operator Norms via Generalized Krivine Rounding

We consider the $(\ell_p,\ell_r)$-Grothendieck problem, which seeks to maximize the bilinear form $y^T A x$ for an input matrix $A \in {\mathbb R}^{m \times n}$ over vectors $x,y$ with $\|x\|_p=\|y\|_r=1$. The problem is equivalent to computing the $p \to r^\ast$ operator norm of $A$, where $\ell_{r^*}$ is the dual norm ... more >>>

TR22-160 | 31st October 2022
Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, N. V. Vinodchandran

The Geometry of Rounding

Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of $\mathbb{R}^d$ are equivalent, we introduce the following natural partition problem which we call the secluded hypercube partition problem: Given $k\in\mathbb{N}$ (ideally small) and $\epsilon>0$ (ideally large), is there a partition of ... more >>>

ISSN 1433-8092 | Imprint