21 citations · 47 across the 19 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.CC2013
Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs
Rishi Saket
This work revisits the PCP Verifiers used in the works of Hastad [Has01], Guruswami et al.[GHS02], Holmerin[Hol02] and Guruswami[Gur00] for satisfiable Max-E3-SAT and Max-Ek-Set-Sp…
cs.CC2013
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
Subhash Khot, Rishi Saket
This work studies the hardness of finding independent sets in hypergraphs which are either 2-colorable or are almost 2-colorable, i.e. can be 2-colored after removing a small fract…
cs.DS2013★ 9 cited
A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure
Rishi Saket
We present a polynomial time approximation scheme (PTAS) for the minimum value of the classical Ising Hamiltonian with linear terms on the Chimera graph structure as defined in the…