AIBullisharXiv – CS AI · Jun 197/10
🧠Researchers demonstrate that chain-of-thought transformers can efficiently simulate Word RAM algorithms with only poly-logarithmic overhead, enabling tasks like sorting and pathfinding at near-optimal computational complexity. This theoretical advance bridges the gap between practical algorithm design and transformer capabilities, suggesting reasoning models can perform substantial computation efficiently.
AINeutralarXiv – CS AI · Jun 236/10
🧠Researchers formalize the problem of synthesizing control policies for stochastic systems that maintain entropy-based objectives in Markov Decision Processes, proving the problem is computationally hard while developing a verification and synthesis method that combines convex duality and invariant synthesis techniques.
AINeutralarXiv – CS AI · Jun 116/10
🧠Researchers formalize test-time training (TTT) as a theoretical framework for sampling from complex probability distributions, proving that the Jerrum-Sinclair random walk approach is query-optimal with a quadratic lower bound. The work bridges generative AI sampling efficiency with classical algorithmic theory, establishing foundational principles for adapting language models during inference.
AINeutralarXiv – CS AI · May 286/10
🧠Researchers demonstrate that Vision Transformers face fundamental architectural limitations in spatial reasoning tasks due to computational complexity constraints. By framing spatial understanding as a group homomorphism problem, they prove that constant-depth ViTs cannot capture non-solvable spatial structures like 3D rotations, revealing a theoretical gap between required complexity classes.
AINeutralarXiv – CS AI · May 275/10
🧠Researchers present 2-ASP(Q)^w, a fragment of Answer Set Programming extended with quantifiers and weak constraints, proving its theoretical complexity bounds and introducing practical computation strategies using CEGAR techniques. The work bridges theoretical computer science with implementable solutions for optimization problems, offering both formal completeness results and experimental validation on real-world benchmarks.
AINeutralarXiv – CS AI · May 275/10
🧠This academic paper addresses inconsistency handling in prioritized knowledge bases by analyzing the computational complexity of query entailment and repair enumeration under three optimal repair notions (global, Pareto, completion). The work establishes formal connections between optimal repairs and argumentation theory extensions, offering theoretical foundations for knowledge base consistency management.
AINeutralarXiv – CS AI · May 16/10
🧠Researchers propose a novel rule-generation approach to evaluate compositionality in large language models, addressing critical limitations in existing assessment methods that lack explainability and suffer from dataset partition leakage. This new framework requires LLMs to generate executable programs as rules for data mapping, providing more robust insights into how well these models generalize compositional concepts.
