All
All

What are you looking for?

All
Projects
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”
EN
ČeštinaEnglish

Randomness, pseudorandomness and models of arithmetic

Result description

Pseudorandomness plays an important role in number theory, complexity theory and cryptography. Our aim is to use models of arithmetic to explain pseudorandomness by randomness. To this and we construct a set of models M, a common element i of these models and a probability distribution on M, such that for every pseudorandom sequence s, the probability that s(i)=1 holds true in a random model from M is equal to 1/2.

Keywords

pseudorandomnessnumber theory

The result's identifiers

Alternative languages

  • Result language

    angličtina

  • Original language name

    Randomness, pseudorandomness and models of arithmetic

  • Original language description

    Pseudorandomness plays an important role in number theory, complexity theory and cryptography. Our aim is to use models of arithmetic to explain pseudorandomness by randomness. To this and we construct a set of models M, a common element i of these models and a probability distribution on M, such that for every pseudorandom sequence s, the probability that s(i)=1 holds true in a random model from M is equal to 1/2.

  • Czech name

    —

  • Czech description

    —

Classification

  • Type

    C - Chapter in a specialist book

  • CEP classification

    BA - General mathematics

  • OECD FORD branch

    —

Result continuities

Others

  • Publication year

    2013

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Book/collection name

    New Studies in Weak Arithmetics

  • ISBN

    978-1-57586-723-6

  • Number of pages of the result

    18

  • Pages from-to

    199-216

  • Number of pages of the book

    221

  • Publisher name

    Center for the Study of Language and Information

  • Place of publication

    Stanford

  • UT code for WoS chapter

    —

Basic information

Result type

C - Chapter in a specialist book

C

CEP

BA - General mathematics

Year of implementation

2013

Similar results(10)

THE PHASE TRANSITION OF DISCREPANCY IN RANDOM HYPERGRAPHSConspiracies Between Learning Algorithms, Circuit Lower Bounds, and PseudorandomnessKolmogorov complexity, pseudorandom generators and statistical models testing.