- Beyond Bits: An Introduction to Computation over the Reals Tillmann Miltzow Thu 02 April 2026
- An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds Deepanshu Kush Thu 02 April 2026
- The Mystery Deepens: On the Query Complexity of Tarski Fixed Points Xi Chen Yuhao Li Mihalis Yannakakis Thu 02 April 2026
- Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation Michał R. Przybyłek Paweł Siedlecki Tue 31 March 2026
- Ideals, Macaulay Bases, and PCPs Prashanth Amireddy Amik Raj Behera Srikanth Srinivasan Madhu Sudan Sophus Valentin Willumsgaard Tue 31 March 2026
- Visibly Recursive Automata Kévin Dubrulle Véronique Bruyère Guillermo A. Pérez Gaetan Staquet Tue 17 March 2026
- Hypersequent Calculi Have Ackermannian Complexity A.~R. Balasubramanian Vitor Greati Revantha Ramanayake Wed 25 February 2026
- Hilbert's Nullstellensatz is in the Counting Hierarchy Robert Andrews Abhibhav Garg Éric Schost Tue 24 February 2026
- The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth Jannik Schestag Norbert Zeh Thu 12 February 2026
- A Theory for Probabilistic Polynomial-Time Reasoning Lijie Chen Jiatu Li Igor C. Oliveira Ryan Williams Thu 12 February 2026
- Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard Leonid Dorochko Michał Wrona Tue 03 February 2026
- High Rate Efficient Local List Decoding from HDX Yotam Dikstein Max Hopkins Russell Impagliazzo Toniann Pitassi Tue 03 February 2026
- Verified polynomial-time reductions in Lean 4: formalizing the complexity of decision-relevant information Tristan Simas Sat 24 January 2026
- Hard Clique Formulas for Resolution Albert Atserias Thu 22 January 2026
- Arithmetic Complexity of Solutions of the Dirichlet Problem Holger Boche Volker Pohl H. Vincent Poor Sun 18 January 2026
- Correspondences in computational and dynamical complexity II: forcing complex reductions Samuel Everett Sun 18 January 2026
- Algebra in Algorithmic Coding Theory Madhu Sudan Fri 19 December 2025
- Toward P = NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model Darren J. Edwards Fri 19 December 2025
- mathrmTIME[t]subseteq mathrmSPACE[O(sqrtt)] via Tree Height Compression Logan Nye Mon 17 November 2025
- Polynomial-time Tractable Problems over the p-adic Numbers Arno Fehm Manuel Bodirsky Fri 25 April 2025
- Dichotomy for orderings Gábor Kun Jaroslav Nešetřil Fri 25 April 2025
- Reachability in Geometrically d-Dimensional VASS Yuxi Fu Yangluo Zheng Qizhe Yang Fri 25 April 2025
- Vanishing of Schubert coefficients is in sf AMąp sf coAM assuming the GRH Igor Pak Colleen Robichaux Fri 11 April 2025
- Polynomial-Time PIT from (Almost) Necessary Assumptions Robert Andrews Deepanshu Kush Roei Tell Fri 11 April 2025
- The Probability Spaces of QuickSort George Nadareishvili Jonas Oberhauser Wolfgang J. Paul Fri 11 April 2025
- mathsfP-completeness of Graph Local Complementation Pablo Concha-Vega Sat 05 April 2025
- Simple general magnification of circuit lower bounds Albert Atserias Moritz Muller Sat 05 April 2025
- Disjunctive Complexity Nikita Ivanov Alexander Rubtsov Michael Vyalyi Sat 05 April 2025
- Integer multiplication is at least as hard as matrix transposition David Harvey Joris van der Hoeven Sat 05 April 2025
- Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals Abhibhav Garg Rafael Oliveira Nitin Saxena Sat 05 April 2025
- Upper and Lower Bounds for the Linear Ordering Principle Edward A. Hirsch Ilya Volkovich Sat 05 April 2025
- Continuous models of computation: from computability to complexity Amaury Pouly Mon 13 November 2023
- Learning from positive and negative examples: New proof for binary alphabets Jonas Lingg Mateus de Oliveira Oliveira Petra Wolf Wed 04 October 2023
- Context-Bounded Verification of Context-Free Specifications Pascal Baumann Moses Ganardi Rupak Majumdar Ramanathan S. Thinniyam Georg Zetzsche Tue 17 January 2023
- Complexity Results on Register Context-Free Grammars and Related Formalisms Ryoma Senda Yoshiaki Takata Hiroyuki Seki Mon 09 May 2022
- Context-Bounded Verification of Thread Pools Pascal Baumann Rupak Majumdar Ramanathan S. Thinniyam Georg Zetzsche Mon 17 January 2022
- Computational complexity of solving polynomial differential equations over unbounded domains Amaury Pouly Daniel S. Graça Wed 17 February 2021
- One-Clock Priced Timed Games Are PSPACE-Hard John Fearnley Rasmus Ibsen-Jensen Rahul Savani Sat 04 July 2020
- The Complexity of Reachability in Affine Vector Addition Systems with States Michael Blondin Mikhail Raskin Sat 04 July 2020
- On path equivalence of nondeterministic finite automata Wen-Guey Tzeng Fri 07 February 2020
- Complexity of weak acceptance conditions in tree automata Jakub Neumann Andrzej Szepietowski Igor Walukiewicz Fri 07 February 2020
- Fooling Turing machines with sublogarithmic space: a note on `For completeness, sublogarithmic space is no space' by M. Agrawal Andrzej Szepietowski Fri 07 February 2020
- For completeness, sublogarithmic space is no space Manindra Agrawal Fri 07 February 2020
- Cosmological Lower Bound on the Circuit Complexity of a Small Problem in Logic Larry Stockmeyer Albert R. Meyer Wed 22 January 2020
- Fixed Points, Nash Equilibria, and the Existential Theory of the Reals Marcus Schaefer Daniel żTefankoviăż Wed 14 August 2019
- On the Shortest Path Game Andreas Darmann Ulrich Pferschy Joachim Schauer Tue 26 March 2019
- BPA bisimilarity is EXPTIME-hard Stefan Kiefer Tue 12 February 2019
- Real addition and the polynomial hierarchy Eduardo D. Sontag Mon 18 December 2017
- The Complexity of Membership Problems for Circuits over Sets of Integers Stephen Travers Tue 27 January 2015
- Reachability on Prefix-recognizable Graphs Stefan Gøller Thu 29 May 2014
- On the Approximability of Trade-offs and Optimal Access of Web Sources C. H. Papadimitriou M. Yannakakis Mon 14 April 2014
- On the Complexity of a Problem on Monadic String Rewriting Systems Ferucio Laurenţiu Ţiplea Erkki Makinen Wed 19 February 2014
- Deciding the winner in parity games is in UPąpco-UP Marcin Jurdziński Sun 16 February 2014
- Stochastic limit-average games are in EXPTIME Krishnendu Chatterjee Rupak Majumdar ThomasA. Henzinger Mon 13 January 2014
- Efficient Minimization of Deterministic Weak omega-automata Christof Løding Thu 12 December 2013
- The Post correspondence problem over a unary alphabet P. Rudnicki G.J. Woeginger Sat 05 October 2013
- Relating word and tree automata O. Kupferman S. Safra M. Y. Vardi Fri 12 July 2013
- A finite set of functions with an EXPTIME-complete composition problem Marcin Kozik Thu 13 June 2013
Library Size: 13G (58 entries),
Last Updated: Apr 04, 2026, 18:14:59,
Build Time: N/A
