{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:45:01Z","timestamp":1725795901594},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_83","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"1003-1014","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs"],"prefix":"10.1007","author":[{"given":"Madhur","family":"Tulsiani","sequence":"first","affiliation":[]},{"given":"John","family":"Wright","sequence":"additional","affiliation":[]},{"given":"Yuan","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"83_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for Unique Games and related problems. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 563\u2013572 (2010)","DOI":"10.1109\/FOCS.2010.59"},{"key":"83_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Khot, S.A., Kolla, A., Steurer, D., Tulsiani, M., Vishnoi, N.K.: Unique Games on expanding constraint graphs are easy. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 21\u201328 (2008)","DOI":"10.1145\/1374376.1374380"},{"key":"83_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B., Hardt, M., Haviv, I., Rao, A., Regev, O., Steurer, D.: Rounding parallel repetitions of Unique Games. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 374\u2013383 (2008)","DOI":"10.1109\/FOCS.2008.55"},{"key":"83_CR4","doi-asserted-by":"crossref","unstructured":"Barak, B., Rao, A., Raz, R., Rosen, R., Shaltiel, R.: Strong parallel repetition theorem for free projection games. In: Proceedings of the 13th Annual International Workshop on Randomization and Computation, pp. 352\u2013365 (2009)","DOI":"10.1007\/978-3-642-03685-9_27"},{"key":"83_CR5","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"83_CR6","doi-asserted-by":"crossref","unstructured":"Feige, U., Kindler, G., O\u2019Donnell, R.: Understanding parallel repetition requires understanding foams. In: Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, pp. 179\u2013192 (2007)","DOI":"10.1109\/CCC.2007.39"},{"key":"83_CR7","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 482\u2013491 (2011)","DOI":"10.1109\/FOCS.2011.36"},{"key":"83_CR8","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Trevisan, L.: A new regularity lemma and faster approximation algorithms for low threshold rank graphs. In: Proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 303\u2013316 (2013)","DOI":"10.1007\/978-3-642-40328-6_22"},{"key":"83_CR9","doi-asserted-by":"crossref","unstructured":"Kwok, T.C., Lau, L.C., Lee, Y.T., Gharan, S.O., Trevisan, L.: Improved Cheeger\u2019s inequality: analysis of spectral partitioning algorithms through higher order spectral gap. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pp. 11\u201320 (2013)","DOI":"10.1145\/2488608.2488611"},{"issue":"2","key":"83_CR10","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s00037-011-0011-7","volume":"20","author":"A. Kolla","year":"2011","unstructured":"Kolla, A.: Spectral algorithms for Unique Games. Computational Complexity\u00a020(2), 177\u2013206 (2011)","journal-title":"Computational Complexity"},{"key":"83_CR11","unstructured":"Kolla, A., Tulsiani, M.: Playing random and expanding unique games(2007) (manuscript )"},{"key":"83_CR12","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Gharan, S.O., Trevisan, L.: Multi-way spectral partitioning and higher-order Cheeger inequalities. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pp. 1117\u20131130 (2012)","DOI":"10.1145\/2213977.2214078"},{"key":"83_CR13","doi-asserted-by":"crossref","unstructured":"Louis, A., Raghavendra, P., Tetali, P., Vempala, S.: Many sparse cuts via higher eigenvalues. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pp. 1131\u20131140 (2012)","DOI":"10.1145\/2213977.2214079"},{"issue":"6","key":"83_CR14","doi-asserted-by":"publisher","first-page":"1871","DOI":"10.1137\/080734042","volume":"40","author":"A. Rao","year":"2011","unstructured":"Rao, A.: Parallel repetition in projection games and a concentration bound. SIAM Journal on Computing\u00a040(6), 1871\u20131891 (2011)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"83_CR15","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM Journal on Computing\u00a027(3), 763\u2013803 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"83_CR16","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1137\/090747270","volume":"40","author":"R. Raz","year":"2011","unstructured":"Raz, R.: A counterexample to strong parallel repetition. SIAM Journal on Computing\u00a040(3), 771\u2013777 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"83_CR17","doi-asserted-by":"crossref","unstructured":"Raz, R., Rosen, R.: A strong parallel repetition theorem for projection games on expanders. In: Proceedings of the 27th Annual IEEE Conference on Computational Complexity, pp. 247\u2013257 (2012)","DOI":"10.1109\/CCC.2012.11"},{"key":"83_CR18","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions between expansion problems. In: Proceedings of the 27th Annual IEEE Conference on Computational Complexity, pp. 64\u201373 (2012)","DOI":"10.1109\/CCC.2012.43"},{"key":"83_CR19","unstructured":"Safra, S., Schwartz, O.: On parallel-repetition, unique-game and max-cut (2007) (manuscript)"},{"key":"83_CR20","unstructured":"Steurer, D.: Talk at the Simons Institute for the Theory of Computing (2013)"},{"key":"83_CR21","unstructured":"Trevisan, L.: Lecture 6 from CS359G: graph partitioning and expanders(2011) \n                    \n                      http:\/\/theory.stanford.edu\/~trevisan\/cs359g\/lecture06.pdf"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_83","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:19:57Z","timestamp":1558909197000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_83"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_83","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}