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

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Lu, Z, Oliveira, IC, Santhanam, R
Formáid:	Conference item
Teanga:	English
Foilsithe / Cruthaithe:	Association for Computing Machinery 2021

Míreanna comhchosúla

Pseudodeterministic constructions in subexponential time
de réir: Oliveira, I, et al.
Foilsithe / Cruthaithe: (2017)

On the Possibilities and Limitations of Pseudodeterministic Algorithms
de réir: Goldreich, Oded, et al.
Foilsithe / Cruthaithe: (2021)

Algorithms and algorithmic obstacles for probabilistic combinatorial structures
de réir: Li, Quan, Ph. D. Massachusetts Institute of Technology
Foilsithe / Cruthaithe: (2018)

Hardness magnification for natural problems
de réir: Santhanam, R, et al.
Foilsithe / Cruthaithe: (2018)

Anti-chain based algorithms for timed/probabilistic refinement checking
de réir: Wang, Ting, et al.
Foilsithe / Cruthaithe: (2020)

An average-case lower bound against ACC$^0$
de réir: Chen, R, et al.
Foilsithe / Cruthaithe: (2018)

Probabilistic routing algorithm
de réir: Ta Hoang, Thuc Khanh
Foilsithe / Cruthaithe: (2014)

Probabilistic Algorithmic Knowledge
de réir: Joseph Y. Halpern, et al.
Foilsithe / Cruthaithe: (2005-12-01)

Hardness magnification near state-of-the-art lower bounds
de réir: Oliveira, IC, et al.
Foilsithe / Cruthaithe: (2021)

Optimal solutions in probabilistic structural design/
de réir: 421269 Parimi, S. R., et al.
Foilsithe / Cruthaithe: (1974)

A probabilistic fragment-based protein structure prediction algorithm.
de réir: David Simoncini, et al.
Foilsithe / Cruthaithe: (2012-01-01)

Quantitative program logic and expected time bounds in probabilistic distributed algorithms
de réir: McIver, A
Foilsithe / Cruthaithe: (2002)

Probabilistic analysis of the greedy algorithm.
de réir: N.N. Kuzjurin
Foilsithe / Cruthaithe: (2004-01-01)

Probabilistic Algorithm in Finite Fields
de réir: Rabin, Michael O.
Foilsithe / Cruthaithe: (2023)

Algorithmic probabilistic game semantics
de réir: Kiefer, S, et al.
Foilsithe / Cruthaithe: (2013)

Multi-criteria probabilistic structural design /
de réir: 418569 Cohn, M. Z.
Foilsithe / Cruthaithe: (1971)

Correction: A Probabilistic Fragment-Based Protein Structure Prediction Algorithm
Foilsithe / Cruthaithe: (2012-01-01)

Correction: A Probabilistic Fragment-Based Protein Structure Prediction Algorithm.
de réir: David Simoncini, et al.
Foilsithe / Cruthaithe: (2012-01-01)

Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
de réir: Oliveira, I, et al.
Foilsithe / Cruthaithe: (2017)

Probabilistic models and optimization algorithms for large-scale transportation problems
de réir: Lu, Jing
Foilsithe / Cruthaithe: (2020)

Enhanced Probabilistic Inference Algorithm Using Probabilistic Neural Networks for Learning Control
de réir: Yang Li, et al.
Foilsithe / Cruthaithe: (2019-01-01)

Probabilistic learning algorithms and optimality theory
de réir: Keller, F, et al.
Foilsithe / Cruthaithe: (2002)

Probabilistic algorithm for mining frequent sequences
de réir: Julija Pragarauskaitė, et al.
Foilsithe / Cruthaithe: (2010-12-01)

An Efficient Algorithm to Determine Probabilistic Bisimulation
de réir: Jan Friso Groote, et al.
Foilsithe / Cruthaithe: (2018-09-01)

Probabilistic adaptive computation time
de réir: M. Figurnov, et al.
Foilsithe / Cruthaithe: (2018-12-01)

Discrete- and Continuous-Time Probabilistic Models and Algorithms for Inferring Neuronal UP and DOWN States
de réir: Chen, Zhe, et al.
Foilsithe / Cruthaithe: (2012)

Algorithms and probabilistic models of parameters of operation of in-plant power supply
de réir: E. I. Gracheva, et al.
Foilsithe / Cruthaithe: (2021-05-01)

Pinning Stabilization of Probabilistic Boolean Networks With Time Delays
de réir: Pengwei Liu, et al.
Foilsithe / Cruthaithe: (2020-01-01)

AN IMPROVED PDR INDOOR LOCAION ALGORITHM BASED ON PROBABILISTIC CONSTRAINTS
de réir: Y. You, et al.
Foilsithe / Cruthaithe: (2017-09-01)

A Bayesian Network Structure Learning Algorithm Based on Probabilistic Incremental Analysis and Constraint
de réir: Haoran Liu, et al.
Foilsithe / Cruthaithe: (2022-01-01)

SPA: a probabilistic algorithm for spliced alignment.
Foilsithe / Cruthaithe: (2006-04-01)

A Probabilistic Analysis of the Nxt Forging Algorithm
de réir: Serguei Popov
Foilsithe / Cruthaithe: (2016-12-01)

OPTIMIZATION OF THE PROBABILISTIC ALGORITHM FOR RESOLVING AIRSPACE CONFLICTS
de réir: Gabriela STROE, et al.
Foilsithe / Cruthaithe: (2020-12-01)

SPA: a probabilistic algorithm for spliced alignment.
de réir: Erik van Nimwegen, et al.
Foilsithe / Cruthaithe: (2006-04-01)

Probabilistic analysis a algorithm for strip packing
de réir: N. N. Kuzjurin, et al.
Foilsithe / Cruthaithe: (2018-10-01)

Probabilistic Intuitionistic Fuzzy Decision Making Algorithms
de réir: Rinki Solanki, et al.
Foilsithe / Cruthaithe: (2021-01-01)

Probabilistic Logic under Coherence: Complexity and Algorithms
de réir: Biazzo, V, et al.
Foilsithe / Cruthaithe: (2005)

Probabilistic Logic under Coherence: Complexity and Algorithms
de réir: Biazzo, V, et al.
Foilsithe / Cruthaithe: (2001)

Modeling cognition with probabilistic programs : representations and algorithms
de réir: Stuhlmüller, Andreas
Foilsithe / Cruthaithe: (2016)

A Statistical Analysis of Probabilistic Counting Algorithms
de réir: Clifford, P, et al.
Foilsithe / Cruthaithe: (2012)