乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T06:39:27Z","timestamp":1729665567882,"version":"3.28.0"},"reference-count":105,"publisher":"IEEE","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,6]]},"DOI":"10.1109\/ccc.2010.19","type":"proceedings-article","created":{"date-parts":[[2010,7,12]],"date-time":"2010-07-12T14:21:40Z","timestamp":1278944500000},"page":"99-121","source":"Crossref","is-referenced-by-count":30,"title":["On the Unique Games Conjecture (Invited Survey)"],"prefix":"10.1109","author":[{"given":"Subhash","family":"Khot","sequence":"first","affiliation":[]}],"member":"263","reference":[{"key":"ref39","first-page":"733","article-title":"Two-prover one-round proof systems, their power and their problems","author":"feige","year":"1992","journal-title":"Proceedings of the 24th Annual ACM Symposium on the Theory of Computing"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.39"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132594"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2004.1313847"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502795"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.36"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509915"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"ref34","article-title":"A new multilayered PCP and the hardness of hypergraph vertex cover","author":"dinur","year":"2002","journal-title":"Proc ACM Symposium on Theory of Computing"},{"journal-title":"Compression bounds for Lipschitz maps from the Heisenberg group to l1 Preprint","year":"2009","author":"cheeger","key":"ref28"},{"key":"ref27","first-page":"129","author":"cheeger","year":"2006","journal-title":"On the differentiation of Lipschitz maps from metric measure spaces to Banach spaces"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.47"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02785861"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132547"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1687"},{"journal-title":"A simple invariance theorem arXiv mathI0508213vl","year":"2005","author":"chatterjee","key":"ref24"},{"key":"ref23","article-title":"Near-optimal algorithms for maximum constraint satisfaction problems","author":"charikar","year":"2007","journal-title":"SODA"},{"key":"ref101","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132519"},{"key":"ref26","article-title":"Differentiating maps into L1 and the geometry of BV functions","author":"cheeger","year":"2006","journal-title":"To appear in Ann Math"},{"key":"ref100","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335329"},{"key":"ref25","first-page":"144","article-title":"On the hardness of approximating multi-cut and sparsest-cut","author":"chawla","year":"2005","journal-title":"Proc 20th IEEE Conference on Computational Complexity"},{"journal-title":"On a protocol possibly useful for MIN-2SAT Manuscript","year":"2001","author":"hastad","key":"ref50"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959936"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1993.253464"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237990"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1030.0086"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365710"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21923"},{"journal-title":"New maximally stable gaussian partitions with discrete applications arXiv 0903 3362v3","year":"2010","author":"isaksson","key":"ref53"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250852"},{"key":"ref40","first-page":"117","article-title":"On systems of linear equations with two variables per equation","author":"feige","year":"2004","journal-title":"APPROX-RANDOM"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.40"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132548"},{"journal-title":"A 2 npoly(E)-time algorithm for (1 -?)-satisfiable Unique games Manuscript","year":"2010","author":"arora","key":"ref5"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060673"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374380"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109569"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050065"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.51"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892074"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009809"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380837"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614315"},{"key":"ref43","first-page":"422","article-title":"0.878 approximation algorithms for MAX-CUT and MAX-2SAT","author":"goemans","year":"1994","journal-title":"Proc 26th ACM Symposium on Theory of Computing"},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.50"},{"key":"ref72","first-page":"64","article-title":"The UGC hardness threshold of the lpGrothendieck problem","author":"kindler","year":"2008","journal-title":"SODA"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.74"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.37"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.47"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.20"},{"key":"ref75","article-title":"Improved lower bounds for embeddings into 11","author":"krauthgamer","year":"2006","journal-title":"Proc ACM-SIAM symposium on Discrete algorithms"},{"key":"ref78","first-page":"67","article-title":"Improved rounding techniques for the max 2-sat and max di-cut problems","author":"lewin","year":"2002","journal-title":"IPCO"},{"key":"ref79","first-page":"573","article-title":"Finite metric spaces-combinatorics, geometry and algorithms","volume":"3","author":"linial","year":"2002","journal-title":"Proc the International Congress of Mathematicians"},{"key":"ref60","article-title":"On the power of unique 2-prover 1-round games","author":"khot","year":"2002","journal-title":"Proc 34th ACM Symposium on Theory of Computing"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1142\/9789814324359_0163"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1145\/1067309.1067318"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.49"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.33"},{"key":"ref65","article-title":"Sharp kernel clustering algorithms and their associated Grothendieck inequalities","author":"khot","year":"2010","journal-title":"SODA"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.67"},{"journal-title":"Approximate Lasserre integrality gap for Unique games Manuscript","year":"2010","author":"khot","key":"ref67"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214437"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1142\/S1793525309000096"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.5"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060675"},{"key":"ref95","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374378"},{"key":"ref94","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"ref93","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.58"},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.73"},{"key":"ref105","first-page":"201","article-title":"Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint","author":"zwick","year":"1998","journal-title":"SODA"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.74"},{"key":"ref104","article-title":"Inapproximability of combinatorial optimization problems","volume":"2","author":"trevisan","year":"2005","journal-title":"Optimisation Combinatiore"},{"key":"ref90","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"ref103","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.22"},{"key":"ref102","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"ref98","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(79)90055-1"},{"key":"ref99","doi-asserted-by":"publisher","DOI":"10.1007\/BF00537230"},{"key":"ref96","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"ref97","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.49"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007355"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250818"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0272-6"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78773-0_58"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.23"},{"journal-title":"Inapproximability of hypergraph vertex cover and applications to scheduling problems Manuscript","year":"2010","author":"bansal","key":"ref16"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.44"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.55"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374379"},{"key":"ref18","article-title":"Free bits, PCPs and non-approximability","author":"bellare","year":"1995","journal-title":"Electronic Colloquium on Computational Complexity Technical Report TR95–024"},{"journal-title":"On the banach space valued Azuma inequality and small set isoperimetry in Alon-Roichman graphs Unpublished manuscript","year":"2004","author":"naor","key":"ref84"},{"key":"ref19","first-page":"1","volume":"70","author":"borell","year":"1985","journal-title":"Geometric bounds on the Ornstein-Uhlenbeck velocity process"},{"key":"ref83","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/SFCS.2005.53","article-title":"Noise stability of functions with low influences: invariance and optimality","author":"mossel","year":"2005","journal-title":"Proc 46th IEEE Symposium on Foundations of Computer Science"},{"key":"ref80","article-title":"How to play Unique games on expanders","author":"makarychev","year":"2009","journal-title":"CoRR abs\/0903 0367"},{"key":"ref89","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"ref85","doi-asserted-by":"publisher","DOI":"10.1142\/9789814324359_0110"},{"key":"ref86","article-title":"Approximating the maximum acyclic subgraph","author":"newman","year":"2000","journal-title":"Master thesis"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374425"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536482"}],"event":{"name":"2010 IEEE 25th Annual Conference on Computational Complexity (CCC)","start":{"date-parts":[[2010,6,9]]},"location":"Cambridge, MA, USA","end":{"date-parts":[[2010,6,12]]}},"container-title":["2010 IEEE 25th Annual Conference on Computational Complexity"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/5497049\/5497861\/05497893.pdf?arnumber=5497893","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T10:42:50Z","timestamp":1497868970000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/5497893\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":105,"URL":"https:\/\/doi.org\/10.1109\/ccc.2010.19","relation":{},"subject":[],"published":{"date-parts":[[2010,6]]}}}