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.