Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
by Avi Wigderson and David Xiao
Theory of Computing, Volume 4(3), pp. 53-76, 2008
Bibliography with links to cited articles
[1] Rudolf Ahlswede and Andreas Winter: Strong converse for identification via quantum channels. IEEE Transactions on Information Theory, 48(3):569–579, 2002. [IEEE:10.1109/18.985947].
[2] Noga Alon, Uriel Feige, Avi Wigderson, and David Zuckerman: Derandomized graph products. Computational Complexity, 5(1):60–75, 1995. [Springer:r591795p150lj86q].
[3] Noga Alon and Yuval Roichman: Random Cayley graphs and expanders. Random Structures & Algorithms, 5, 1994.
[4] Sanjeev Arora and Satyen Kale: A combinatorial, primal-dual approach to semidefinite programs. In Proc. 39th STOC, pp. 227–236, New York, NY, USA, 2007. ACM. [STOC:10.1145/1250790.1250823].
[5] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, May 1998.
[6] Sanjeev Arora, Satish Rao, and Umesh Vazirani: Expander flows, geometric embeddings, and graph partitionings. In Proc. 36th STOC, pp. 222–231. ACM Press, 2004. [STOC:10.1145/1007352.1007355].
[7] József Beck and Joel Spencer: Integral approximation sequences. Mathematical Programming, 30(1):88–98, 1984. [Springer:d77488n21q0222p0].
[8] Yonatan Bilu and Shlomo Hoory: On codes from hypergraphs. European Journal of Combinatorics, 25(3):339–354, 2004. [Elsevier:10.1016/j.ejc.2003.10.002].
[9] Aviad Cohen and Avi Wigderson: Dispersers, deterministic amplification, and weak random sources. In Proc. 30th FOCS, pp. 14–19. IEEE Computer Society Press, 1989.
[10] Uriel Feige: A threshold of lnn for approximating set cover. J. ACM, 45(4):634–652, 1998. [JACM:10.1145/285055.285059].
[11] M. X. Goemans and D. P. Williams: Improved approximation algorithms for max-cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995. [JACM:10.1145/227683.227684].
[12] S. Golden: Lower bounds for the Helmholtz function. Physical Review, 137B(4):B1127–1128, 1965. [10.1103PhysRev.137.B1127].
[13] Oded Goldreich: A sample of samplers - a computational perspective on sampling (survey). Electronic Colloquium on Computational Complexity (ECCC), 4(020), 1997. [ECCC:TR97-020].
[14] Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, and David Zuckerman: Security preserving amplification of hardness. In Proc. 31st FOCS, pp. 318–326. IEEE Computer Society Press, 1990.
[15] Oded Goldreich and Madhu Sudan: Locally testable codes and PCPs of almost-linear length. In Proc. 43rd FOCS, pp. 13–22, Los Alamitos-Washington-Brussels-Tokyo, 2002. IEEE Computer Society, IEEE Computer Society Press. [FOCS:10.1109/SFCS.2002.1181878].
[16] G. H. Golub and C. F. Van Loan: Matrix Computations. Johns Hopkins University Press, 1989.
[17] Shlomo Hoory, Nathan Linial, and Avi Wigderson: Expander graphs and their applications. Bull. Amer. Math. Soc., 43:439–561, 2006.
[18] Russell Impagliazzo and David Zuckerman: How to recycle random bits. In Proc. 30th FOCS, pp. 248–253. IEEE, 1989.
[19] Stavros G. Kolliopoulos and Neal E. Young: Approximation algorithms for covering/packing integer programs. J. Computer and System Sciences, 71(4):495–505, 2005. [JCSS:10.1016/j.jcss.2005.05.002].
[20] Zeph Landau and Alexander Russell: Random Cayley graphs are expanders: a simplified proof of the Alon-Roichman theorem. The Electronic Journal of Combinatorics, 11(1), 2004.
[21] Po-Shen Loh and Leonard J. Schulman: Improved expansion of random Cayley graphs. Discrete Mathematics and Theoretical Computer Science, 6(2):523–528, 2004.
[22] Joseph Naor and Moni Naor: Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing, 22(4):838–856, August 1993. [SICOMP:10.1137/0222053].
[23] Noam Nisan and Amnon Ta-Shma: Extracting randomness: A survey and new constructions. J. Computer and System Sciences, 58(1):148–173, 1999. [JCSS:10.1006/jcss.1997.1546].
[24] Prabhakar Raghavan: Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Computer and System Sciences, 37(2):130–143, 1988. [JCSS:10.1016/0022-0000(88)90003-7].
[25] Ronen Shaltiel: Recent developments in extractors. Bulletin of the European Association for Theoretical Computer Science, 2002.
[26] N.Z. Shor: Cut-off method with space extension in convex programming problems. Cybernetics and Systems Analysis, 13:94–96, 1977. [Springer:w88055332t2p4215].
[27] N.Z. Shor: Quadratic optimization problems. Soviet Journal of Circuits and Systems Sciences, 25:1–11, 1987.
[28] Amir Shpilka and Avi Wigderson: Derandomizing homomorphism testing in general groups. In Proc. 36th STOC, pp. 427–435. ACM Press, 2004. [STOC:10.1145/1007352.1007421].
[29] Joel Spencer: Ten Lectures on the Probabilistic Method, 2nd Edition. SIAM, 1994.
[30] Daniel Spielman: Computationally Efficient Error-Correcting Codes and Holographic Proofs. PhD thesis, M.I.T., 1995.
[31] C. J. Thompson: Inequality with applications in statistical mechanics. Journal of Mathematical Physics, 6(11):1812–1823, 1965. [doi:10.1063/1.1704727].
[32] L. Vandenberghe and S. Boyd: Semidefinite programming. SIAM Review, 38:49–95, March 1996. [SIREV:10.1137/1038003].
[33] Avi Wigderson and David Xiao: A randomness-efficient sampler for matrix-valued functions and applications. In Proc. 46th FOCS, pp. 397–406, 2005. [FOCS:10.1109/SFCS.2005.8].
[34] Avi Wigderson and David Xiao: A randomness-efficient sampler for matrix-valued functions and applications. ECCC Report TR05-107, 2005. [ECCC:TR05-107].
[35] D. B. Yudin and A. S. Nemirovski: Informational complexity and efficient methos for solving complex extremal problems. Matekon, 13:25–45, 1977.