Article

Free access

Evaluation may be easier than generation (extended abstract)

Author:

Moni NaorAuthors Info & Claims

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

Pages 74 - 83

https://doi.org/10.1145/237814.237833

Published: 01 July 1996 Publication History

PDF eReader

References

[1]

D. Angluin and M. Kharitonov, When won't membership queries help, Proc. 23rd ACM Annual Symposium on the Theory of Computing, 1991, pp. 444-454.

Digital Library

Google Scholar

[2]

E. Bach, How to generate factored random numbers, SIAM J. Computing 17, 1988, 179-193.

Digital Library

Google Scholar

[3]

Bellare, M. and S. Goldwasser, New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs, Advances in Cryptology- CRYPTO 89, Lecture Notes in Computer Science, vol. 435, Springer- Verlag, 1990, pp. 194-211.

Digital Library

Google Scholar

[4]

M. Bellare and S. Micali, How to Sign Given Any Trapdoor Function, Proc. 20th ACM Annual Symposium on the Theory of Computing, 1988, pp. 32-42.

Digital Library

Google Scholar

[5]

A. Blum, Separating distribution.free and mistakebound learning models over ihe Boolean domain, Proc. 31st IEEE Symposium on Foundations of Computer Science, 1990, pp. 211-218.

Google Scholar

[6]

A. Blum, M. Furst, M. Kearns, and R. Lipton. Crypiographic Primitives Based on Hard Learning Problems. Advances in Cryptology CRYPTO 93, Lecture Notes in Computer Science 773, Springer-Verlag, 1994, pp. 278-291.

Digital Library

Google Scholar

[7]

M. Blum, A. De Santis, S. Micali and, G. Persiano, Non-Interactive Zero-Knowledge, SIAM J. Computing, 1991, pp. 1084-1118.

Digital Library

Google Scholar

[8]

T. M. Cover and j. A. Thomas, Elements of Information Theory, Wiley, 1991.

Digital Library

Google Scholar

[9]

C. Dwork and M. Naor, An Efficient Existentially Unforgeable Signature Scheme and its Applications, Advances in Cryptology- CRYPTO '94, Springer Verlag, 1994, pp. 234-246.

Digital Library

Google Scholar

[10]

S. Even, O. Goldreich, and S. Micali, Online/Off-line Digital Signatures, Advances in Cryptology- CRYPTO '89, Lecture Notes in Computer Science, vol. 435, Springer-Verlag, 1990, pp. 263-275.

Digital Library

Google Scholar

[11]

U. Feige, D. Lapidot and A. Shamir, Muliiple Non-interactive Zero-Knowledge Proofs Based on a Single Random Siring, Proc. of 31st Symposium on Foundations of Computer Science, 1990, pp. 308-317.

Digital Library

Google Scholar

[12]

Y. Freund, An improved boosting algorithm and its implication on learning complexity, Proc. 5th ACM Workshop on Computational Learning Theory, 1992, pp. 391-398.

Digital Library

Google Scholar

[13]

Goldreich, O., Foundations of Cryptography (Fragments of a Book) 1995. Available in the Electronic Colloquium on Computational Complexity: http://www.eccc.unitrier, de/eccc/info/ECCC-Books/ecccbooks.html.

Google Scholar

[14]

O. Goldreich, Two remarks concerning the Goldwasser-Micali-Rivest signature scheme, Advances in Cryptology- CRYPTO' 86, Lecture Notes in Computer Science, vol. 263, Springer- Verlag, 1987, pp. 104-110.

Digital Library

Google Scholar

[15]

O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions, J. of the ACM. 33 (1986) 792-807.

Digital Library

Google Scholar

[16]

S. Goldwasser, S. Micali and R. Rivest A secure digital signature scheme, SIAM J. on Computing 17, 1988, pp. 281-308.

Digital Library

Google Scholar

[17]

M. Kearns and L. Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, J. of the ACM. 41(1) (Jan, 1994) 67-95.

Digital Library

Google Scholar

[18]

M. Kearns, Yishai Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire and Linda Sellie, On lhe learnability of discrele distributions, Proc. 26th ACM Annual Symposium on the Theory of Computing, 1994, pp. 273-282.

Digital Library

Google Scholar

[19]

M. Kharitonov, Cryptographic hardness of distribution-specific learning, Proc. 25th ACM Symposium on Theory of Computing, (1993) 372-381.

Digital Library

Google Scholar

[20]

J. Kilian, On the complexity of bounded- ~nieraction and non-interaciwe zero-knowledge proofs, Proc. of the 35th IEEE Symposium on the Foundation of Computer Science, 1994.

Digital Library

Google Scholar

[21]

J. Kilian and E. Petrank, An efficient non-interactive zero-knowledge proof system for NP with general assumptions, Electronic Colloquium on Computational Complexity TR95-038. Available: http://www.eccc.uni~ trier, de/eccc/info/ECCC.

Google Scholar

[22]

K. Mulmuley, U. V. Vazirani and V. V. Vazirani Matching is as easy as matrix inversion, Combinatorica 7, 1987, 105-113.

Digital Library

Google Scholar

[23]

M. Naor,Bit commitment using pseudo-randomness, Journal of Cryptology, vol 4, 1991, pp. 151-158.

Digital Library

Google Scholar

[24]

M. Naor and O. Reingold, Synthesizers and their applications Proc. 36th IEEE Symposium on Foundations of Computer Science, 1995, pp. 170- 181.

Digital Library

Google Scholar

