wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

self_reducibility (433B)

      1 # Self-reducibility
      2 
      3 https://en.wikipedia.org/wiki/Function_problem#Self-reducibility
      4 
      5 The paper [jerrum1986random] that defines it shows equivalence of [counting_approximate] and [sampling_approximate]
      6 - it also shows that [counting_approximate] to within a constant factor allows you, for self-reducible problems, to do [counting_approximate] with a [fpras], by going via [sampling_approximate]
      7 
      8 Up: [theoretical_computer_science]