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

Mô tả đầy đủ

Chi tiết về thư mục
Những tác giả chính:	Lu, Z, Oliveira, IC, Santhanam, R
Định dạng:	Conference item
Ngôn ngữ:	English
Được phát hành:	Association for Computing Machinery 2021

Những quyển sách tương tự

Pseudodeterministic constructions in subexponential time
Bằng: Oliveira, I, et al.
Được phát hành: (2017)

On the Possibilities and Limitations of Pseudodeterministic Algorithms
Bằng: Goldreich, Oded, et al.
Được phát hành: (2021)

Algorithms and algorithmic obstacles for probabilistic combinatorial structures
Bằng: Li, Quan, Ph. D. Massachusetts Institute of Technology
Được phát hành: (2018)

Hardness magnification for natural problems
Bằng: Santhanam, R, et al.
Được phát hành: (2018)

Anti-chain based algorithms for timed/probabilistic refinement checking
Bằng: Wang, Ting, et al.
Được phát hành: (2020)

An average-case lower bound against ACC$^0$
Bằng: Chen, R, et al.
Được phát hành: (2018)

Probabilistic routing algorithm
Bằng: Ta Hoang, Thuc Khanh
Được phát hành: (2014)

Probabilistic Algorithmic Knowledge
Bằng: Joseph Y. Halpern, et al.
Được phát hành: (2005-12-01)

Hardness magnification near state-of-the-art lower bounds
Bằng: Oliveira, IC, et al.
Được phát hành: (2021)

Optimal solutions in probabilistic structural design/
Bằng: 421269 Parimi, S. R., et al.
Được phát hành: (1974)

A probabilistic fragment-based protein structure prediction algorithm.
Bằng: David Simoncini, et al.
Được phát hành: (2012-01-01)

Quantitative program logic and expected time bounds in probabilistic distributed algorithms
Bằng: McIver, A
Được phát hành: (2002)

Probabilistic analysis of the greedy algorithm.
Bằng: N.N. Kuzjurin
Được phát hành: (2004-01-01)

Probabilistic Algorithm in Finite Fields
Bằng: Rabin, Michael O.
Được phát hành: (2023)

Algorithmic probabilistic game semantics
Bằng: Kiefer, S, et al.
Được phát hành: (2013)

Multi-criteria probabilistic structural design /
Bằng: 418569 Cohn, M. Z.
Được phát hành: (1971)

Correction: A Probabilistic Fragment-Based Protein Structure Prediction Algorithm
Được phát hành: (2012-01-01)

Correction: A Probabilistic Fragment-Based Protein Structure Prediction Algorithm.
Bằng: David Simoncini, et al.
Được phát hành: (2012-01-01)

Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
Bằng: Oliveira, I, et al.
Được phát hành: (2017)

Probabilistic models and optimization algorithms for large-scale transportation problems
Bằng: Lu, Jing
Được phát hành: (2020)

Enhanced Probabilistic Inference Algorithm Using Probabilistic Neural Networks for Learning Control
Bằng: Yang Li, et al.
Được phát hành: (2019-01-01)

Probabilistic learning algorithms and optimality theory
Bằng: Keller, F, et al.
Được phát hành: (2002)

Probabilistic algorithm for mining frequent sequences
Bằng: Julija Pragarauskaitė, et al.
Được phát hành: (2010-12-01)

An Efficient Algorithm to Determine Probabilistic Bisimulation
Bằng: Jan Friso Groote, et al.
Được phát hành: (2018-09-01)

Probabilistic adaptive computation time
Bằng: M. Figurnov, et al.
Được phát hành: (2018-12-01)

Discrete- and Continuous-Time Probabilistic Models and Algorithms for Inferring Neuronal UP and DOWN States
Bằng: Chen, Zhe, et al.
Được phát hành: (2012)

Algorithms and probabilistic models of parameters of operation of in-plant power supply
Bằng: E. I. Gracheva, et al.
Được phát hành: (2021-05-01)

Pinning Stabilization of Probabilistic Boolean Networks With Time Delays
Bằng: Pengwei Liu, et al.
Được phát hành: (2020-01-01)

AN IMPROVED PDR INDOOR LOCAION ALGORITHM BASED ON PROBABILISTIC CONSTRAINTS
Bằng: Y. You, et al.
Được phát hành: (2017-09-01)

A Bayesian Network Structure Learning Algorithm Based on Probabilistic Incremental Analysis and Constraint
Bằng: Haoran Liu, et al.
Được phát hành: (2022-01-01)

SPA: a probabilistic algorithm for spliced alignment.
Được phát hành: (2006-04-01)

A Probabilistic Analysis of the Nxt Forging Algorithm
Bằng: Serguei Popov
Được phát hành: (2016-12-01)

OPTIMIZATION OF THE PROBABILISTIC ALGORITHM FOR RESOLVING AIRSPACE CONFLICTS
Bằng: Gabriela STROE, et al.
Được phát hành: (2020-12-01)

SPA: a probabilistic algorithm for spliced alignment.
Bằng: Erik van Nimwegen, et al.
Được phát hành: (2006-04-01)

Probabilistic analysis a algorithm for strip packing
Bằng: N. N. Kuzjurin, et al.
Được phát hành: (2018-10-01)

Probabilistic Intuitionistic Fuzzy Decision Making Algorithms
Bằng: Rinki Solanki, et al.
Được phát hành: (2021-01-01)

Probabilistic Logic under Coherence: Complexity and Algorithms
Bằng: Biazzo, V, et al.
Được phát hành: (2005)

Probabilistic Logic under Coherence: Complexity and Algorithms
Bằng: Biazzo, V, et al.
Được phát hành: (2001)

Modeling cognition with probabilistic programs : representations and algorithms
Bằng: Stuhlmüller, Andreas
Được phát hành: (2016)

A Statistical Analysis of Probabilistic Counting Algorithms
Bằng: Clifford, P, et al.
Được phát hành: (2012)