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