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
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
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response
Erlingsson, Ú., Pihur, V., & Korolova, A. (2014) · Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2660267.2660348 · Cited by 1,838
Huang, L., Joseph, A. D., Nelson, B., Rubinstein, B. I. P., & Tygar, J. D. (2011) · Proceedings of the 4th ACM workshop on Security and artificial intelligence · doi:10.1145/2046684.2046692 · Cited by 1,194
(2011) · PubMed · Cited by 990
Federated Learning for Internet of Things: Recent Advances, Taxonomy, and Open Challenges
Khan, L. U., Saad, W., Han, Z., Hossain, E., & Hong, C. S. (2021) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2021.3090430 · Cited by 892
Differential Privacy Techniques for Cyber Physical Systems: A Survey
Hassan, M. U., Rehmani, M. H., & Chen, J. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2019.2944748 · Cited by 564
Local Differential Privacy-Based Federated Learning for Internet of Things
Zhao, Y., Zhao, J., Yang, M., Wang, T., Wang, N., Lyu, L., Niyato, D., & Lam, K.-Y. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.3037194 · Cited by 456
Differentially Private Spatial Decompositions
Cormode, G., Procopiuc, C., Srivastava, D., Shen, E., & Yu, T. (2012) · 2012 IEEE 28th International Conference on Data Engineering · doi:10.1109/icde.2012.16 · Cited by 411
Airavat: security and privacy for MapReduce
Roy, I., Setty, S., Kilzer, A., Shmatikov, V., & Witchel, E. (2010) · doi:10.5555/1855711.1855731 · Cited by 393
Scalable Private Learning with PATE
Papernot, N., Song, S., Mironov, I., Raghunathan, A., Talwar, K., & Erlingsson, Ú. (2018) · arXiv · doi:10.48550/arxiv.1802.08908 · Cited by 373
Broadening the Scope of Differential Privacy Using Metrics
Chatzikokolakis, K., Andrés, M. E., Bordenabe, N. E., & Palamidessi, C. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-39077-7_5 · Cited by 340
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.27 · Cited by 334
Big privacy: challenges and opportunities of privacy study in the age of big data
Yu, S. (2016) · IEEE Access · doi:10.1109/access.2016.2577036 · Cited by 307
A survey of edge computing-based designs for IoT security
Sha, K., Yang, T. A., Wei, W., & Davari, S. (2020) · Digital Communications and Networks · doi:10.1016/j.dcan.2019.08.006 · Cited by 295
Noise stability of functions with low influences: Invariance and optimality
Mossel, E., O’Donnell, R., & Oleszkiewicz, K. (2010) · Annals of Mathematics · doi:10.4007/annals.2010.171.295 · Cited by 288
Evaluating Differentially Private Machine Learning in Practice
Jayaraman, B., & Evans, D. (2019) · arXiv · doi:10.48550/arxiv.1902.08874 · Cited by 265
Trustworthy ai: A computational perspective
Liu, H., Wang, Y., Fan, W., Liu, X., Li, Y., Jain, S., Liu, Y., Jain, A., & Tang, J. (2023) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3546872 · Cited by 261
Differentially private grids for geospatial data
Qardaji, W., Yang, W., & Li, N. (2013) · 2013 IEEE 29th International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2013.6544872 · Cited by 260
Distributed Privacy-Preserving Collaborative Intrusion Detection Systems for VANETs
Zhang, T., & Zhu, Q. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2018.2801622 · Cited by 168
Enhancing data utility in differential privacy via microaggregation-based $$k$$ k -anonymity
Soria-Comas, J., Domingo-Ferrer, J., Sánchez, D., & Martínez, S. (2014) · The VLDB Journal · doi:10.1007/s00778-014-0351-4 · Cited by 149
Rodríguez-Barroso, N., Stipcich, G., Jiménez-López, D., Ruiz-Millán, J. A., Martínez-Cámara, E., González-Seco, G., Luzón, M. V., Veganzones, M. A., & Herrera, F. (2020) · Information Fusion · doi:10.1016/j.inffus.2020.07.009 · Cited by 148
On the Compatibility of Privacy and Fairness
Cummings, R., Gupta, V., Kimpara, D., & Morgenstern, J. (2019) · Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization · doi:10.1145/3314183.3323847 · Cited by 133
Privacy in Internet of Things: From Principles to Technologies
Li, C., & Palanisamy, B. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2864168 · Cited by 130
A Survey on Differentially Private Machine Learning [Review Article]
Gong, M., Xie, Y., Pan, K., Feng, K., & Qin, A. K. (2020) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2020.2976185 · Cited by 115
InPrivate Digging: Enabling Tree-based Distributed Data Mining with Differential Privacy
Zhao, L., Ni, L., Hu, S., Chen, Y., Zhou, P., Xiao, F., & Wu, L. (2018) · IEEE INFOCOM 2018 - IEEE Conference on Computer Communications · doi:10.1109/infocom.2018.8486352 · Cited by 108
Discrimination- and privacy-aware patterns
Hajian, S., Domingo-Ferrer, J., Monreale, A., Pedreschi, D., & Giannotti, F. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0393-7 · Cited by 93
Anonymisation Models for Text Data: State of the art, Challenges and Future Directions
Lison, P., Pilán, I., Sanchez, D., Batet, M., & Øvrelid, L. (2021) · Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers) · doi:10.18653/v1/2021.acl-long.323 · Cited by 80
Wireless Network Intelligence at the Edge
Park, J., Samarakoon, S., Bennis, M., & Debbah, M. (2019) · Proceedings of the IEEE · doi:10.1109/jproc.2019.2941458 · Cited by 92
Differentially Private Fair Learning
Jagielski, M., Kearns, M., Mao, J., Oprea, A., Roth, A., Sharifi-Malvajerdi, S., & Ullman, J. (2018) · arXiv · doi:10.48550/arxiv.1812.02696 · Cited by 62
Secure and robust machine learning for healthcare: A survey
Qayyum, A., Qadir, J., Bilal, M., & Al-Fuqaha, A. (2021) · IEEE Reviews in Biomedical Engineering · doi:10.1109/rbme.2020.3013489 · Cited by 59
FCMF: Federated collective matrix factorization for heterogeneous collaborative filtering
Yang, E., Huang, Y., Liang, F., Pan, W., & Ming, Z. (2021) · Knowledge-Based Systems · doi:10.1016/j.knosys.2021.106946 · Cited by 58
SafePath: Differentially-private publishing of passenger trajectories in transportation systems
Al-Hussaeni, K., Fung, B. C. M., Iqbal, F., Dagher, G. G., & Park, E. G. (2018) · Computer Networks · doi:10.1016/j.comnet.2018.07.007 · Cited by 52
Differentially private user-based collaborative filtering recommendation based on k-means clustering
Chen, Z., Wang, Y., Zhang, S., Zhong, H., & Chen, L. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.114366 · Cited by 42
On the Power of Multiple Anonymous Messages
Ghazi, B., Golowich, N., Kumar, R., Pagh, R., & Velingker, A. (2019) · arXiv · doi:10.48550/arxiv.1908.11358 · Cited by 26
Differential Privacy Defenses and Sampling Attacks for Membership Inference
Rahimian, S., Orekondy, T., & Fritz, M. (2021) · Proceedings of the 14th ACM Workshop on Artificial Intelligence and Security · doi:10.1145/3474369.3486876 · Cited by 24
Angelopoulos, A. N., Bates, S., Zrnic, T., & Jordan, M. I. (2022) · Harvard Data Science Review · doi:10.1162/99608f92.16c71dad · Cited by 8
Li, X., Wang, Y., Song, J., Liu, Y., Zhang, X., Zhou, K., & Li, C. (2020) · World Wide Web · doi:10.1007/s11280-019-00769-8 · Cited by 7
Minimax Rates of Estimating Approximate Differential Privacy
Liu, X., & Oh, S. (2019) · arXiv · doi:10.48550/arxiv.1905.10335 · Cited by 4
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.