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)