Journal of the ACM Bibliography

Selected papers that cite this one

• Arne Andersson, Peter Bro Miltersen, Søren Riis, and Mikkel Thorup. Static dictionaries on AC^0 RAMs: Query time Theta(sqrt(log n/log log n)) is necessary and sufficient. In 37th Annual Symposium on Foundations of Computer Science, pages 441-450, Burlington, Vermont, 14-16 October 1996. IEEE.

• Shai Ben-David and Eli Dichterman. Learning with restricted focus of attention. Journal of Computer and System Sciences, 56(3):277-298, April 1998.

• Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 253-262, Montréal, Québec, Canada, 23-25 May 1994.

• Ravi B. Boppana. The average sensitivity of bounded-depth circuits. Information Processing Letters, 63(5):257-261, 15 September 1997.

• Nader H. Bshouty and Christino Tamon. On the Fourier spectrum of monotone functions. Journal of the ACM, 43(4):747-770, July 1996.

• Nader H. Bshouty and Christino Tamon. On the Fourier spectrum of monotone functions (extended abstract). In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 219-228, Las Vegas, Nevada, 29 May-1 June 1995.

• William Evans and Nicholas Pippenger. Lower bounds for noisy Boolean decision trees. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 620-628, Philadelphia, Pennsylvania, 22-24 May 1996.

• Vince Grolmusz. On the power of circuits with gates of low L_1 norms. Theoretical Computer Science, 188(1-2):117-128, 30 November 1997.

• Russell Impagliazzo and Moni Naor. Efficient cryptographic schemes provably as secure as subset sum. Journal of Cryptology, 9(4):199-216, Autumn 1996.

• Jeffrey C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55(3):414-440, December 1997.

• Yishay Mansour. An O(n^{log log n}) learning algorithm for DNF under the uniform distribution. Journal of Computer and System Sciences, 50(3):543-550, June 1995.

• Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions (extended abstract). In 38th Annual Symposium on Foundations of Computer Science, pages 458-467, Miami Beach, Florida, 20-22 October 1997. IEEE.

• S. Venkatesh. Pseudo-average block sensitivity equals average sensitivity. Information Processing Letters, 68(2):93-95, 30 October 1998.

Selected references

• Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792-807, October 1986.

• Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on Boolean functions (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, pages 68-80, White Plains, New York, 24-26 October 1988. IEEE.

• Michael Kearns and Leslie G. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 433-444, Seattle, Washington, 15-17 May 1989.

• Nathan Linial and Noam Nisan. Approximate inclusion-exclusion. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 260-270, Baltimore, Maryland, 14-16 May 1990.

• Yishay Mansour, Noam Nisan, and Prasoon Tiwari. The computational complexity of universal hashing. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 235-243, Baltimore, Maryland, 14-16 May 1990.

• Noam Nisan and Avi Wigderson. Hardness vs. randomness (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, pages 2-11, White Plains, New York, 24-26 October 1988. IEEE.

• Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 77-82, New York City, 25-27 May 1987.

• Andrew C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 80-91, Chicago, Illinois, 3-5 November 1982. IEEE.

• Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles (preliminary version). In 26th Annual Symposium on Foundations of Computer Science, pages 1-10, Portland, Oregon, 21-23 October 1985. IEEE.

Shortcuts: