Arnaud Durand

According to our database, Arnaud Durand authored at least 49 papers between 1996 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

A Characterization of Functions over the Integers Computable in Polynomial Time Using Discrete Ordinary Differential Equations.

Olivier Bournez, Arnaud Durand

Comput. Complex., December, 2023

2022

Tractability Frontier of Data Complexity in Team Semantics.

Arnaud Durand, Juha Kontinen, Nicolas de Rugy-Altherre, Jouko Väänänen

ACM Trans. Comput. Log., 2022

Enumerating Answers to First-Order Queries over Databases of Low Degree.

Arnaud Durand, Nicole Schweikardt, Luc Segoufin

Log. Methods Comput. Sci., 2022

A characterization of functions over the integers computable in polynomial time using discrete differential equations.

Olivier Bournez, Arnaud Durand

CoRR, 2022

Modular SAT-based techniques for reasoning tasks in team semantics.

Arnaud Durand, Juha Kontinen, Jouko Väänänen

CoRR, 2022

Enumeration Classes Defined by Circuits.

Nadia Creignou, Arnaud Durand, Heribert Vollmer

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

2021

Descriptive complexity of #P functions: A new perspective.

Arnaud Durand, Anselm Haak, Juha Kontinen, Heribert Vollmer

J. Comput. Syst. Sci., 2021

2020

Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration.

Arnaud Durand

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

2019

Recursion Schemes, Discrete Differential Equations and Characterization of Polynomial Time Computations.

Olivier Bournez, Arnaud Durand

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

Recursion schemes, discrete differential equations and characterization of polynomial time computation.

Olivier Bournez, Arnaud Durand, Sabrina Ouazzani

CoRR, 2018

Approximation and dependence via multiteam semantics.

Arnaud Durand, Miika Hannula, Juha Kontinen, Arne Meier, Jonni Virtema

Ann. Math. Artif. Intell., 2018

Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth.

Arnaud Durand, Anselm Haak, Heribert Vollmer

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Probabilistic Team Semantics.

Arnaud Durand, Miika Hannula, Juha Kontinen, Arne Meier, Jonni Virtema

Proceedings of the Foundations of Information and Knowledge Systems, 2018

2017

Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth.

Arnaud Durand, Anselm Haak, Heribert Vollmer

CoRR, 2017

2016

The Arithmetic Complexity of Tensor Contraction.

Florent Capelli, Arnaud Durand, Stefan Mengel

Theory Comput. Syst., 2016

Homomorphism Polynomials Complete for VP.

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

Chic. J. Theor. Comput. Sci., 2016

Descriptive Complexity of #AC⁰ Functions.

Arnaud Durand, Anselm Haak, Juha Kontinen, Heribert Vollmer

Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

Expressivity and Complexity of Dependence Logic.

Arnaud Durand, Juha Kontinen, Heribert Vollmer

Proceedings of the Dependence Logic, Theory and Applications, 2016

2015

Structural Tractability of Counting of Solutions to Conjunctive Queries.

Arnaud Durand, Stefan Mengel

Theory Comput. Syst., 2015

Dependence Logic with a Majority Quantifier.

Arnaud Durand, Johannes Ebbing, Juha Kontinen, Heribert Vollmer

J. Log. Lang. Inf., 2015

2014

The complexity of weighted counting for acyclic conjunctive queries.

Arnaud Durand, Stefan Mengel

J. Comput. Syst. Sci., 2014

Hypergraph Acyclicity and Propositional Model Counting.

Florent Capelli, Arnaud Durand, Stefan Mengel

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2014, 2014

2013

The arithmetic complexity of tensor contractions.

Florent Capelli, Arnaud Durand, Stefan Mengel

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012

Hierarchies in Dependence Logic.

Arnaud Durand, Juha Kontinen

ACM Trans. Comput. Log., 2012

Trichotomies in the Complexity of Minimal Inference.

Arnaud Durand, Miki Hermann, Gustav Nordh

Theory Comput. Syst., 2012

Fifty years of the spectrum problem: survey and new results.

Arnaud Durand, Neil D. Jones, Johann A. Makowsky, Malika More

Bull. Symb. Log., 2012

2011

Complexity issues for the sandwich homogeneous set problem.

Arnaud Durand, Michel Habib

Discret. Appl. Math., 2011

On Polynomials Defined by Acyclic Conjunctive Queries and Weighted Counting Problems

Arnaud Durand, Stefan Mengel

CoRR, 2011

Enumeration Complexity of Logical Query Problems with Second-order Variables.

Arnaud Durand, Yann Strozecki

Proceedings of the Computer Science Logic, 2011

2010

Efficient Enumeration for Conjunctive Queries over X-underbar Structures.

Guillaume Bagan, Arnaud Durand, Emmanuel Filiot, Olivier Gauwin

Proceedings of the Computer Science Logic, 24th International Workshop, 2010

2009

Trichotomy in the Complexity of Minimal Inference.

Arnaud Durand, Miki Hermann, Gustav Nordh

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

2008

Computing the jth solution of a first-order query.

Guillaume Bagan, Arnaud Durand, Etienne Grandjean, Frédéric Olive

RAIRO Theor. Informatics Appl., 2008

On the counting complexity of propositional circumscription.

Arnaud Durand, Miki Hermann

Inf. Process. Lett., 2008

2007

First-order queries on structures of bounded degree are computable with constant delay.

Arnaud Durand, Etienne Grandjean

ACM Trans. Comput. Log., 2007

A simple proof of the polylog counting ability of first-order logic: guest column.

Arnaud Durand, Clemens Lautemann, Malika More

SIGACT News, 2007

On Acyclic Conjunctive Queries and Constant Delay Enumeration.

Guillaume Bagan, Arnaud Durand, Etienne Grandjean

Proceedings of the Computer Science Logic, 21st International Workshop, 2007

2006

The Expressive Power of Bijections over Weakly Arithmetized Structures.

Étienne Ailloud, Arnaud Durand

Theory Comput. Syst., 2006

The complexity of acyclic conjunctive queries revisited

Arnaud Durand, Etienne Grandjean

CoRR, 2006

Counting Results in Weak Formalisms.

Arnaud Durand, Clemens Lautemann, Malika More

Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

First-Order Queries over One Unary Function.

Arnaud Durand, Frédéric Olive

Proceedings of the Computer Science Logic, 20th International Workshop, 2006

2005

Subtractive reductions and complete problems for counting complexity classes.

Arnaud Durand, Miki Hermann, Phokion G. Kolaitis

Theor. Comput. Sci., 2005

2003

The Inference Problem for Propositional Circumscription of Affine Formulas Is coNP-Complete.

Arnaud Durand, Miki Hermann

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

2002

On the complexity of recognizing the Hilbert basis of a linear diophantine system.

Arnaud Durand, Miki Hermann, Laurent Juban

Theor. Comput. Sci., 2002

Nonerasing, Counting, and Majority over the Linear Time Hierarchy.

Arnaud Durand, Malika More

Inf. Comput., 2002

Linear Time and the Power of One First-Order Universal Quantifier.

Arnaud Durand

Inf. Comput., 2002

1998

Subclasses of Binary NP.

Arnaud Durand, Clemens Lautemann, Thomas Schwentick

J. Log. Comput., 1998

Modeling Cache Coherence Protocol - A Case Study with FLASH.

Arnaud Durand

Proceedings of the Fifth International Workshop on Abstract State Machines, 1998

1997

Spectra with Only Unary Function Symbols.

Arnaud Durand, Ronald Fagin, Bernd Loescher

Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996

First-Order Spectra with one Binary Predicate.

Arnaud Durand, Solomampionona Ranaivoson

Theor. Comput. Sci., 1996