On Beating the Hybrid Argument
by Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola
Theory of Computing, Volume 9(26), pp. 809-843, 2013
Bibliography with links to cited articles
[1] Scott Aaronson: A counterexample to the Generalized Linial-Nisan Conjecture. Electron. Colloq. on Comput. Complexity (ECCC), 17:109, 2010. ECCC.
[2] Scott Aaronson: BQP and the polynomial hierarchy. In Proc. 42nd STOC, pp. 141–150. ACM Press, 2010. See also in ECCC. [doi:10.1145/1806689.1806711]
[3] Miklós Ajtai: Σ11-formulae on finite structures. Ann. Pure Appl. Logic, 24(1):1–48, 1983. [doi:10.1016/0168-0072(83)90038-6]
[4] Miklós Ajtai and Michael Ben-Or: A theorem on probabilistic constant depth computations. In Proc. 16th STOC, pp. 471–474. ACM Press, 1984. [doi:10.1145/800057.808715]
[5] Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz: Cryptography in NC0. SIAM J. Comput., 36(4):845–888, 2006. Preliminary version in FOCS’04. [doi:10.1137/S0097539705446950]
[6] James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich: The expressive power of voting polynomials. Combinatorica, 14(2):135–148, 1994. Preliminary version in STOC’91. [doi:10.1007/BF01215346]
[7] Boaz Barak, Ronen Shaltiel, and Avi Wigderson: Computational analogues of entropy. In Proc. 7th Internat. Workshop on Randomization and Computation (RANDOM’03), pp. 200–215. Springer, 2003. [doi:10.1007/978-3-540-45198-3_18]
[8] Richard Beigel: When do extra majority gates help? Polylog(N) majority gates are equivalent to one. Comput. Complexity, 4(4):314–324, 1994. Preliminary version in STOC’92. [doi:10.1007/BF01263420]
[9] Ethan Bernstein and Umesh V. Vazirani: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. Preliminary version in STOC’93. [doi:10.1137/S0097539796300921]
[10] Manuel Blum and Silvio Micali: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput., 13(4):850–864, 1984. Preliminary version in FOCS’82. [doi:10.1137/0213053]
[11] Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff: Pseudorandom generators for regular branching programs. In Proc. 51st FOCS, pp. 40–47. IEEE Comp. Soc. Press, 2010. See also at ECCC. [doi:10.1109/FOCS.2010.11]
[12] Joshua Brody and Elad Verbin: The coin problem, and pseudorandomness for branching programs. In Proc. 51st FOCS, pp. 30–39. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.10]
[13] Joan Feigenbaum and Lance Fortnow: Random-self-reducibility of complete sets. SIAM J. Comput., 22(5):994–1005, 1993. Preliminary version in SCT’91. [doi:10.1137/0222061]
[14] Yuval Filmus: Smolensky’s polynomial method, 2010. See author’s home page.
[15] Oded Goldreich: Foundations of Cryptography, Volume 1: Basic Tools. Cambridge Univ. Press, 2001. See also author’s home page.
[16] Oded Goldreich and Leonid A. Levin: A hard-core predicate for all one-way functions. In Proc. 21st STOC, pp. 25–32. ACM Press, 1989. [doi:10.1145/73007.73010]
[17] Oded Goldreich and Avi Wigderson: Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Structures & Algorithms, 11(4):315–343, 1997. Preliminary version in STOC’94. See also at ECCC. [doi:10.1002/(SICI)1098-2418(199712)11:4¡315::AID-RSA3¿3.0.CO;2-1]
[18] Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum: Verifying and decoding in constant depth. In Proc. 39th STOC, pp. 440–449. ACM Press, 2007. [doi:10.1145/1250790.1250855]
[19] Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum: A (de)constructive approach to program checking. In Proc. 40th STOC, pp. 143–152. ACM Press, 2008. See also at ECCC. [doi:10.1145/1374376.1374399]
[20] Shafi Goldwasser and Silvio Micali: Probabilistic encryption. J. Comput. System Sci., 28(2):270–299, 1984. [doi:10.1016/0022-0000(84)90070-9]
[21] Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan: Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes. J. ACM, 56(4), 2009. Preliminary version in CCC’07. [doi:10.1145/1538902.1538904]
[22] Johan Håstad: Computational limitations of small-depth circuits. MIT Press, 1987. [ACM:SERIES9056.27031]
[23] Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby: A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, 1999. Preliminary versions in STOC’89 and STOC’90. [doi:10.1137/S0097539793244708]
[24] Russell Impagliazzo: Hard-core distributions for somewhat hard problems. In Proc. 36th FOCS, pp. 538–545. IEEE Comp. Soc. Press, 1995. [doi:10.1109/SFCS.1995.492584]
[25] Russell Impagliazzo, Noam Nisan, and Avi Wigderson: Pseudorandomness for network algorithms. In Proc. 26th STOC, pp. 356–364. ACM Press, 1994. [doi:10.1145/195058.195190]
[26] Yuval Ishai and Eyal Kushilevitz: Randomizing polynomials: A new representation with applications to round-efficient secure computation. In Proc. 41st FOCS, pp. 294–304. IEEE Comp. Soc. Press, 2000. [doi:10.1109/SFCS.2000.892118]
[27] Yuval Ishai and Eyal Kushilevitz: Perfect constant-round secure computation via perfect randomizing polynomials. In Proc. 29th Internat. Colloq. on Automata, Languages and Programming (ICALP’02), pp. 244–256. Springer, 2002. [doi:10.1007/3-540-45465-9_22]
[28] Alexei Kitaev, Alexander Shen, and Mikhail Vyalyi: Classical and Quantum Computation. Amer. Math. Soc., 2002. [ACM:863284]
[29] Michal Koucký, Prajakta Nimbhorkar, and Pavel Pudlák: Pseudorandom generators for group products: extended abstract. In Proc. 43rd STOC, pp. 263–272. ACM Press, 2011. [doi:10.1145/1993636.1993672]
[30] Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu: Complexity of hard-core set proofs. Comput. Complexity, 20(1):145–171, 2011. Preliminary version in ICALP’07. [doi:10.1007/s00037-011-0003-7]
[31] Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991. [doi:10.1007/BF01375474]
[32] Noam Nisan: Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. Preliminary version in STOC’90. [doi:10.1007/BF01305237]
[33] Noam Nisan and Avi Wigderson: Hardness vs randomness. J. Comput. System Sci., 49(2):149–167, 1994. Preliminary version in FOCS’88. [doi:10.1016/S0022-0000(05)80043-1]
[34] Noam Nisan and David Zuckerman: Randomness is linear in space. J. Comput. System Sci., 52(1):43–52, 1996. Preliminary version in STOC’93. [doi:10.1006/jcss.1996.0004]
[35] Ran Raz and Omer Reingold: On recycling the randomness of states in space bounded computation. In Proc. 31st STOC, pp. 159–168. ACM Press, 1999. [doi:10.1145/301250.301294]
[36] Alexander Razborov: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mat. Zametki, 41(4):598–607, 1987. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987. [doi:10.1007/BF01137685]
[37] Ronen Shaltiel and Emanuele Viola: Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122–3154, 2010. Preliminary version in STOC’08. See also at ECCC. [doi:10.1137/080735096]
[38] Roman Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. 19th STOC, pp. 77–82. ACM Press, 1987. [doi:10.1145/28395.28404]
[39] Roman Smolensky: On representations by low-degree polynomials. In Proc. 34th FOCS, pp. 130–138. IEEE Comp. Soc. Press, 1993. [doi:10.1109/SFCS.1993.366874]
[40] Madhu Sudan, Luca Trevisan, and Salil P. Vadhan: Pseudorandom generators without the XOR lemma. J. Comput. System Sci., 62(2):236–266, 2001. Preliminary version in STOC’99. See also at ECCC. [doi:10.1006/jcss.2000.1730]
[41] Emanuele Viola: Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM J. Comput., 36(5):1387–1403, 2007. Preliminary version in CCC’05. See also at ECCC. [doi:10.1137/050640941]
[42] Emanuele Viola: On approximate majority and probabilistic time. Comput. Complexity, 18(3):337–375, 2009. Preliminary version in CCC’07. [doi:10.1007/s00037-009-0267-3]
[43] Emanuele Viola: On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1–72, 2009. [doi:10.1561/0400000033]
[44] Emanuele Viola: The complexity of distributions. SIAM J. Comput., 41(1):191–218, 2012. Preliminary version in FOCS’10. [doi:10.1137/100814998]
[45] John Watrous: Succinct quantum proofs for properties of finite groups. In Proc. 41st FOCS, pp. 537–546. IEEE Comp. Soc. Press, 2000. [doi:10.1109/SFCS.2000.892141]
[46] Ryan Williams: Non-uniform ACC circuit lower bounds. In Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 115–125. IEEE Comp. Soc. Press, 2011. [doi:10.1109/CCC.2011.36]
[47] Ryan Williams: Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput., 42(3):1218–1244, 2013. Preliminary version in STOC’10. [doi:10.1137/10080703X]
[48] Andrew Chi-Chih Yao: Theory and applications of trapdoor functions (extended abstract). In Proc. 23rd FOCS, pp. 80–91. IEEE Comp. Soc. Press, 1982. [doi:10.1109/SFCS.1982.45]
[49] David Zuckerman: Randomness-optimal oblivious sampling. Random Structures & Algorithms, 11(4):345–367, 1997. Preliminary version in STOC’96. [doi:10.1002/(SICI)1098-2418(199712)11:4¡345::AID-RSA4¿3.0.CO;2-Z]