Stem inapproxim$ (all stems)

22 papers:

STOC-2015-BraunPZ #combinator #problem

Inapproximability of Combinatorial Problems via Small LPs and SDPs (GB, SP, DZ), pp. 107–116.

STOC-2015-DanielySS

Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension (AD, MS, GS), pp. 401–408.

STOC-2015-Rubinstein #equilibrium #nash

Inapproximability of Nash Equilibrium (AR), pp. 409–418.

STOC-2014-GalanisSV

Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region (AG, DS, EV), pp. 823–831.

STOC-2011-Yoshida #algorithm #approximate #bound #csp

Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP (YY), pp. 665–674.

ICALP-v1-2010-BansalK #problem #scheduling

Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems (NB, SK), pp. 250–261.

ICALP-v1-2010-GuruswamiS #on the

On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs (VG, RS), pp. 360–371.

STOC-2008-Raghavendra #algorithm #csp #question

Optimal algorithms and inapproximability results for every CSP? (PR), pp. 245–254.

STOC-2008-SkopalikV #nash

Inapproximability of pure nash equilibria (AS, BV), pp. 355–364.

STOC-2007-GoldbergJ #polynomial

Inapproximability of the Tutte polynomial (LAG, MJ), pp. 459–468.

DLT-2007-GruberH #complexity #exclamation #nondeterminism

Inapproximability of Nondeterministic State and Transition Complexity Assuming P=!NP (HG, MH), pp. 205–216.

STOC-2006-Zuckerman #clique #linear

Linear degree extractors and the inapproximability of max clique and chromatic number (DZ), pp. 681–690.

ICALP-v1-2006-KhotP #clique

Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion (SK, AKP), pp. 226–237.

ICALP-2005-LinRTW #exponential #fibonacci

Braess’s Paradox, Fibonacci Numbers, and Exponential Inapproximability (HCL, TR, ÉT, AW), pp. 497–512.

STOC-2003-HalperinK

Polylogarithmic inapproximability (EH, RK), pp. 585–594.

ICALP-2002-EngebretsenHR #equation #finite

Inapproximability Results for Equations over Finite Groups (LE, JH, AR), pp. 73–84.

ICALP-2002-Holmerin

Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs (JH), pp. 1005–1016.

STOC-2000-Srinivasan #clique

The value of strong inapproximability results for clique (AS), pp. 144–152.

ICALP-2000-ElkinP #problem

Strong Inapproximability of the Basic k-Spanner Problem (ME, DP), pp. 636–647.

ICALP-1999-BermanK #on the

On Some Tighter Inapproximability Results (Extended Abstract) (PB, MK), pp. 200–209.

ICALP-1999-Umans #complexity #on the #problem

On the Complexity and Inapproximability of Shortest Implicant Problems (CU), pp. 687–696.

STOC-1997-Hastad

Some Optimal Inapproximability Results (JH), pp. 1–10.