E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
-
ISBN:
979-8-3503-3587-3
-
Date (published):
14-Jul-2023
-
Event name:
Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
en
Event date:
26-Jun-2023 - 29-Jun-2023
-
Event place:
Boston, United States of America (the)
-
Number of Pages:
13
-
Publisher:
IEEE, Piscataway
-
Keywords:
derandomization; existentially closed graphs; finite models; graph transduction; pseudorandomness; Rado graph; random graphs; zero-one law
en
Abstract:
We study pseudorandomness and pseudorandom generators from the perspective of logical definability. Building on results from ordinary derandomization and finite model theory, we show that it is possible to deterministically construct, in polynomial time, graphs and relational structures that are statistically indistinguishable from random structures by any sentence of first order or least fixed point logics. This raises the question of whether such constructions can be implemented via logical transductions from simpler structures with less entropy. In other words, can logical formulas be pseudorandom generators? We provide a complete classification of when this is possible for first order logic, fixed point logic, and fixed point logic with parity, and provide partial results and conjectures for first order logic with parity.
