Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMABILITY:
Reports tagged with approximability:
TR96-015 | 12th December 1995
Edoardo Amaldi, Viggo Kann

On the approximability of some NP-hard minimization problems for linear systems

We investigate the computational complexity of two classes of
combinatorial optimization problems related to linear systems
and study the relationship between their approximability properties.
In the first class (MIN ULR) one wishes, given a possibly infeasible
system of linear relations, to find ... more >>>


TR97-003 | 29th January 1997
Sanjeev Arora, Madhu Sudan

Improved low-degree testing and its applications


NP = PCP(log n, 1) and related results crucially depend upon
the close connection between the probability with which a
function passes a ``low degree test'' and the distance of
this function to the nearest degree d polynomial. In this
paper we study a test ... more >>>


TR99-038 | 27th August 1999
Peter Jonsson, Paolo Liberatore

On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

We study the computational complexity of an optimization
version of the constraint satisfaction problem: given a set $F$ of
constraint functions, an instance consists of a set of variables $V$
related by constraints chosen from $F$ and a natural number $k$. The
problem is to decide whether there exists a ... more >>>


TR00-054 | 5th May 2000
Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri

On the power assignment problem in radio networks

Given a finite set $S$ of points (i.e. the stations of a radio
network) on a $d$-dimensional Euclidean space and a positive integer
$1\le h \le |S|-1$, the \minrangeh{d} problem
consists of assigning transmission ranges to the stations so as
to minimize the total power consumption, provided ... more >>>


TR10-031 | 4th March 2010
Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek

Hardness and Approximability in Multi-Objective Optimization

We systematically study the hardness and the approximability of combinatorial multi-objective NP optimization problems (multi-objective problems, for short).

We define solution notions that precisely capture the typical algorithmic tasks in multi-objective optimization. These notions inherit polynomial-time Turing reducibility from multivalued functions, which allows us to compare the solution notions and ... more >>>


TR11-163 | 2nd December 2011
Libor Barto, Marcin Kozik

Robust Satisfiability of Constraint Satisfaction Problems

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least $(1-g(\varepsilon))$-fraction of the constraints given a $(1-\varepsilon)$-satisfiable instance, where $g(\varepsilon) \rightarrow 0$ as $\varepsilon \rightarrow 0$, $g(0)=0$.
Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction ... more >>>


TR12-078 | 14th June 2012
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev

Approximate Graph Isomorphism

We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $\pi$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log n)}$ time approximation scheme that for any constant ... more >>>


TR12-111 | 5th September 2012
Venkatesan Guruswami, Ali Kemal Sinop

Faster SDP hierarchy solvers for local rounding algorithms

Convex relaxations based on different hierarchies of
linear/semi-definite programs have been used recently to devise
approximation algorithms for various optimization problems. The
approximation guarantee of these algorithms improves with the number
of {\em rounds} $r$ in the hierarchy, though the complexity of solving
(or even writing down the solution for) ... more >>>


TR16-185 | 18th November 2016
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

Revisions: 1

We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x \in \mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in many diverse contexts ranging from tensor and operator norms to graph expansion to quantum information ... 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 >>>


TR20-079 | 15th May 2020
Hermann Gruber , Markus Holzer, Simon Wolfsteiner

On Minimizing Regular Expressions Without Kleene Star

Finite languages lie at the heart of literally every regular expression. Therefore, we investigate the approximation complexity of minimizing regular expressions without Kleene star, or, equivalently, regular expressions describing finite languages. On the side of approximation hardness, given such an expression of size~$s$, we prove that it is impossible to ... more >>>


TR20-167 | 9th November 2020
Venkatesan Guruswami, Sai Sandeep

Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture

A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this ... more >>>


TR21-011 | 13th February 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Classification of the streaming approximability of Boolean CSPs

Revisions: 4 , Comments: 1

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal ... more >>>


TR21-063 | 3rd May 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Approximability of all finite CSPs in the dynamic streaming setting

Revisions: 3

A constraint satisfaction problem (CSP), Max-CSP$({\cal F})$, is specified by a finite set of constraints ${\cal F} \subseteq \{[q]^k \to \{0,1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from ${\cal F}$ to subsequences of the $n$ ... more >>>


TR21-086 | 22nd June 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

Linear Space Streaming Lower Bounds for Approximating CSPs

Revisions: 1

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints. We also identify ... more >>>


TR22-066 | 4th May 2022
Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

On sketching approximations for symmetric Boolean CSPs

A Boolean maximum constraint satisfaction problem, Max-CSP\((f)\), is specified by a predicate \(f:\{-1,1\}^k\to\{0,1\}\). An \(n\)-variable instance of Max-CSP\((f)\) consists of a list of constraints, each of which applies \(f\) to \(k\) distinct literals drawn from the \(n\) variables. For \(k=2\), Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios ... more >>>


TR22-068 | 5th May 2022
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy

Sketching Approximability of (Weak) Monarchy Predicates

Revisions: 1

We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first ... more >>>


TR24-121 | 16th July 2024
Nader Bshouty

Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

Revisions: 1

Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities.

More specifically, let $\gamma:{\mathbb R}^+\to ... more >>>




ISSN 1433-8092 | Imprint