bibliographer - Computer Science - Computational Complexity

Metric Dimension and Geodetic Set Parameterized by Vertex Cover Florent Foucaud Esther Galby Liana Khazaliya Shaohua Li Fionn Mc Inerney Roohani Sharma Prafullkumar Tale Sat 05 April 2025
Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover Florent Foucaud Esther Galby Liana Khazaliya Shaohua Li Fionn Mc Inerney Roohani Sharma Prafullkumar Tale Sat 05 April 2025
Computational Complexity of Polynomial Subalgebras Leonie Kayser Fri 14 March 2025
Symmetric Algebraic Circuits and Homomorphism Polynomials Anuj Dawar Benedikt Pago Tim Seppelt Fri 14 March 2025
On the Complexity of the Conditional Independence Implication Problem With Bounded Cardinalities Michał Makowski Wed 12 March 2025
Simulating Time With Square-Root Space R. Ryan Williams Sun 09 March 2025
Succinct Perfect Zero-knowledge for MIP* Honghao Fu Xingjian Zhang Sun 09 March 2025
Classification and degenerations of small minimal border rank tensors via modules Jakub Jagiełła Joachim Jelisiejew Sun 09 March 2025
Reduction of the group isomorphism problem to the group automorphism problem Saveliy V. Skresanov Sun 09 March 2025
The Structural Complexity of Matrix-Vector Multiplication Emile Anand Jan van den Brand Rose McCarty Sun 09 March 2025
Vanishing of Schubert Coefficients Igor Pak Colleen Robichaux Tue 18 February 2025
New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality Tomáš Nagy Michael Pinsker Michał Wrona Tue 18 February 2025
An efficient uniqueness theorem for overcomplete tensor decomposition Pascal Koiran Fri 14 February 2025
Algebraic metacomplexity and representation theory Maxim van den Berg Pranjal Dutta Fulvio Gesmundo Christian Ikenmeyer Vladimir Lysikov Fri 14 February 2025
Fair Vertex Problems Parameterized by Cluster Vertex Deletion Tomáš Masařík Jędrzej Olkowski Anna Zych-Pawlewicz Fri 14 February 2025
Some structural complexity results for existsmathbb R Klaus Meer Adrian Wurm Fri 14 February 2025
Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes David Gamarnik Wed 29 January 2025
Positive Moments Forever: Undecidable and Decidable Cases Gemma De les Coves Joshua Graf Andreas Klingler Tim Netzer Tue 21 January 2025
Transformers in Uniform TC^0 David Chiang Tue 07 January 2025
Super Unique Tarski is in UEOPL John Fearnley Rahul Savani Mon 25 November 2024
Matrix-by-matrix multiplication algorithm with O(N^2log2N) computational complexity for variable precision arithmetic Maciej Paszyński Sat 02 November 2024
Improving the Leading Constant of Matrix Multiplication Josh Alman Hantao Yu Sat 02 November 2024
Solving Polynomial Equations Over Finite Fields Holger Dell Anselm Haak Melvin Kallmayer Leo Wennmann Sat 02 November 2024
A LOCAL View of the Polynomial Hierarchy Fabian Reiter Sat 26 October 2024
A parametric version of the Hilbert Nullstellensatz Rida Ait El Manssour Nikhil Balaji Klara Nosan Mahsa Shirmohammadi James Worrell Sat 26 October 2024
C2k+1-coloring of bounded-diameter graphs Marta Piecyk Sat 26 October 2024
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds Karl Bringmann Allan Grønlund Marvin Kunnemann Kasper Green Larsen Sat 12 October 2024
The Complexity of Symmetric Bimatrix Games with Common Payoffs Abheek Ghosh Alexandros Hollender Sat 12 October 2024
Symmetric powers: structure, smoothability, and applications Cosimo Flavi Joachim Jelisiejew Mateusz Michałek Wed 14 August 2024
The Subspace Flatness Conjecture and Faster Integer Programming Victor Reis Thomas Rothvoss Thu 01 August 2024
Satisfiability of commutative vs. non-commutative CSPs Andrei A. Bulatov Stanislav Živný Thu 01 August 2024
Determination Problems for Orbit Closures and Matrix Groups Rida Ait El Manssour George Kenison Mahsa Shirmohammadi James Worrell Thu 01 August 2024
Specification and Automatic Verification of Computational Reductions Julien Grange Fabian Vehlken Nils Vortmeier Thomas Zeume Thu 01 August 2024
The Existential Theory of the Reals as a Complexity Class: A Compendium Marcus Schaefer Jean Cardinal Tillmann Miltzow Wed 31 July 2024
The Computational Complexity of Factored Graphs Shreya Gupta Boyang Huang Russell Impagliazzo Stanley Woo Christopher Ye Wed 31 July 2024
Simple Linear Loops: Algebraic Invariants and Applications Rida Ait El Manssour George Kenison Mahsa Shirmohammadi Anton Varonka Wed 24 July 2024
Explicit Commutative ROABPs from Partial Derivatives Vishwas Bhargava Anamay Tengse Wed 24 July 2024
Positivity of the symmetric group characters is as hard as the polynomial time hierarchy Christian Ikenmeyer Igor Pak Greta Panova Mon 15 July 2024
Weighted basic parallel processes and combinatorial enumeration Lorenzo Clemente Wed 10 July 2024
On the Number of Quantifiers Needed to Define Boolean Functions Marco Carmosino Ronald Fagin Neil Immerman Phokion Kolaitis Jonathan Lenchner Rik Sengupta Thu 04 July 2024
Computable one-way functions on the reals George Barmpalias Xiaoyan Zhang Thu 27 June 2024
Completeness classes in algebraic complexity theory Peter Burgisser Sun 23 June 2024
Treewidth Inapproximability and Tight ETH Lower Bound Édouard Bonnet Sun 23 June 2024
Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture Peter Burgisser Mahmut Levent Doğan Visu Makam Michael Walter Avi Wigderson Tue 28 May 2024
The Existential Theory of the Reals with Summation Operators Markus Blaser Julian Dørfler Maciej Liskiewicz Benito van der Zander Thu 09 May 2024
Maximizing Network Phylogenetic Diversity Leo van Iersel Mark Jones Jannik Schestag Celine Scornavacca Mathias Weller Wed 08 May 2024
A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results Vikraman Arvind Pushkar S Joglekar Tue 30 April 2024
The Acrobatics of BQP Scott Aaronson DeVon Ingram William Kretschmer Tue 30 April 2024
Functional Closure Properties of Finite mathbbN-weighted Automata Julian Dørfler Christian Ikenmeyer Wed 24 April 2024
Solving promise equations over monoids and groups Alberto Larrauri Stanislav Živný Wed 24 April 2024
Existential Second-Order Logic Over Graphs: A Complete Complexity-Theoretic Classification Till Tantau Sun 21 April 2024
Pi2^P vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem Dmitriy Zhuk Thu 18 April 2024
On the complexity of Chow and Hurwitz forms Mahmut Levent Doğan Alperen Ali Ergur Elias Tsigaridas Thu 18 April 2024
The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture Ambroise Baril Miguel Couceiro Victor Lagerkvist Thu 18 April 2024
Trading Determinism for Noncommutativity in Edmonds' Problem V. Arvind Abhranil Chatterjee Partha Mukhopadhyay Fri 12 April 2024
Local Correction of Linear Functions over the Boolean Cube Prashanth Amireddy Amik Raj Behera Manaswi Paraashar Srikanth Srinivasan Madhu Sudan Sat 06 April 2024
Complexity problems in enumerative combinatorics Igor Pak Fri 22 March 2024
PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements Scott Aaronson Sabee Grewal Vishnu Iyer Simon C. Marshall Ronak Ramachandran Wed 13 March 2024
PosSLP and Sum of Squares Markus Blaser Julian Dørfler Gorav Jindal Mon 04 March 2024
On the Counting Complexity of the Skolem Problem Gorav Jindal Joel Ouaknine Mon 04 March 2024
Polynomial Identity Testing via Evaluation of Rational Functions Ivan Hu Dieter van Melkebeek Andrew Morgan Thu 29 February 2024
Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras Libor Barto Zarathustra Brady Andrei Bulatov Marcin Kozik Dmitriy Zhuk Thu 29 February 2024
Decidability and k-Regular Sequences Daniel Krenn Jeffrey Shallit Wed 21 February 2024
Hausdorff Reductions and the Exponential Hierarchies Enrico Malizia Fri 02 February 2024
What Juris Hartmanis taught me about Reductions Neil Immerman Tue 30 January 2024
Isomorphism Testing of Rooted Trees in Linear Time Anna Lindeberg Fri 19 January 2024
Low-Rank Tensor Decomposition over Finite Fields Jason Yang Fri 19 January 2024
Grothendieck inequalities characterize converses to the polynomial method Jop Briet Francisco Escudero Gutiérrez Sander Gribling Sun 07 January 2024
Weighted Automata and Logics Meet Computational Complexity Peter Kostolányi Fri 22 December 2023
A faster FPRAS for NFA Kuldeep S. Meel Sourav Chakraborty Umang Mathur Fri 22 December 2023
Algebraic Complexity Classes Meena Mahajan Mon 27 November 2023
Enumerating Tarski fixed points on lattices of binary relations Julian Muller Fri 24 November 2023
NP-hard problems are not in BQP Reiner Czerwinski Thu 16 November 2023
A Survey on Analog Models of Computation Olivier Bournez Amaury Pouly Mon 06 November 2023
Word-Mappings of level 3 G. Sénizergues Thu 12 October 2023
On the Length of Strongly Monotone Descending Chains over mathbbN^d Sylvain Schmitz Lia Schutze Sat 07 October 2023
Monotone Classes Beyond VNP Prerona Chatterjee Kshitij Gajjar Anamay Tengse Sat 07 October 2023
The Recursive Arrival Problem Thomas Webster Thu 05 October 2023
Learning from Positive and Negative Examples: New Proof for Binary Alphabets Jonas Lingg Mateus de Oliveira Oliveira Petra Wolf Wed 04 October 2023
Progress on Polynomial Identity Testing - II Nitin Saxena Mon 02 October 2023
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time V. Arvind Abhranil Chatterjee Partha Mukhopadhyay Thu 28 September 2023
A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem Zhengyu Li Curtis Bright Vijay Ganesh Thu 21 September 2023
On Annihilators of Explicit Polynomial Maps Prerona Chatterjee Anamay Tengse Fri 15 September 2023
On Lifting Lower Bounds for Noncommutative Circuits using Automata V. Arvind Abhranil Chatterjee Sat 26 August 2023
Simulation of Turing machines with analytic discrete ODEs: FPTIME and FPSPACE over the reals characterised with discrete ordinary differential equations Manon Blanc Olivier Bournez Tue 25 July 2023
New Bounds for Matrix Multiplication: from Alpha to Omega Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu Renfei Zhou Wed 19 July 2023
On the Hardness of PosSLP Peter Burgisser Gorav Jindal Wed 19 July 2023
Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond Jan Dreier Daniel Mock Peter Rossmanith Fri 14 July 2023
Polynomial Identity Testing and the Ideal Proof System: PIT is in NP if and only if IPS can be p-simulated by a Cook-Reckhow proof system Joshua A. Grochow Tue 11 July 2023
Fine-grained reductions around CFL-reachability Aleksandra Istomina Semyon Grigorev Ekaterina Shemetova Tue 11 July 2023
Logarithmic Weisfeiler--Leman Identifies All Graphs of Bounded Rank Width Michael Levet Nicholas Sieger Tue 11 July 2023
Computational Complexity in Algebraic Combinatorics Greta Panova Tue 11 July 2023
BQP = PSPACE Shibdas Roy Thu 06 July 2023
Weighted First Order Model Counting with Directed Acyclic Graph Axioms Sagar Malhotra Luciano Serafini Thu 06 July 2023
Symmetric Weighted First-Order Model Counting Paul Beame Guy Van den Broeck Eric Gribkoff Dan Suciu Thu 06 July 2023
Pizza Sharing is PPA-hard Argyrios Deligkas John Fearnley Themistoklis Melissourgos Thu 22 June 2023
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Grøbner Bases Massimo Lauria Jakob Nordstrøm Mon 05 June 2023
Making textsfIP=textsfPSPACE Practical: Efficient Interactive Protocols for BDD Algorithms Eszter Couillard Philipp Czerner Javier Esparza Rupak Majumdar Wed 24 May 2023
The Complexity of Diagonalization Nikhil Srivastava Wed 24 May 2023
Principal-Agent Boolean Games David Hyland Julian Gutierrez Michael Wooldridge Wed 24 May 2023
The Noncommutative Edmonds' Problem Re-visited Abhranil Chatterjee Partha Mukhopadhyay Wed 24 May 2023
Testing Isomorphism of Graphs in Polynomial Time Rui Xue Wed 24 May 2023
DNN Verification, Reachability, and the Exponential Function Problem Omri Isac Yoni Zohar Clark Barrett Guy Katz Sat 13 May 2023
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality Marvin Kunnemann Filip Mazowiecki Lia Schutze Henry Sinclair-Banks Karol Węgrzycki Fri 05 May 2023
A Critique of Czerwinski's ''Separation of rm PSPACE and rm EXP'' Ian Clingerman Quan Luu Fri 05 May 2023
Simulating Logspace-Recursion with Logarithmic Quantifier Depth Steffen van Bergerem Martin Grohe Sandra Kiefer Luca Oeljeklaus Fri 28 April 2023
Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF Johannes K. Fichte Robert Ganian Markus Hecher Friedrich Slivovsky Sebastian Ordyniak Fri 28 April 2023
Multiplicity Problems on Algebraic Series and Context-Free Grammars Nikhil Balaji Lorenzo Clemente Klara Nosan Mahsa Shirmohammadi James Worrell Fri 28 April 2023
The Identity Problem in the special affine group of mathbbZ^2 Ruiwen Dong Fri 28 April 2023
Boolean symmetric vs. functional PCSP dichotomy Tamio-Vesa Nakajima Stanislav Živný Fri 28 April 2023
The Descriptive Complexity of Graph Neural Networks Martin Grohe Fri 28 April 2023
Verifying linear temporal specifications of constant-rate multi-mode systems Michael Blondin Philip Offtermatt Alex Sansfaçon-Buchanan Fri 28 April 2023
FIXP-membership via Convex Optimization: Games, Cakes, and Markets Aris Filos-Ratsikas Kristoffer Arnsfelt Hansen Kasper Høgh Alexandros Hollender Fri 28 April 2023
On the Order of Power Series and the Sum of Square Roots Problem Louis Gaillard Gorav Jindal Fri 28 April 2023
The Mathematics of Ltextbackslash'aszltextbackslash'o Lovtextbackslash'asz Martin Grøtschel Jaroslav Nešetřil Wed 08 March 2023
The mathsfAC^0-Complexity Of Visibly Pushdown Languages Stefan Gøller Nathan Grosshans Thu 02 March 2023
Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits Benedikt Pago Mon 20 February 2023
Measuring robustness of dynamical systems. Relating time and space to length and precision Manon Blanc Olivier Bournez Tue 07 February 2023
Quasi-optimal multiplication of linear differential operators Alexandre Benoit Alin Bostan Joris van der Hoeven Thu 02 February 2023
stateQIP = statePSPACE Tony Metger Henry Yuen Fri 27 January 2023
The Complexity of Verifying Loop-Free Programs as Differentially Private Marco Gaboardi Kobbi Nissim David Purser Sat 07 January 2023
On the Complexity of Problems on Tree-structured Graphs Hans L. Bodlaender Carla Groenland Hugo Jacob Marcin Pilipczuk Michal Pilipczuk Tue 29 November 2022
An invitation to the promise constraint satisfaction problem Andrei Krokhin Jakub Opršal Sat 26 November 2022
Border complexity via elementary symmetric polynomials Pranjal Dutta Fulvio Gesmundo Christian Ikenmeyer Gorav Jindal Vladimir Lysikov Tue 15 November 2022
Google's 2019 ``Quantum Supremacy'' Claims: Data, Documentation, and Discussion Gil Kalai Yosef Rinott Tomer Shoham Sat 29 October 2022
Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs Richard Mayr Eric Munday Sat 29 October 2022
Beyond the Existential Theory of the Reals Marcus Schaefer Daniel Stefankovic Sat 29 October 2022
VPSPACE and a Transfer Theorem over the Reals Pascal Koiran Sylvain Perifel Mon 24 October 2022
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width Robert Ganian Thekla Hamm Viktoriia Korchemna Karolina Okrasa Kirill Simonov Mon 17 October 2022
A characterization of functions over the integers computable in polynomial time using discrete differential equations Olivier Bournez Arnaud Durand Mon 03 October 2022
Polynomial time computable functions over the reals characterized using discrete ordinary differential equations Manon Blanc Olivier Bournez Mon 03 October 2022
A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations Manon Blanc Olivier Bournez Mon 03 October 2022
The Hairy Ball Problem is PPAD-Complete Paul W. Goldberg Alexandros Hollender Fri 16 September 2022
Subset Sum in O(n^11łog(n)) Rion Tolchin Fri 16 September 2022
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field V. Arvind Abhranil Chatterjee Utsab Ghosal Partha Mukhopadhyay C. Ramya Fri 16 September 2022
What is a combinatorial interpretation Igor Pak Fri 16 September 2022
How Much Structure Is Needed for Huge Quantum Speedups Scott Aaronson Fri 16 September 2022
On Power Set Axiom Leonid A. Levin Fri 16 September 2022
Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set Julian D'Costa Engel Lefaucheux Eike Neumann Joel Ouaknine James Worrell Mon 29 August 2022
Alternating Automatic Register Machines Ziyuan Gao Sanjay Jain Zeyong Li Ammar Fathin Sabili Frank Stephan Wed 03 August 2022
On the Computation of the Zariski Closure of Finitely Generated Groups of Matrices Klara Nosan Amaury Pouly Sylvain Schmitz Mahsa Shirmohammadi James Worrell Sat 16 July 2022
On the Number of Quantifiers as a Complexity Measure Ronald Fagin Jonathan Lenchner Nikhil Vyas Ryan Williams Wed 13 July 2022
Counting of Teams in First-Order Team Logics Anselm Haak Juha Kontinen Fabian Muller Heribert Vollmer Fan Yang Fri 01 July 2022
A Formula for the Determinant Nicholas Pippenger Thu 02 June 2022
Further Collapses in TFNP Mika Gøøs Alexandros Hollender Siddhartha Jain Gilbert Maystre William Pires Robert Robere Ran Tao Thu 26 May 2022
Monomials in arithmetic circuits: Complete problems in the counting hierarchy Hervé Fournier Guillaume Malod Stefan Mengel Tue 22 February 2022
Identity testing for radical expressions Nikhil Balaji Klara Nosan Mahsa Shirmohammadi James Worrell Thu 17 February 2022
Improved Upper Bounds for Finding Tarski Fixed Points Xi Chen Yuhao Li Thu 17 February 2022
A quantum complexity approach to the Kirchberg Embedding Problem Isaac Goldbring Bradd Hart Sun 24 October 2021
MIP*=RE Zhengfeng Ji Anand Natarajan Thomas Vidick John Wright Henry Yuen Wed 29 September 2021
The Connes Embedding Problem: A guided tour Isaac Goldbring Tue 28 September 2021
A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings Gustav Grabolle Wed 22 September 2021
Lower Bounds on Unambiguous Automata Complementation and Separation via Communication Complexity Mika Gøøs Stefan Kiefer Wed 22 September 2021
Linear equations for unordered data vectors Piotr Hofman Jakub Różycki Wed 08 September 2021
Optimal Fine-grained Hardness of Approximation of Linear Equations Mitali Bafna Nikhil Vyas Fri 25 June 2021
Towards a more efficient approach for the satisfiability of two-variable logic Ting-Wei Lin Chia-Hsuan Lu Tony Tan Fri 30 April 2021
Resolution with Symmetry Rule applied to Linear Equations Pascal Schweitzer Constantin Seebach Sun 14 February 2021
Exploring Rulial Space: The Case of Turing Machines Stephen Wolfram Sun 14 February 2021
Yet another argument in favour of NP=CoNP Edward Hermann Haeusler Wed 13 January 2021
On P Versus NP Lev Gordeev Tue 05 January 2021
Subquadratic-Time Algorithms for Normal Bases Mark Giesbrecht Armin Jamshidpey Éric Schost Sun 27 December 2020
Improved Maximally Recoverable LRCs using Skew Polynomials Sivakanth Gopi Venkatesan Guruswami Wed 16 December 2020
On proof theory in computer science L. Gordeev E. H. Haeusler Sun 13 December 2020
Proof Compression and NP Versus PSPACE II: Addendum L. Gordeev E. H. Hermann Thu 19 November 2020
On the Complexity of CSP-based Ideal Membership Problems Andrei A. Bulatov Akbar Rafiey Thu 12 November 2020
Verification of Flat FIFO Systems Alain Finkel M. Praveen Sun 25 October 2020
A Refined Laser Method and Faster Matrix Multiplication Josh Alman Virginia Vassilevska Williams Thu 15 October 2020
The Complexity of the Homomorphism Problem for Boolean structures Libor Barto William DeMeo Antoine Mottet Thu 15 October 2020
Reachability in Dynamical Systems with Rounding Christel Baier Florian Funke Simon Jantsch Toghrul Karimov Engel Lefaucheux Joel Ouaknine Amaury Pouly David Purser Markus A. Whiteland Wed 07 October 2020
The Argument against Quantum Computers, the Quantum Laws of Nature, and Google's Supremacy Claims Gil Kalai Thu 13 August 2020
The Amazing Power of Randomness: NP=RP András Faragó Tue 04 August 2020
Cyclotomic Identity Testing and Applications Nikhil Balaji Sylvain Perifel Mahsa Shirmohammadi James Worrell Tue 28 July 2020
Evolution toward a Nash equilibrium Ioannis Avramopoulos Thu 23 July 2020
On the decidability and complexity of Metric Temporal Logic over finite words Joel Ouaknine James Worrell Mon 06 July 2020
Fundamentals of Computing Leonid A. Levin Sat 04 July 2020
Political Advertising Dataset: the use case of the Polish 2020 Presidential Elections Łukasz Augustyniak Krzysztof Rajda Tomasz Kajdanowicz Michał Bernaczyk Mon 22 June 2020
On the Skolem Problem and Prime Powers George Kenison Richard Lipton Joel Ouaknine James Worrell Mon 22 June 2020
Existential Theory of the Reals Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games Kristoffer Arnsfelt Hansen Steffan Christ Sølvsten Mon 22 June 2020
Polynomial time deterministic identity testingalgorithm for Sigma^[3]PiSigmaPi^[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials Shir Peleg Amir Shpilka Wed 17 June 2020
Special-case Algorithms for Blackbox Radical Membership, Nullstellensatz and Transcendence Degree Abhibhav Garg Nitin Saxena Wed 17 June 2020
Testing Membership for Timed Automata Richard Lassaigne Michel de Rougemont Fri 29 May 2020
The Iteration Number of Colour Refinement Sandra Kiefer Brendan D. McKay Thu 21 May 2020
Synchronization of Deterministic Visibly Push-Down Automata Henning Fernau Petra Wolf Wed 13 May 2020
Synchronizing Deterministic Push-Down Automata Can Be Really Hard Henning Fernau Petra Wolf Tomoyuki Yamakami Wed 13 May 2020
Insignificant Choice Polynomial Time Klaus-Dieter Schewe Wed 13 May 2020
Graph isomorphism in quasipolynomial time parameterized by treewidth Daniel Wiebking Sat 25 April 2020
Decision Problems in Information Theory Mahmoud Abo Khamis Phokion G. Kolaitis Hung Q. Ngo Dan Suciu Sat 25 April 2020
The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem Zachary Remscrim Sun 19 April 2020
Descriptive complexity of real computation and probabilistic independence logic Miika Hannula Juha Kontinen Jan Van den Bussche Jonni Virtema Sun 19 April 2020
On the complexity of zero gap MIP* Hamoon Mousavi Seyed Sajjad Nezhadi Henry Yuen Tue 03 March 2020
Hyperbolic Minesweeper is in P Eryk Kopczyński Tue 03 March 2020
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity Benjamin Rossman Thu 13 February 2020
Complexity Theory, Game Theory, and Economics: The Barbados Lectures Tim Roughgarden Wed 12 February 2020
Relativization of Gurevich's Conjectures Anatole Dahan Anuj Dawar Wed 12 February 2020
On Affine Reachability Problems Stefan Jaax Stefan Kiefer Thu 30 January 2020
Elements of Scheduling Jan Karel Lenstra David B. Shmoys Mon 27 January 2020
The Computational Complexity of Angry Birds Matthew Stephenson Jochen Renz Xiaoyu Ge Wed 01 January 2020
Lower bounds for the state complexity of probabilistic languages and the language of prime numbers Nathanael Fijalkow Fri 27 December 2019
On the Resolution of the Sensitivity Conjecture Rohan Karthikeyan Siddharth Sinha Vallabh Patil Fri 27 December 2019
Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity Dušan Knop Martin Koutecký Tomáš Masařík Tomáš Toufar Wed 11 December 2019
Complexity Results on Register Pushdown Automata Ryoma Senda Yoshiaki Takata Hiroyuki Seki Thu 24 October 2019
Affine Extensions of Integer Vector Addition Systems with States Michael Blondin Christoph Haase Filip Mazowiecki Mikhail Raskin Mon 14 October 2019
Succinct Population Protocols for Presburger Arithmetic Michael Blondin Javier Esparza Blaise Genest Martin Helfrich Stefan Jaax Fri 11 October 2019
On the variable hierarchy of first-order spectra Eryk Kopczynski Tony Tan Wed 02 October 2019
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria Kousha Etessami Christos Papadimitriou Aviad Rubinstein Mihalis Yannakakis Tue 10 September 2019
The Complexity of Reachability in Affine Vector Addition Systems with States Michael Blondin Mikhail Raskin Tue 10 September 2019
Verification of Flat FIFO Systems Alain Finkel M. Praveen Wed 21 August 2019
Two-variable logic revisited Yanger Ma Tony Tan Wed 21 August 2019
Computing Nested Fixpoints in Quasipolynomial Time Daniel Hausmann Lutz Schrøder Sat 20 July 2019
Equilibria, Fixed Points, and Complexity Classes Mihalis Yannakakis Sat 13 July 2019
On the Relative Succinctness of Sentential Decision Diagrams Beate Bollig Matthias Buttkus Sat 13 July 2019
Algorithms in Real Algebraic Geometry: A Survey Saugata Basu Sat 29 June 2019
On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond Paul C. Bell Igor Potapov Pavel Semukhin Fri 28 June 2019
The Polynomial Hierarchy collapses Valentin Bura Tue 28 May 2019
Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic Sandra Kiefer Pascal Schweitzer Tue 28 May 2019
Modular difference logic is hard Nikolaj Bjørner Andreas Blass Yuri Gurevich Madan Musuvathi Mon 29 April 2019
A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton M. Raskin Fri 15 June 2018

Library Size: 13G (217 entries), Last Updated: Apr 04, 2026, 18:14:59, Build Time: N/A

[show logs] [hide logs]