Pseudodeterministic algorithms and the structure of probabilistic time

Pseudodeterministic algorithms and the structure of probabilistic time

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of BPTIME: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows. <br> A new unconditional pseudorandom gen...

Bibliografske podrobnosti
Main Authors:	Lu, Z, Oliveira, IC, Santhanam, R
Format:	Conference item
Jezik:	English
Izdano:	Association for Computing Machinery 2021

Podobne knjige/članki

Pseudodeterministic constructions in subexponential time
od: Oliveira, I, et al.
Izdano: (2017)

On the Possibilities and Limitations of Pseudodeterministic Algorithms
od: Goldreich, Oded, et al.
Izdano: (2021)

Algorithms and algorithmic obstacles for probabilistic combinatorial structures
od: Li, Quan, Ph. D. Massachusetts Institute of Technology
Izdano: (2018)

Hardness magnification for natural problems
od: Santhanam, R, et al.
Izdano: (2018)

Anti-chain based algorithms for timed/probabilistic refinement checking
od: Wang, Ting, et al.
Izdano: (2020)

An average-case lower bound against ACC$^0$
od: Chen, R, et al.
Izdano: (2018)

Probabilistic routing algorithm
od: Ta Hoang, Thuc Khanh
Izdano: (2014)

Probabilistic Algorithmic Knowledge
od: Joseph Y. Halpern, et al.
Izdano: (2005-12-01)

Hardness magnification near state-of-the-art lower bounds
od: Oliveira, IC, et al.
Izdano: (2021)

Optimal solutions in probabilistic structural design/
od: 421269 Parimi, S. R., et al.
Izdano: (1974)

A probabilistic fragment-based protein structure prediction algorithm.
od: David Simoncini, et al.
Izdano: (2012-01-01)

Quantitative program logic and expected time bounds in probabilistic distributed algorithms
od: McIver, A
Izdano: (2002)

Probabilistic analysis of the greedy algorithm.
od: N.N. Kuzjurin
Izdano: (2004-01-01)

Probabilistic Algorithm in Finite Fields
od: Rabin, Michael O.
Izdano: (2023)

Algorithmic probabilistic game semantics
od: Kiefer, S, et al.
Izdano: (2013)

Multi-criteria probabilistic structural design /
od: 418569 Cohn, M. Z.
Izdano: (1971)

Correction: A Probabilistic Fragment-Based Protein Structure Prediction Algorithm
Izdano: (2012-01-01)

Correction: A Probabilistic Fragment-Based Protein Structure Prediction Algorithm.
od: David Simoncini, et al.
Izdano: (2012-01-01)

Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
od: Oliveira, I, et al.
Izdano: (2017)

Probabilistic models and optimization algorithms for large-scale transportation problems
od: Lu, Jing
Izdano: (2020)

Enhanced Probabilistic Inference Algorithm Using Probabilistic Neural Networks for Learning Control
od: Yang Li, et al.
Izdano: (2019-01-01)

Probabilistic learning algorithms and optimality theory
od: Keller, F, et al.
Izdano: (2002)

Probabilistic algorithm for mining frequent sequences
od: Julija Pragarauskaitė, et al.
Izdano: (2010-12-01)

An Efficient Algorithm to Determine Probabilistic Bisimulation
od: Jan Friso Groote, et al.
Izdano: (2018-09-01)

Probabilistic adaptive computation time
od: M. Figurnov, et al.
Izdano: (2018-12-01)

Discrete- and Continuous-Time Probabilistic Models and Algorithms for Inferring Neuronal UP and DOWN States
od: Chen, Zhe, et al.
Izdano: (2012)

Algorithms and probabilistic models of parameters of operation of in-plant power supply
od: E. I. Gracheva, et al.
Izdano: (2021-05-01)

Pinning Stabilization of Probabilistic Boolean Networks With Time Delays
od: Pengwei Liu, et al.
Izdano: (2020-01-01)

AN IMPROVED PDR INDOOR LOCAION ALGORITHM BASED ON PROBABILISTIC CONSTRAINTS
od: Y. You, et al.
Izdano: (2017-09-01)

A Bayesian Network Structure Learning Algorithm Based on Probabilistic Incremental Analysis and Constraint
od: Haoran Liu, et al.
Izdano: (2022-01-01)

SPA: a probabilistic algorithm for spliced alignment.
Izdano: (2006-04-01)

A Probabilistic Analysis of the Nxt Forging Algorithm
od: Serguei Popov
Izdano: (2016-12-01)

OPTIMIZATION OF THE PROBABILISTIC ALGORITHM FOR RESOLVING AIRSPACE CONFLICTS
od: Gabriela STROE, et al.
Izdano: (2020-12-01)

SPA: a probabilistic algorithm for spliced alignment.
od: Erik van Nimwegen, et al.
Izdano: (2006-04-01)

Probabilistic analysis a algorithm for strip packing
od: N. N. Kuzjurin, et al.
Izdano: (2018-10-01)

Probabilistic Intuitionistic Fuzzy Decision Making Algorithms
od: Rinki Solanki, et al.
Izdano: (2021-01-01)

Probabilistic Logic under Coherence: Complexity and Algorithms
od: Biazzo, V, et al.
Izdano: (2005)

Probabilistic Logic under Coherence: Complexity and Algorithms
od: Biazzo, V, et al.
Izdano: (2001)

Modeling cognition with probabilistic programs : representations and algorithms
od: Stuhlmüller, Andreas
Izdano: (2016)

A Statistical Analysis of Probabilistic Counting Algorithms
od: Clifford, P, et al.
Izdano: (2012)