Conference item icon

Conference item

Pseudo-derandomizing learning and approximation

Abstract:

We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser [Eran Gat and Shafi Goldwasser, 2011]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed output with high probability. We explore pseudo-determinism in the settings of learning and approximation. Our goal is to simulate known randomized algorithms in these settings by pseudo-deterministic algorithms in a generic fashion - a goal we succinctly term pseudo-derandomization....

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.APPROX-RANDOM.2018.55

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Magdalen College
Role:
Author
Publisher:
Schloss Dagstuhl Publisher's website
Journal:
22nd International Conference on Randomization and Approximation Journal website
Volume:
116
Series:
Leibniz International Proceedings in Informatics
Host title:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Publication date:
2018-08-02
Acceptance date:
2018-06-01
DOI:
ISSN:
1868-8969
Source identifiers:
908930
ISBN:
9783959770859
Keywords:
Pubs id:
pubs:908930
UUID:
uuid:c7f33f22-d7aa-41ae-aa7d-a4f37c1a1f18
Local pid:
pubs:908930
Deposit date:
2018-08-18

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP