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...

Fuld beskrivelse

Bibliografiske detaljer
Main Authors:	Lu, Z, Oliveira, IC, Santhanam, R
Format:	Conference item
Sprog:	English
Udgivet:	Association for Computing Machinery 2021

Lignende værker

Pseudodeterministic constructions in subexponential time
af: Oliveira, I, et al.
Udgivet: (2017)

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

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

Hardness magnification for natural problems
af: Santhanam, R, et al.
Udgivet: (2018)

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

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

Probabilistic routing algorithm
af: Ta Hoang, Thuc Khanh
Udgivet: (2014)

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

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

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

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

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

Probabilistic analysis of the greedy algorithm.
af: N.N. Kuzjurin
Udgivet: (2004-01-01)

Probabilistic Algorithm in Finite Fields
af: Rabin, Michael O.
Udgivet: (2023)

Algorithmic probabilistic game semantics
af: Kiefer, S, et al.
Udgivet: (2013)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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