A. Durand, A. Haak, H. Vollmer.
Model-Theoretic Characterizations of Boolean and Arithmetic Circuit
Classes of Small Depth.
To appear in: 33rd Annual ACM/IEEE Symposium on
Logic in Computer Science, 2018 (LICS'18)
[arxiv version]
A. Durand, M. Hannula, J. Kontinen, A. Meier,
J. Virtema.
Approximation and Dependence via Multiteam Semantics.
Annals of Mathematics and Artificial
Intelligence, 2018.
Conference version in: Foundations of Information and Knowledge Systems - 9th International
Symposium, FoIKS 2016. Springer, LNCS 9616, pp. 271-291, 2016
[arxiv version] [journal version]
A. Durand, J. Kontinen, H. Vollmer.
Dependence Logic: Theory and
Applications. Chapter: Expressivity and Complexity of Dependence Logic
pp. 5-32, Springer, 2016
[arxiv version]
A. Durand, A. Haak, J. Kontinen, H. Vollmer.
Descriptive Complexity of #AC0 Functions.
25th Annual Conference on Computer Science
Logic (CSL 2016), LIPiCS, vol 62, pp. 20:1-20:16, 2016
[arxiv version]
F. Capelli, A. Durand, S. Mengel.
The arithmetic Complexity of Tensor Contraction
Theory of Computing Systems, vol 58(4),
pp. 506-527, 2016
Conference version in: 30th Symposium on Theoretical Aspects of
Computer Science (STACS'13). Leibniz International Proceedings in
Informatics (LIPIcs), vol. 20, pages 365-376, 2013
[arxiv version]
A. Durand, S. Mengel.
Structural Tractability of Counting of Solutions to Conjunctive Queries.
Theory of Computing Systems, vol 57(4),
pp. 1202-1249, 2015.
[arxiv version]
A. Durand,
J. Ebbing,
J. Kontinen,
H. Vollmer.
Dependence Logic with a Majority Quantifier.
Journal of Logic, Language and Information vol
24(3), pp. 289--305, 2015
[arxiv version]
A. Durand,
J. Kontinen,
Nicolas de Rugy-Altherre,
Jouko Väänänen.
Tractability Frontier of Data Complexity in Team Semantics
Sixth International Symposium on Games, Automata, Logics
and Formal Verification, GandALF 2015, EPTCS, vol 193, pp. 73-85,2015.
[arxiv version]
A. Durand, M. Mahajan, G. Malod,
Nicolas de Rugy-Altherre,
Nitin Saurabh
Homomorphism Polynomials Complete for VP
Chicago Journal of Theoretical Computer
Science, vol. 3, pp. 1-25, 2016 (Conference version in FSTTCS 2014)
[pdf]
F. Capelli, A. Durand, S. Mengel.
Hypergraph Acyclicity and Propositional Model Counting
Theory and Applications of Satisfiability
Testing (SAT 2014), Springer LNCS vol 8561, pp. 399-414, 2014
[arxiv version]
A. Durand, N. Schweikardt, L. Segoufin.
Enumerating First-Order Queries over Databases of Low Degree
Proceedings of the 33rd ACM
SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'14), pp. 121-131, 2014
A. Durand, S. Mengel.
The complexity of weighted counting for acyclic
conjunctive queries
Journal of Computer and System Sciences,
vol. 80(1), pp. 277-296, 2014.
A. Durand, S. Mengel.
Structural Tractability of Counting of Solutions to Conjunctive Queries
Joint 2013 ACM EDBT/ICDT Conferences, ICDT '13,
Genoa, Italy, pp. 81-92, 2013
A. Durand, J. Ebbing, J. Kontinen, H. Vollmer.
Dependence logic with a majority quantifier
Foundations of Software Technology and
Theoretical Computer Science (FSTTCS 2011), pages
252-263, Leibniz International Proceedings in Informatics (LIPIcs)
[arxiv version]
A. Durand, Y. Strozecki.
Enumeration Complexity of Logical Query Problems with Second-order Variables
Computer Science Logic (CSL'11) - 25th
International Workshop/20th Annual Conference of the EACSL, pp
189-202, Leibniz International Proceedings in Informatics (LIPIcs)
[pdf]
A. Durand, J. Kontinen.
Hierarchies in Dependence Logic
ACM Transactions on Computational Logic, vol
12(3), 2012
[arxiv version]
A. Durand, N. Jones, J. Makowsky, M. More.
Fifty Years of the Spectrum Problem: Survey and
New Results
Bulletin of Symbolic Logic, vol. 18(4),
505-553, 2012
[pdf]
A. Durand, M. Hermann, G. Nordh.
Trichotomy in the complexity of minimal inference
Theory of Computing Systems, 50(3), pages 446-491. Journal version of the LICS'09 paper
[pdf]
A. Durand, M. Habib.
Complexity Issues for the Homogeneous Set Sandwich
Problem
Discrete Applied Mathematics, 159(7), pages
574-580, 2011
G. Bagan, A. Durand, E. Filiot, O. Gauwin.
Efficient Enumeration for Conjunctive Queries over X-underbar Structures
Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL'10), Lecture Notes in Computer Science, ARCoSS, vol. 6247, pages 80-94. 2010
[pdf]
A. Durand, M. Hermann, G. Nordh.
Trichotomy in the complexity of minimal inference
24th Annual IEEE Symposium on Logic in Computer Science (LICS'2009), pp. 387-396, 2009
[pdf]
G. Bagan, A. Durand, E. Grandjean, F. Olive.
Computing the jth solution of a first-order query.
RAIRO Theor. Inf. Appl. vol. 42, pp. 147-164, 2008
A. Durand, M. Hermann.
On the Counting Complexity of Propositional Circumscription.
Information Processing Letters, 106(4), p. 164-170, 2008
[pdf]
A. Durand, C. Lautemann, M. More.
Counting results in weak formalisms.
ACM Sigact News , Complexity Theory Column 57
G. Bagan, A. Durand, E.Grandjean.
On Acyclic Conjunctive Queries and Constant Delay Enumeration.
Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, LNCS 4646, pages 208-222, 2007
[pdf]
[longer version]
A. Durand, E.Grandjean.
First-order queries on structures of bounded degree are computable
with constant delay.
ACM Transactions on Computational Logic, vol (8)4, 2007.
[pdf]
A. Durand, F. Olive.
First-order queries over one unary function.
Computer Science Logic, 20th
International Workshop, CSL 2006, 15th Annual Conference of the EACSL, LNCS
4207, pages 334-348. Springer, 2006
[pdf]
E. Ailloud, A. Durand.
The expressive power of bijections over weakly arithmetized.
Theory of Computing Systems, 39(2):297-309, 2006.
[pdf]
A. Durand, E. Grandjean.
The complexity of acyclic conjunctive queries revisited.
Technical report, 2005. The version available for download is that of arXiv:cs/0605008v1 (May, 2006).
[pdf]
A. Durand, M. Hermann, P.G. Kolaitis.
Subtractive reductions and complete problems for counting complexity
classes.
Theoretical Computer Science, 340(3):496-513, 2005.
[pdf]
A. Durand, E. Grandjean, F. Olive.
New results on arity vs. number of variables.
Research report 20-2004, LIF, Marseille, France, April 2004.
[pdf]
A. Durand.
Habilitation à diriger des recherches.
Université Paris 12, 2003.
[pdf]
A. Durand, M. Hermann.
The inference problem for propositional circumscription of affine
formulas is coNP-complete.
In H. Alt and M. Habib, editors, 20th Symposium on Theoretical
Aspects of Computer Science (STACS'03), LNCS 2607, pages 451-462. Springer, 2003.
[pdf]
A. Durand.
Binary-NP and the power of one first-order universal quantifier.
Information and Computation, 178(1):12-22, 2002.
[pdf]
A. Durand, M. Hermann, L. Juban.
On the complexity of recognizing the hilbert bases of a linear
diophantine system.
Theoretical Computer Science, 270(1-2):625-642, 2002.
[pdf]
A. Durand, M. More.
Non erasing, counting and majority over the linear hierarchy.
Information and Computation, 174(2):132-142, 2002.
[pdf]
D. Beauquier, T. Crolard, A. Durand, A. Slissenko.
Impossibility of essential real-time garbage collection in the general case.
In CSIT'01, pages 17-20, Yerevan (Armenia), 2001.
A. Durand, M. Hermann, P.G. Kolaitis.
Subtractive reductions and complete problems for counting complexity classes.
In M. Nielsen and B. Rovan, editors, 25th International Symposium on Mathematical Foundations of Computer Science (MFCS'00), LNCS 1893, pages 323-332. Springer, 2000.
A. Durand, M. Hermann, L. Juban.
On the complexity of recognizing the hilbert bases of a linear diophantine system.
In L. Pacholski and M. Kutylowski, editors, 24th International Symposium on Mathematical Foundations of Computer Science (MFCS'99), LNCS 1672, pages 92-102. Springer, 1999.
A. Durand.
Modeling cache coherence protocol - a case study with flash.
In Workshop on Abstract State Machines, pages 111-126. T.U.
Magdeburg, 1998.
A. Durand. R. Fagin, B. Loescher.
Spectra with only unary function symbols.
In M. Nielsen and W. Thomas, editors, Computer Science Logic,
selected paper of CSL'97, LNCS 1414, pages 189-202. Springer, 1998.
Also available as BRICS notes series NS-97-1 and IBM Research Report
RJ 10105.
[pdf]
A. Durand, C. Lautemann, M. More.
Counting results in weak formalisms.
Technical report, S.D.A.D. Université de Caen, 1998.
[pdf]
A. Durand, C. Lautemann, T. Schwentick.
Subclasses of binary NP.
Journal of Logic and Computation, 8(2):189-207, 1998.
[pdf]
A. Durand.
Hiérarchies de définissabilité logique au second ordre.
Thèse de Doctorat. Université de Caen., 1996.
[pdf]
A. Durand, S. Ranaivoson.
First-order spectra with one binary predicate.
Theoretical Computer Science, 160(1-2):305-320, 1996.
A. Durand, S. Ranaivoson.
First-order spectra with one binary predicate.
In J. Tyurin, L. Pacholski, editors, Computer Science Logic,
selected paper of CSL'94, LNCS 933, pages 177-189. Springer, 1995.