↓ Skip to main content

Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation

Overview of attention for book
Cover of 'Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
  3. Altmetric Badge
    Chapter 2 Proving Computational Ability
  4. Altmetric Badge
    Chapter 3 On Constructing 1-1 One-Way Functions
  5. Altmetric Badge
    Chapter 4 On the Circuit Complexity of Perfect Hashing
  6. Altmetric Badge
    Chapter 5 Collision-Free Hashing from Lattice Problems
  7. Altmetric Badge
    Chapter 6 Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
  8. Altmetric Badge
    Chapter 7 Strong Proofs of Knowledge
  9. Altmetric Badge
    Chapter 8 Simplified Derandomization of BPP Using a Hitting Set Generator
  10. Altmetric Badge
    Chapter 9 On Testing Expansion in Bounded-Degree Graphs
  11. Altmetric Badge
    Chapter 10 Candidate One-Way Functions Based on Expander Graphs
  12. Altmetric Badge
    Chapter 11 Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
  13. Altmetric Badge
    Chapter 12 The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles
  14. Altmetric Badge
    Chapter 13 From Logarithmic Advice to Single-Bit Advice
  15. Altmetric Badge
    Chapter 14 On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge
  16. Altmetric Badge
    Chapter 15 On the Average-Case Complexity of Property Testing
  17. Altmetric Badge
    Chapter 16 A Candidate Counterexample to the Easy Cylinders Conjecture
  18. Altmetric Badge
    Chapter 17 From Absolute Distinguishability to Positive Distinguishability
  19. Altmetric Badge
    Chapter 18 Testing Graph Blow-Up
  20. Altmetric Badge
    Chapter 19 Proximity Oblivious Testing and the Role of Invariances
  21. Altmetric Badge
    Chapter 20 In a World of P=BPP
  22. Altmetric Badge
    Chapter 21 Notes on Levin’s Theory of Average-Case Complexity
  23. Altmetric Badge
    Chapter 22 Three XOR-Lemmas — An Exposition
  24. Altmetric Badge
    Chapter 23 On Yao’s XOR-Lemma
  25. Altmetric Badge
    Chapter 24 A Sample of Samplers: A Computational Perspective on Sampling
  26. Altmetric Badge
    Chapter 25 Short Locally Testable Codes and Proofs
  27. Altmetric Badge
    Chapter 26 Bravely, Moderately: A Common Theme in Four Recent Works
  28. Altmetric Badge
    Chapter 27 On the Complexity of Computational Problems Regarding Distributions
  29. Altmetric Badge
    Chapter 28 Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art
  30. Altmetric Badge
    Chapter 29 Average Case Complexity, Revisited
  31. Altmetric Badge
    Chapter 30 Basic Facts about Expander Graphs
  32. Altmetric Badge
    Chapter 31 A Brief Introduction to Property Testing
  33. Altmetric Badge
    Chapter 32 Introduction to Testing Graph Properties
  34. Altmetric Badge
    Chapter 33 Randomness and Computation
  35. Altmetric Badge
    Chapter 34 On Security Preserving Reductions – Revised Terminology
  36. Altmetric Badge
    Chapter 35 Contemplations on Testing Graph Properties
  37. Altmetric Badge
    Chapter 36 Another Motivation for Reducing the Randomness Complexity of Algorithms
Attention for Chapter 2: Proving Computational Ability
Altmetric Badge

Mentioned by

twitter
1 X user

Citations

dimensions_citation
14 Dimensions

Readers on

mendeley
2 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Chapter title
Proving Computational Ability
Chapter number 2
Book title
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation
Published in
Lecture notes in computer science, February 2016
DOI 10.1007/978-3-642-22670-0_2
Book ISBNs
978-3-64-222669-4, 978-3-64-222670-0
Authors

Mihir Bellare, Oded Goldreich, Bellare, Mihir, Goldreich, Oded

X Demographics

X Demographics

The data shown below were collected from the profile of 1 X user who shared this research output. Click here to find out more about how the information was compiled.
Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 2 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
United States 1 50%
Unknown 1 50%

Demographic breakdown

Readers by professional status Count As %
Student > Ph. D. Student 2 100%
Readers by discipline Count As %
Computer Science 2 100%
Attention Score in Context

Attention Score in Context

This research output has an Altmetric Attention Score of 1. This is our high-level measure of the quality and quantity of online attention that it has received. This Attention Score, as well as the ranking and number of research outputs shown below, was calculated when the research output was last mentioned on 28 February 2013.
All research outputs
#18,331,227
of 22,699,621 outputs
Outputs from Lecture notes in computer science
#6,006
of 8,125 outputs
Outputs of similar age
#286,905
of 396,598 outputs
Outputs of similar age from Lecture notes in computer science
#391
of 509 outputs
Altmetric has tracked 22,699,621 research outputs across all sources so far. This one is in the 11th percentile – i.e., 11% of other outputs scored the same or lower than it.
So far Altmetric has tracked 8,125 research outputs from this source. They receive a mean Attention Score of 5.0. This one is in the 14th percentile – i.e., 14% of its peers scored the same or lower than it.
Older research outputs will score higher simply because they've had more time to accumulate mentions. To account for age we can compare this Altmetric Attention Score to the 396,598 tracked outputs that were published within six weeks on either side of this one in any source. This one is in the 15th percentile – i.e., 15% of its contemporaries scored the same or lower than it.
We're also able to compare this research output to 509 others from the same source and published within six weeks on either side of this one. This one is in the 13th percentile – i.e., 13% of its contemporaries scored the same or lower than it.