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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>

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 >>>