Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Computational Complexity and Local Algorithms : On the Interplay Between Randomness and Computation / / edited by Oded Goldreich
| Computational Complexity and Local Algorithms : On the Interplay Between Randomness and Computation / / edited by Oded Goldreich |
| Autore | Goldreich Oded |
| Edizione | [1st ed. 2025.] |
| Pubbl/distr/stampa | Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2025 |
| Descrizione fisica | 1 online resource (1007 pages) |
| Disciplina | 005.13 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Algorithms
Computational complexity Mathematics - Data processing Design and Analysis of Algorithms Computational Complexity Computational Mathematics and Numerical Analysis |
| ISBN | 3-031-88946-0 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | -. On defining PPT-search problems -- -. Multi-pseudodeterministic algorithms -- On counting t-cliques Mod 2 -- On coarse and fine approximate counting of t-cliques -- On the complexity of enumerating ordered sets -- On the Cook-Mertz Tree Evaluation procedure -- Solving Tree Evaluation in o(log n · log log n) space -- On parallel repetitions of interactive proof systems -- On locally-characterized expander graphs (a survey) -- On the Locally Testable Code of Dinur et al. (2021) -- On the lower bound on the length of relaxed Locally Decodable Codes -- On the relaxed LDC of BGHSV: A survey that corrects the record -- On the complexity of estimating the Effective Support Size -- Robust Self-Ordering versus Local Self-Ordering -- On Testing Hamiltonicity in the Bounded Degree Graph Model -- Testing Isomorphism in the Bounded-Degree Graph Model -- On Testing Isomorphism to a fixed graph in the Bounded-Degree Graph Model -- On Testing Asymmetry in the Bounded Degree Graph Model -- On the query complexity of testing local graph properties in the Bounded-Degree Graph Model -- Testing in the bounded-degree graph model with degree bound two -- On properties that are non-trivial to test -- One-Sided Error Testing of Monomials and Affine Subspaces -- On testing group properties. |
| Record Nr. | UNINA-9911009341403321 |
Goldreich Oded
|
||
| Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2025 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Computational Complexity and Local Algorithms : On the Interplay Between Randomness and Computation / / edited by Oded Goldreich
| Computational Complexity and Local Algorithms : On the Interplay Between Randomness and Computation / / edited by Oded Goldreich |
| Autore | Goldreich Oded |
| Edizione | [1st ed. 2025.] |
| Pubbl/distr/stampa | Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2025 |
| Descrizione fisica | 1 online resource (1007 pages) |
| Disciplina | 005.13 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Algorithms
Computational complexity Mathematics - Data processing Design and Analysis of Algorithms Computational Complexity Computational Mathematics and Numerical Analysis |
| ISBN | 3-031-88946-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | -. On defining PPT-search problems -- -. Multi-pseudodeterministic algorithms -- On counting t-cliques Mod 2 -- On coarse and fine approximate counting of t-cliques -- On the complexity of enumerating ordered sets -- On the Cook-Mertz Tree Evaluation procedure -- Solving Tree Evaluation in o(log n · log log n) space -- On parallel repetitions of interactive proof systems -- On locally-characterized expander graphs (a survey) -- On the Locally Testable Code of Dinur et al. (2021) -- On the lower bound on the length of relaxed Locally Decodable Codes -- On the relaxed LDC of BGHSV: A survey that corrects the record -- On the complexity of estimating the Effective Support Size -- Robust Self-Ordering versus Local Self-Ordering -- On Testing Hamiltonicity in the Bounded Degree Graph Model -- Testing Isomorphism in the Bounded-Degree Graph Model -- On Testing Isomorphism to a fixed graph in the Bounded-Degree Graph Model -- On Testing Asymmetry in the Bounded Degree Graph Model -- On the query complexity of testing local graph properties in the Bounded-Degree Graph Model -- Testing in the bounded-degree graph model with degree bound two -- On properties that are non-trivial to test -- One-Sided Error Testing of Monomials and Affine Subspaces -- On testing group properties. |
| Record Nr. | UNISA-996664548203316 |
|
Goldreich Oded
|
||
| Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2025 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Providing Sound Foundations for Cryptography : On the Work of Shafi Goldwasser and Silvio Micali
| Providing Sound Foundations for Cryptography : On the Work of Shafi Goldwasser and Silvio Micali |
| Autore | Goldreich Oded |
| Edizione | [1st ed.] |
| Pubbl/distr/stampa | San Rafael : , : Morgan & Claypool Publishers, , 2019 |
| Descrizione fisica | 1 online resource (838 pages) |
| Disciplina | 005.824 |
| Collana | ACM Bks. |
| Soggetto topico |
Algorithms
Computer algorithms Computer scientists |
| ISBN | 1-4503-7269-4 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Intro -- Contents -- Preface -- Acknowledgments -- Photo and Text Credits -- PART I. BIOGRAPHIES, INTERVIEWS, AND AWARD LECTURES -- 1. A Story Behind Every Problem: A Brief Biography of Shafi Goldwasser -- 2. One Obsession at a Time: A Brief Biography of Silvio Micali -- 3. An Interview with Shafi Goldwasser -- 4. An Interview with Silvio Micali -- 5. The Cryptographic Lens: Shafi Goldwasser'sTuring Lecture -- 6. Proofs, According to Silvio: Silvio Micali's Turing Lecture -- PART II. ORIGINAL PAPERS -- 7. Probabilistic Encryption -- 8. The Knowledge Complexity of Interactive Proof Systems -- 9. How to Generate Cryptographically Strong Sequences of Pseudorandom Bits -- 10. How to Construct Random Functions -- 11. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks -- 12. Proofs that Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems -- 13. How to Play Any Mental Game: A Completeness Theorem for Protocols with Honest Majority -- 14. Non-Interactive Zero-Knowledge (NIZK) Proof Systems -- 15. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation -- 16. Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions -- PART III. PERSPECTIVES -- 17. On the Foundations of Cryptography -- 18. On the Impact of Cryptography on Complexity Theory -- 19. On Some Noncryptographic Works of Goldwasser and Micali -- 20. Fundamentals of Fully Homomorphic Encryption -- 21. Interactive Proofs for Lattice Problems -- 22. Following a Tangent of Proofs -- 23. A Tutorial on Concurrent Zero-Knowledge -- 24. Doubly Efficient Interactive Proofs -- 25. Computational Entropy -- 26. A Survey of Leakage-Resilient Cryptography -- Editor and Author Biographies -- Blank Page. |
| Altri titoli varianti | Providing Sound Foundations for Cryptography |
| Record Nr. | UNINA-9910838221303321 |
|
Goldreich Oded
|
||
| San Rafael : , : Morgan & Claypool Publishers, , 2019 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Studies in Complexity and Cryptography [[electronic resource] ] : Miscellanea on the Interplay between Randomness and Computation / / by Oded Goldreich
| Studies in Complexity and Cryptography [[electronic resource] ] : Miscellanea on the Interplay between Randomness and Computation / / by Oded Goldreich |
| Autore | Goldreich Oded |
| Edizione | [1st ed. 2011.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2011 |
| Descrizione fisica | 1 online resource (XI, 563 p. 9 illus., 1 illus. in color.) |
| Disciplina | 511.3/52 |
| Altri autori (Persone) | AvigadLidor |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science
Cryptography Data encryption (Computer science) Machine theory Computer science—Mathematics Discrete mathematics Algorithms Theory of Computation Cryptology Formal Languages and Automata Theory Discrete Mathematics in Computer Science |
| ISBN | 3-642-22670-1 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Research Contributions -- Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard.- Proving Computational Ability -- On Constructing 1-1 One-Way Functions -- On the Circuit Complexity of Perfect Hashing.- Collision-Free Hashing from Lattice Problems.- Another Proof That BPP ⊆ PH (and More) -- Strong Proofs of Knowledge -- Simplified Derandomization of BPP Using a Hitting Set Generator.- On Testing Expansion in Bounded-Degree Graphs.- Candidate One-Way Functions Based on Expander Graphs.- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.- The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles.- From Logarithmic Advice to Single-Bit Advice.- On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge.- On the Average-Case Complexity of Property Testing.- A Candidate Counterexample to the Easy Cylinders Conjecture.- From Absolute Distinguishability to Positive Distinguishability.- Testing Graph Blow-Up.- Proximity Oblivious Testing and the Role of Invariances.- In a World of P=BPP.- Surveys -- Notes on Levin’s Theory of Average-Case Complexity.- Three XOR-Lemmas — An Exposition.- On Yao’s XOR-Lemma.- A Sample of Samplers: A Computational Perspective on Sampling.- Short Locally Testable Codes and Proofs.- Bravely, Moderately: A Common Theme in Four Recent Works.- On the Complexity of Computational Problems Regarding Distributions.- Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art.- Average Case Complexity, Revisited.- Basic Facts about Expander Graphs.- A Brief Introduction to Property Testing.- Introduction to Testing Graph Properties.- Randomness and Computation.- Programmatic and Reflective Articles -- On Security Preserving Reductions – Revised Terminology.- Contemplations on Testing Graph Properties.- Another Motivation for Reducing the Randomness Complexity of Algorithms.- About the Authors. . |
| Record Nr. | UNISA-996465753403316 |
|
Goldreich Oded
|
||
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2011 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||