zbMATH — the first resource for mathematics

Lower bounds on the size of semidefinite programming relaxations. (English) Zbl 1321.90099
Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 567-576 (2015).

90C22 Semidefinite programming
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI arXiv
[1] I. Abraham, and C. Gavoille. On Approximate Distance Labels and Routing Schemes with A.ne Stretch. DISC, 404 415, 2011. · Zbl 1350.68020
[2] I. Alth\" ofer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81 100, 1993. · Zbl 0762.05039
[3] B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Near-linear time construction of sparse neighborhood covers. In SIAM J. Comput., Vol. 28, No. 1, 263-. U277, 1998. · Zbl 0943.05079
[4] S. Baswana, A. Gaur, S. Sen and J. Upadhyay. Distance oracles for unwieghted graphs: Breaking the quadratic barrier with constant additive error. In ICALP, pages 609-. U621, 2008. · Zbl 1153.68405
[5] S. Baswana and T. Kavitha. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In Proc. IEEE Symp. on Foundations of Computer Science (FOCS), 591 602, 2006.
[6] S.Chechik. Approximate Distance Oracles with Constant Query Time. To appear in Proc. 46th ACM Symp. on Theory of Computing (STOC), 2014. · Zbl 1315.68112
[7] E. Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput., 28:210 .U-236, 1998. · Zbl 0915.68077
[8] P. Erd.os. Extremal problems in graph theory. In Theory of graphs and its applications, pages 29 . U-36, 1964.
[9] J. Matou.sek. On the distortion required for embeding .nite metric spaces into normed spaces. In Israel Journal of Math 93, 333 344, 1996.
[10] M. Mendel, and A. Naor. Ramsey partitions and proximity data structures In Proc. 47th IEEE Symp. on Foundations of Computer Science (FOCS), 109 118, 2006. · Zbl 1122.68043
[11] M. Mendel, and A. Naor. Ramsey partitions and proximity data structures. In Journal of the European Mathematical Society, 9:2, 253 275, 2007. · Zbl 1122.68043
[12] M. Mendel and C. Schwob. Fast C-K-R Partitions of Sparse Graphs. In Journal of Theoretical Comp. Sci., (2), 1 . U-18, 2009. · Zbl 1286.68373
[13] A. Naor, and T. Tao. Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem. In Israel Journal of Mathematics, 192 ,489 . U-504, 2012. · Zbl 1266.46017
[14] M. P.atra\cscu and L. Roditty. Distance oracles beyond the thorup-zwick bound. In FOCS, pages 815-. U823, 2010.
[15] M. P.atra\cscu, L. Roditty and M. Thorup. A New In.nity of Distance Oracles for Sparse Graphs In FOCS, pages 738 747, 2012.
[16] L. Roditty, M. Thorup, and U. Zwick. Deterministic constructions of approximate distance oracles and spanners. In Proc. 32nd Int. Colloq. on Automata, Languages & Prog., 261 272, 2005. · Zbl 1082.68087
[17] C. Sommer. Shortest-Path Queries in Static Networks In ACM Computing Surveys,46(4), 2014. · Zbl 1305.68137
[18] M. Thorup and U. Zwick. Approximate distance oracles. In J. ACM, 52, 1 24, 2005. · Zbl 1175.68303
[19] C. Wul.-Nilsen. Approximate Distance Oracles with Improved Preprocessing Time. In Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA),202-. U208, 2012.
[20] C. Wul.-Nilsen. Approximate Distance Oracles with Improved Query Time. In Proc. 24th ACM-SIAM Symp. on Discrete Algorithms (SODA), 539 549, 2013.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.