The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Towards Sharp Inapproximability For Any 2-CSP
Abstract
We continue the recent line of work on the connection between semidefinite programming-based approximation algorithms and the Unique Games Conjecture. Given any-boolean 2-CSP (or more generally, any nonnegative objective function on two boolean variables), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. The key objects in our analysis are the vector triples arising when doing clause-by-clause analysis of algorithms based on semidefinite programming. Given a weighted set of such triples of a certain restricted type, which are "hard" to round in a certain sense, we obtain a Unique Games-based inapproximability matching this "hardness" of rounding the set of vector triples. Conversely, any instance together with an SDP solution can be viewed as a set of vector triples, and we show that we can always find an assignment to the instance which is at least as good as the "hardness" of rounding the corresponding set of vector triples. We conjecture that the restricted type required for the hardness result is in fact no restriction, which would imply that these upper and lower bounds match exactly. This conjecture is supported by all existing results for specific 2-CSPs. As an application, we show that Max 2-AND is hard to approximate within 0.87435. This improves upon the best previous hardness of alphaGW+ epsi ap 0.87856, and comes very close to matching the approximation ratio of the best algorithm known, 0.87401. It also establishes that balanced instances of Max 2-AND, i.e., instances in which each variable occurs positively and negatively equally often, are not the hardest to approximate, as these can be approximated within a factor alphaGW.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Dwork, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_1 · Cited by 5,291
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,413
Probabilistic checking of proofs: a new characterization of NP
Arora, S., & Safra, S. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,153
Smooth sensitivity and sampling in private data analysis
Nissim, K., Raskhodnikova, S., & Smith, A. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250803 · Cited by 974
Security-control methods for statistical databases: a comparative study
Adam, N. R., & Worthmann, J. C. (1989) · ACM Computing Surveys · doi:10.1145/76894.76895 · Cited by 969
Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
Alizadeh, F. (1995) · SIAM Journal on Optimization · doi:10.1137/0805002 · Cited by 892
On the density of families of sets
Sauer, N. (1972) · Journal of Combinatorial Theory, Series A · doi:10.1016/0097-3165(72)90019-2 · Cited by 844
Practical privacy: the SuLQ framework
Blum, A., Dwork, C., McSherry, F., & Nissim, K. (2005) · Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1065167.1065184 · Cited by 797
Algorithmic mechanism design (extended abstract)
Nisan, N., & Ronen, A. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301287 · Cited by 476
Approximate graph coloring by semidefinite programming
Karger, D., Motwani, R., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/274787.274791 · Cited by 420
Improved approximation algorithms for MAXk-CUT and MAX BISECTION
Frieze, A., & Jerrum, M. (1997) · Algorithmica · doi:10.1007/bf02523688 · Cited by 406
Distributed algorithmic mechanism design: recent results and future directions
Feigenbaum, J., & Shenker, S. J. (2002) · international workshop on Discrete Algorithms and Methods for Mobile Computing and Communications · doi:10.1145/570810.570812 · Cited by 360
Truthful approximation mechanisms for restricted combinatorial auctions
Mu’alem, A., & Nisan, N. (2008) · Games and Economic Behavior · doi:10.1016/j.geb.2007.12.009 · Cited by 317
The value of knowing a demand curve: bounds on regret for online posted-price auctions
Kleinberg, R., & Leighton, T. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238232 · Cited by 290
Competitive auctions and digital goods
Goldberg, A. V., Hartline, J. D., & Wright, A. (2001) · doi:10.5555/365411.365768 · Cited by 257
Towards a characterization of truthful combinatorial auctions
Lavi, R., Mu’alem, A., & Nisan, N. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238230 · Cited by 236
i Bundle: an efficient ascending price bundle auction
Parkes, D. C. (1999) · Proceedings of the 1st ACM conference on Electronic commerce · doi:10.1145/336992.337032 · Cited by 215
Maximizing Quadratic Programs: Extending Grothendieck's Inequality
Charikar, M., & Wirth, A. (2004) · 45th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.39 · Cited by 214
Gadgets, Approximation, and Linear Programming
Trevisan, L., Sorkin, G. B., Sudan, M., & Williamson, D. P. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539797328847 · Cited by 199
Online learning in online auctions
Blum, A. L., Kumar, V. S., Atri Rudra, B., & Wu, F. T. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.05.012 · Cited by 159
Archer, A. F., & Eva Tardos, D. (n.d.) · Cited by 150
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
Khot, S., Kindler, G., Mossel, E., & O’Donnell, R. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.49 · Cited by 145
Zwick, U. (1998) · doi:10.5555/314613.314701 · Cited by 143
On the power of unique 2-prover 1-round games
Khot, S. (2003) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2002.1004334 · Cited by 135
An approximate truthful mechanism for combinatorial auctions with single parameter agents
Archer, A. F., Papadimitriou, C. H., Talwar, K., & Eva Tardos, D. (2003) · Symposium on Discrete Algorithms · doi:10.5555/644108.644144 · Cited by 129
Mechanism Design via Machine Learning
Balcan, M.-F., & Blum, A. L. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.50 · Cited by 129
Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems
Lewin, M., Livnat, D., & Zwick, U. (2002) · Lecture notes in computer science · doi:10.1007/3-540-47867-1_6 · Cited by 128
On the optimality of the random hyperplane rounding technique for MAX CUT
Feige, U., & Schechtman, G. (2002) · Random Structures and Algorithms · doi:10.1002/rsa.10036 · Cited by 127
Elkind, E., Sahai, A., & Steiglitz, K. (2004) · ePrints Soton (University of Southampton) · doi:10.5555/982792.982900 · Cited by 120
Gowers uniformity, influence of variables, and PCPs
Samorodnitsky, A., & Trevisan, L. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132519 · Cited by 100
Incentive-compatible online auctions for digital goods
Bar-Yossef, Z., Hildrum, K. W., & Wu, F. T. (2002) · doi:10.5555/545381.545506 · Cited by 98
Collusion-Resistant Mechanisms for Single-Parameter Agents
Goldberg, A. V., & Hartline, J. D. (2004) · doi:10.5555/1070432.1070518 · Cited by 85
New approximation guarantee for chromatic number
Arora, S., & Chlamtáč, E. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132548 · Cited by 75
Parallel Approximation Algorithms by Positive Linear Programming
Trevisan, L. (1998) · Algorithmica · doi:10.1007/pl00009209 · Cited by 70
Manasse, M. S., McSherry, F., & Talwar, K. (2007) · Cited by 67
Balanced max 2-sat might not be the hardest
Austrin, P. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250818 · Cited by 63
Self-citationConditional hardness for approximate coloring
Dinur, I., Mossel, E., & Regev, O. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132567 · Cited by 58
Goldberg, A. V., & Hartline, J. D. (2003) · doi:10.5555/644108.644145 · Cited by 56
SDP gaps and UGC-hardness for MAXCUTGAIN
Khot, S., & O’Donnell, R. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.67 · Cited by 42
Research works printed but not linked: 9
- halperin, 2001, Coloring k-colorable graphs using smaller palettes, SODA 2001, 319
- feige, 1995, Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT, ISTCS1995, 182
- khot, 2003, Vertex Cover Might be Hard to Approximate to within 2 - ?, IEEE Conference on Computational Complexity, 379
- khot, 2005, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into 11, FOCS 2005, 53
- matuura, 2001, 0.863-Approximation Algorithm for MAX DICUT, Proc APPROX-RANDOM, 138
- dinur, 2006, Independent sets in graph powers are almost contained in juntas, Geometric and Functional Analysis
- charikar, 2006, Approximation Algorithm for the Max k-CSP Problem
- 10.1016/S0020-0190(96)00190-1 · doi:10.1016/s0020-0190(96)00190-1
- 10.1109/CCC.2005.20 · doi:10.1109/ccc.2005.20
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856
Differential Privacy: A Survey of Results
Dwork, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-79228-4_1 · Cited by 3,542
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., & Zemel, R. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090255 · Cited by 3,501
Deep learning for healthcare: review, opportunities and challenges
Miotto, R., Wang, F., Wang, S., Jiang, X., & Dudley, J. T. (2018) · Briefings in Bioinformatics · doi:10.1093/bib/bbx044 · Cited by 3,076
Metadata
- Authors
- Austrin, P.
- Venue
- 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
- Publisher
- IEEE
- Published
- 2007-10
- Pages
- 307-317
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W1993116423
- Cited by
- 1,294
- References
- 42
- FWCI
- 23.07
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.