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]. [ .html ]
[3] Noga Alon and Yuval Roichman: Random Cayley graphs and expanders. Random Structures & Algorithms, 5, 1994. [ .html ]
[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]. [ .html ]
[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. [doi:10.1103/PhysRev.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]. [ .html ]
[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. [ http ]
[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. [ .ps | .pdf ]
[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. [ .html ]
[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. [ http ]
[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. [ .ps | .pdf ]
[31] C. J. Thompson: Inequality with applications in statistical mechanics. Journal of Mathematical Physics, 6(11):1812-1823, 1965. [doi:10.1063/1.1704727]. [ DOI | http ]
[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.

This file has been generated by bibtex2html 1.85.