On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems

by Per Austrin, Rajsekar Manokaran, and Cenny Wenner

Theory of Computing, Volume 11(10), pp. 257-283, 2015

Bibliography with links to cited articles

[1]   Sanjeev Arora, Boaz Barak, and David Steurer: Subexponential algorithms for Unique Games and related problems. In Proc. 51st FOCS, pp. 563–572. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.59]

[2]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. Versions in ECCC and FOCS’92. [doi:10.1145/278298.278306]

[3]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92. [doi:10.1145/273865.273901]

[4]   Per Austrin, Rajsekar Manokaran, and Cenny Wenner: On the NP-hardness of approximating Ordering Constraint Satisfaction Problems. In Proc. 16th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’13), pp. 26–41, 2013. [doi:10.1007/978-3-642-40328-6_3]

[5]   Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou: Hypercontractivity, sum-of-squares proofs, and their applications. In Proc. 44th STOC, pp. 307–326. ACM Press, 2012. [doi:10.1145/2213977.2214006, arXiv:1205.4484]

[6]   Siu On Chan: Approximation resistance from pairwise independent subgroups. In Proc. 45th STOC, pp. 447–456. ACM Press, 2013. Version in ECCC. [doi:10.1145/2488608.2488665]

[7]   Moses Charikar, Venkatesan Guruswami, and Rajsekar Manokaran: Every permutation CSP of arity 3 is approximation resistant. In Proc. 24th IEEE Conf. on Computational Complexity (CCC’09), pp. 62–73, 2009. [doi:10.1109/CCC.2009.29]

[8]   Moses Charikar, Konstantin Makarychev, and Yury Makarychev: On the advantage over random for Maximum Acyclic Subgraph. In Proc. 48th FOCS, pp. 625–633. IEEE Comp. Soc. Press, 2007. Version in ECCC. [doi:10.1109/FOCS.2007.65]

[9]   Benny Chor and Madhu Sudan: A geometric approach to betweenness. SIAM J. Discrete Math., 11(4):511–523, 1998. Preliminary version in ESA’95. [doi:10.1137/S0895480195296221]

[10]   Bradley Efron and Charles Stein: The Jackknife Estimate of Variance. Annals of Statistics, 9(3):586–596, 1981. [doi:10.1214/aos/1176345462]

[11]   Lars Engebretsen and Jonas Holmerin: More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Struct. Algorithms, 33(4):497–514, 2008. Preliminary version in STACS’05. [doi:10.1002/rsa.20226]

[12]   Michael R. Garey and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979.

[13]   Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar: Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM J. Comput., 40(3):878–914, 2011. Version in ECCC. [doi:10.1137/090756144]

[14]   Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra: Beating the random ordering is hard: Inapproximability of Maximum Acyclic Subgraph. In Proc. 49th FOCS, pp. 573–582. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.51]

[15]   Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, and Yi Wu: Bypassing UGC from some optimal geometric inapproximability results. In Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’12), pp. 699–717. ACM Press, 2012. Available on ACM DL. Preliminary version in ECCC.

[16]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]

[17]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. Also in CCC’02. [doi:10.1145/509907.510017]

[18]   Elchanan Mossel: Gaussian bounds for noise correlation of functions. Geometric and Functional Analysis, 19(6):1713–1756, 2010. Preliminary version in FOCS’08. [doi:10.1007/s00039-010-0047-x]

[19]   Alantha Newman: The Maximum Acyclic Subgraph Problem and degree-3 graphs. In Proc. 4th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’01), pp. 147–158. Springer, 2001. [doi:10.1007/3-540-44666-4_18]

[20]   Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. Preliminary version in STOC’95. [doi:10.1137/S0097539795280895]

[21]   Alex Samorodnitsky and Luca Trevisan: A PCP characterization of NP with optimal amortized query complexity. In Proc. 32nd STOC, pp. 191–199. ACM Press, 2000. [doi:10.1145/335305.335329]

[22]   Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. SIAM J. Comput., 39(1):323–360, 2009. Preliminary version in STOC’06. [doi:10.1137/070681612]

[23]   Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson: Gadgets, approximation, and linear programming. SIAM J. Comput., 29(6):2074–2097, 2000. Preliminary version in FOCS’96. [doi:10.1137/S0097539797328847]

[24]   Cenny Wenner: Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Theory of Computing, 9(23):703–757, 2013. Preliminary version in APPROX’12. [doi:10.4086/toc.2013.v009a023]

[25]   Paweł Wolff: Hypercontractivity of simple random variables. Studia Mathematica, 180(3):219–236, 2007. [doi:10.4064/sm180-3-3]