COMPLEXITY THEORY & ALGORITHMS RESEARCH

 
Gat, E. and Goldwasser, S. “Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications.” Electronic Colloquium on Computational Complexity (ECCC), 18: 136, 2011.
 
Goldreich, O., Goldwasser, S., and Ron, D. “On the Possibilities and Limitations of Pseudodeterministic Algorithms.” To appear in ITCS 2013: Innovations in Theoretical Computer Science, Berkeley, CA, January 2013.
 
Goldreich, O., Goldwasser, S., and Nussboim, A. “On the Implementation of Huge Random Objects.” SIAM J. on Computing, 39(7):2761-2822, 2010.
 
Akavia, A., Goldreich, G., Goldwasser, S., and Moshkovitz, D. “Erratum for: on basing one-way functions on NP-hardness.” Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), pages 795-796, Cambridge, MA, 2010.
 
Akavia, A., Goldreich, O., Goldwasser, S., and Moshkovitz, D. “On basing one-way functions on NP-hardness.” Proceedings of the 38th ACM Symposium on Theory of Computing (STOC 2006), Seattle, Washington, pages 701-710, May 2006.
 
Akavia, A., Goldwasser, S., and Safra, S. “Proving Hard-Core Predicates Using List Decoding.” Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), pages 146-157, Cambridge, MA, October 2003.
 
Golderich, O., Goldwasser, S., Lehman, E., Ron, D., and Samorodnitsky, A. “Testing Monontonicity.” Combinatorica, 20(3):301–337, 2000.
 
Goldwasser, S. and Kilian, J. “Primality Testing based on Elliptic Curves.” J. of the ACM, 46(4):450-472, July 1999.
 
Goldreich, O., Goldwasser, S., Lehman, E., and Ron, D. “Testing Monotonicity.” 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), Palo Alto, CA, October 1998.
 
Golderich, O., Goldwasser, S., and Ron, D. “Property Testing and its Connection to Learning and Approximation.” J. of the ACM, 45(4):653-750, July 1998.
 
Goldreich, O., Goldwasser S., and Linial, N. “Fault Tolerant Computation in the Full Information Model.” SIAM J. of Computing, 27(2):506-544, April 1998.
 
Feige, U., Goldwasser, S., Lovasz, L., Safra, S., and Szegedi. M. “Interactive Proofs and the Hardness of Approximating Cliques. J. of the ACM, 43(2):268-292, March 1996.
 
Goldreich O., Goldwasser S., and Ron D. “Property Testing and its Connections to Learning and Approximation.” Proceedings of FOCS96, Burlington, VT, October 1995. Final version Accepted to the Journal of the ACM.
 
Bellare, M., and Goldwasser, S. “The Complexity of Decision versus Search.” SIAM Journal of Computing, 23(1):97-119, February 1994.
 
Bellare M., Goldreich, O., and Goldwasser S. “Randmoness in Interactive Proofs.” Computational Complexity, 4(4):319-354, 1993.
 
Bellare, M., Goldwasser S., Carsten L., and Russel A.“Efficient Probabilistically Checkable Proofs with Applications to Approximation.” Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC93), San Diego, CA, May 1993.
 
Bellare, M., Beigel R., Feigenbaum J., and Goldwasser S. “The Complexity of Decision versus Search.” 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991), Puerto Rico, October 1991.
 
Feige, U., Goldwasser S., Lovasz L., Szegedi M., and Safra S. “Approximating the Clique is Almost NP-Complete.” Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991), Puerto Rico, October 1991.
 
Aiello, B., Goldwasser, S., and Hastad, J. “On the Power of Interaction.” Combinatorica 10(1):3-25, 1990.
 
Goldwasser, S. “Interactive Proofs and Applications.” Proceedings of the International Congress of Mathematicians, volume 2, Japan, August 1990.
 
Bellare, M., Goldreich, O., and Goldwasser S. “Saving Randomness in Interactive Proofs.” Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS 1990), pages 563-572, St. Louis, Missouri, May 1990.
 
Goldwasser, S., and M. Sipser. “Private Coins versus Public Coins in Interactive Proof Systems.” Randomness and Computation, vol. 5 of Advances in Computing Research, JAI Press, 1989.
 
Goldwasser, S. “Interactive Proof Systems.” Computational Complexity Theory, J. Hartmanis (Ed.), Proceedings of Symposia in Applied Mathematics, vol. 38, pages 108-128, 1989.
 
Ben-Or, M., Goldwasser S., Kilian J., and Wigderson A. “Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions.” Proceedings of 20th Annual ACM Symposium on Theory of Computing (STOC 1988), Chicago, Illinois, pages 113-122, May 1988.
 
Goldwasser, S., Micali, S., and Rackoff, C. “The Knowledge Complexity of Interactive Proof Systems.” Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC 1985), pages 291-304, Providence, RI, May 1985.
 
Aiello, B., Goldwasser, S., and Hastad, J. “On the Power of Interaction.” Proceedings of the 27th Annual Symposium on the Foundations of Computer Science (FOCS 1986), pages 368-379, Toronto, Canada, October 1986.
 
Goldwasser, S. and Kilian, J. “Almost All Primes Can be Quickly Certified.” Proceedings of the 18th Annual ACM Symposium on the Theory of Computing (STOC 1986), pages 315-329, Berkeley, CA, May 1986.
 
Goldwasser, S. and Sipser, M. “Private Coins versus Public Coins in Interactive Proof Systems.” Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC 1986), pages 59-86, Berkeley CA, May, 1986.

COMPLEXITY THEORY & ALGORITHMS CONFERENCES

FOCS Conference

ITCS Conference

RANDOM Conference

STOC Conference