Advances in Computational Complexity and Probabilistic Models

The field of computational complexity and probabilistic models is moving in a direction that emphasizes the development of new techniques and tools for analyzing and understanding complex systems. Recent research has focused on the study of algebraic pseudorandomness, internal effectful forcing, and the counting power of transformers with no positional encodings. These advances have led to a deeper understanding of the limitations and possibilities of various computational models, including arithmetic circuits, automata, and Markov chains. Notably, the development of new logical relations and fibrational models has enabled the construction of more expressive and flexible models for reasoning about probabilistic systems. Furthermore, the study of energy games, Galois energy games, and probabilistic bisimilarity has led to new insights into the behavior of complex systems and the development of more efficient algorithms for analyzing them. Overall, the field is experiencing a surge of innovation, driven by the intersection of theoretical computer science, mathematics, and probability theory. Some noteworthy papers in this area include: NoPE: The Counting Power of Transformers with No Positional Encodings, which shows that transformers without positional encodings can still express complex counting properties. Robust Probabilistic Bisimilarity for Labelled Markov Chains, which introduces a new notion of robust probabilistic bisimilarity that ensures continuity of the probabilistic bisimilarity distance function.

Sources

Algebraic Pseudorandomness in $VNC^0$

Internal Effectful Forcing in System T

NoPE: The Counting Power of Transformers with No Positional Encodings

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter

Linear Hashing Is Optimal

Logical relations for call-by-push-value models, via internal fibrations in a 2-category

Credible Sets of Phylogenetic Tree Topology Distributions

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems

Propositional Measure Logic

On the Possibilities of Hypercomputing Supertasks

Robust Probabilistic Bisimilarity for Labelled Markov Chains

Approximate Probabilistic Bisimulation for Continuous-Time Markov Chains

Efficient Probabilistic Model Checking for Relational Reachability (Extended Version)

Restricted Chase Termination: You Want More than Fairness

Flipping and Forking

A Riemannian Optimization Approach for Finding the Nearest Reversible Markov Chain

A Chase-based Approach to Consistent Answers of Analytic Queries in Star Schemas

Predicate-Conditional Conformalized Answer Sets for Knowledge Graph Embeddings

A Formal Proof of Complexity Bounds on Diophantine Equations

Built with on top of