Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Invariance Principle:
TR05-039 | 13th April 2005
Irit Dinur, Elchanan Mossel, Oded Regev

Conditional Hardness for Approximate Coloring

We study the approximate-coloring(q,Q) problem: Given a graph G, decide
whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional
hardness for this problem for any constant 3\le q < Q. For q \ge
4, our result is based on Khot's 2-to-1 conjecture [Khot'02].
For q=3, we base our hardness ... more >>>

TR10-111 | 14th July 2010
Venkatesan Guruswami, Ali Kemal Sinop

The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

We prove almost tight hardness results for finding independent sets in bounded degree graphs and hypergraphs that admit a good
coloring. Our specific results include the following (where $\Delta$, assumed to be a constant, is a bound on the degree, and
$n$ is the number of vertices):

... more >>>

TR10-185 | 2nd December 2010
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

Agnostic Learning of Monomials by Halfspaces is Hard

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples, it is $\mathrm{NP}$-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples, for arbitrary constants $\epsilon ... more >>>

TR14-043 | 2nd April 2014
Venkatesan Guruswami, Euiwoong Lee

Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

Consider a $K$-uniform hypergraph $H = (V,E)$. A coloring $c : V \rightarrow \{1, 2, \dots, k \}$ with $k$ colors is rainbow if every hyperedge $e$ contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A ... more >>>

TR16-104 | 14th July 2016
Badih Ghazi, Pritish Kamath, Madhu Sudan

Decidability of Non-Interactive Simulation of Joint Distributions

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions $P(x,y)$ and $Q(u,v)$: The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where ... more >>>

TR17-080 | 1st May 2017
Joshua Brakensiek, Venkatesan Guruswami

The Quest for Strong Inapproximability Results with Perfect Completeness

The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect ... more >>>

TR19-148 | 1st November 2019
Amey Bhangale, Subhash Khot

Simultaneous Max-Cut is harder to approximate than Max-Cut

Revisions: 1

A systematic study of simultaneous optimization of constraint satisfaction problems was initiated in [BKS15]. The simplest such problem is the simultaneous Max-Cut. [BKKST18] gave a $.878$-minimum approximation algorithm for simultaneous Max-Cut which is {\em almost optimal} assuming the Unique Games Conjecture (UGC). For a single instance Max-Cut, [GW95] gave an ... more >>>

TR21-013 | 20th January 2021
Srinivasan Arunachalam, Penghui Yao

Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary $m$-facet polytopes in $n$ variables with seed length poly-logarithmic in $m,n$, concluding a sequence of works in the last decade, that was started by Diakonikolas, Gopalan, Jaiswal, Servedio, Viola (SICOMP 2010) and Meka, ... more >>>

ISSN 1433-8092 | Imprint