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

书目详细资料
Main Authors:	Lu, Z, Oliveira, IC, Santhanam, R
格式:	Conference item
语言:	English
出版:	Association for Computing Machinery 2021

相似书籍

Pseudodeterministic constructions in subexponential time
由: Oliveira, I, et al.
出版: (2017)

On the Possibilities and Limitations of Pseudodeterministic Algorithms
由: Goldreich, Oded, et al.
出版: (2021)

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

Hardness magnification for natural problems
由: Santhanam, R, et al.
出版: (2018)

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

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

Probabilistic routing algorithm
由: Ta Hoang, Thuc Khanh
出版: (2014)

Probabilistic Algorithmic Knowledge
由: Joseph Y. Halpern, et al.
出版: (2005-12-01)

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

Optimal solutions in probabilistic structural design/
由: 421269 Parimi, S. R., et al.
出版: (1974)

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

Quantitative program logic and expected time bounds in probabilistic distributed algorithms
由: McIver, A
出版: (2002)

Probabilistic analysis of the greedy algorithm.
由: N.N. Kuzjurin
出版: (2004-01-01)

Probabilistic Algorithm in Finite Fields
由: Rabin, Michael O.
出版: (2023)

Algorithmic probabilistic game semantics
由: Kiefer, S, et al.
出版: (2013)

Multi-criteria probabilistic structural design /
由: 418569 Cohn, M. Z.
出版: (1971)

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

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

Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
由: Oliveira, I, et al.
出版: (2017)

Probabilistic models and optimization algorithms for large-scale transportation problems
由: Lu, Jing
出版: (2020)

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

Probabilistic learning algorithms and optimality theory
由: Keller, F, et al.
出版: (2002)

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

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

Probabilistic adaptive computation time
由: M. Figurnov, et al.
出版: (2018-12-01)

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

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

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

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

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

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

A Probabilistic Analysis of the Nxt Forging Algorithm
由: Serguei Popov
出版: (2016-12-01)

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

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

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

Probabilistic Intuitionistic Fuzzy Decision Making Algorithms
由: Rinki Solanki, et al.
出版: (2021-01-01)

Probabilistic Logic under Coherence: Complexity and Algorithms
由: Biazzo, V, et al.
出版: (2005)

Probabilistic Logic under Coherence: Complexity and Algorithms
由: Biazzo, V, et al.
出版: (2001)

Modeling cognition with probabilistic programs : representations and algorithms
由: Stuhlmüller, Andreas
出版: (2016)

A Statistical Analysis of Probabilistic Counting Algorithms
由: Clifford, P, et al.
出版: (2012)