Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INVARIANCE PRINCIPLE:
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

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