[25]

M. Naor and M. Yung, Universal one-Way hash functions and their cryptographzc applications, Proc. 21st ACM Annual Symposium on the Theory of Computing, 1989, pp. 33-43.

Digital Library

Google Scholar

[26]

M. Naor and M. Yung, Public key crypiosystems provably secure against chosen ciphertezt attacks, Proc. 22nd ACM Annual Symposium on the Theory of Computing, 1990, pp. 427-437.

Digital Library

Google Scholar

[27]

Rivest, R.L., A. Shamir, and L.M. Adleman, A method for obtaining digital signature and public key cryptosystems, Comm. A CM 21 (1978) 120- 126.

Digital Library

Google Scholar

[28]

Rivest, R.L., Cryptography and Machine Learninq, Proc. ASIACRYPT'91, Springer Verlag, 1993, pp. 427-439.

Digital Library

Google Scholar

[29]

j. Rompel, One-way Function are Necessary and Sufficient for Signatures, Proc. 22nd ACM Annual Symposium on the Theory of Computing, 1990, pp. 387-394.

Digital Library

Google Scholar

[30]

R. E. Schapire, The strength of weak learnability, Machine Learning 5, 1990, pp. 197-227.

Digital Library

Google Scholar

[31]

A.Sinclair and M. Jerrum, Approximate Countinq, Uniform Generation, and Rapidly Mixing Markov Chains, Information and Computation, 82:93-133, 1989.

Digital Library

Google Scholar

[32]

L. G. Valiant and V. V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science 47, 1986, pp. 85-93.

Digital Library

Google Scholar

Cited By

View all

Ghosal RIshai YKorb AKushilevitz ELou PSahai ASaha BServedio R(2023)Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured HardnessProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585119(1243-1256)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585119
De ADiakonikolas IServedio RIndyk P(2015)Learning from satisfying assignmentsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722162(478-497)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722162
Hardt MRothblum GServedio R(2012)Private data release via learning thresholdsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095131(168-187)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095131
Show More Cited By

Index Terms

Evaluation may be easier than generation (extended abstract)
1. Computing methodologies
  1. Machine learning

Recommendations

Assessing Evaluation Metrics for Neural Test Oracle Generation
Recently, deep learning models have shown promising results in test oracle generation. Neural Oracle Generation (NOG) models are commonly evaluated using static (automatic) metrics which are mainly based on textual similarity of the output, e.g. BLEU, ...
Automatic Test-Case Generation with CoVeriTest (Extended Abstract)
Tests and Proofs
Abstract
Automatic test-case generation approaches are applied to avoid expensive, manual test-case generation. However, it is well-known that test-case generation approaches come with different strengths and weaknesses. Therefore, we need to combine ...
A study of the Prather software metric (abstract)
CSC '90: Proceedings of the 1990 ACM annual conference on Cooperation

Due to the increasing complexity of modern software code, we need ways of effectively measuring the difficulty of programs to detect problem code during development. Program metrics [Conte, 86] are a partial answer to this need. They offer us various ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

July 1996

661 pages

ISBN:0897917855

DOI:10.1145/237814

Chairman:
Gary L. Miller

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC96

Sponsor:

SIGACT

STOC96: ACM Symposium on Theory of Computing

May 22 - 24, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

STOC '96 Paper Acceptance Rate 74 of 201 submissions, 37%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
368
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)13

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ghosal RIshai YKorb AKushilevitz ELou PSahai ASaha BServedio R(2023)Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured HardnessProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585119(1243-1256)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585119
De ADiakonikolas IServedio RIndyk P(2015)Learning from satisfying assignmentsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722162(478-497)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722162
Hardt MRothblum GServedio R(2012)Private data release via learning thresholdsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095131(168-187)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095131
Vadhan SZheng CKarloff HPitassi T(2012)Characterizing pseudoentropy and simplifying pseudorandom generator constructionsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214051(817-836)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214051
Vadhan SZheng C(2012)Characterizing pseudoentropy2012 IEEE Information Theory Workshop10.1109/ITW.2012.6404635(104-108)Online publication date: Sep-2012
https://doi.org/10.1109/ITW.2012.6404635
Ishai YKumarasubramanian AOrlandi CSahai A(2010)On Invertible Sampling and Adaptive SecurityAdvances in Cryptology - ASIACRYPT 201010.1007/978-3-642-17373-8_27(466-482)Online publication date: 2010
https://doi.org/10.1007/978-3-642-17373-8_27
Esponda FForrest SHelman P(2009)Negative representations of informationInternational Journal of Information Security10.1007/s10207-009-0078-18:5(331-345)Online publication date: 21-Sep-2009
https://dl.acm.org/doi/10.1007/s10207-009-0078-1
Hsiao CLu CReyzin L(2007)Conditional Computational Entropy, or Toward Separating Pseudoentropy from CompressibilityProceedings of the 26th annual international conference on Advances in Cryptology10.1007/978-3-540-72540-4_10(169-186)Online publication date: 20-May-2007
https://dl.acm.org/doi/10.1007/978-3-540-72540-4_10
Esponda FAckley EForrest SHelman P(2004)Online Negative DatabasesArtificial Immune Systems10.1007/978-3-540-30220-9_14(175-188)Online publication date: 2004
https://doi.org/10.1007/978-3-540-30220-9_14

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Assessing Evaluation Metrics for Neural Test Oracle Generation

Automatic Test-Case Generation with CoVeriTest (Extended Abstract)

A study of the Prather software metric (abstract)