BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Arnaud Durand

Arnaud Durand appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Logic in Computer ScienceComputational Complexitymath.CAmath.LOmath.NTmath.PRmath.DSmath.FAArtificial Intelligencemath.COmath.MGmath.STStatistics Theory

Catalog footprint

What is connected

17works
13topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

17 published item(s)

preprint2022arXiv

Modular SAT-based techniques for reasoning tasks in team semantics

We study the complexity of reasoning tasks for logics in team semantics. Our main focus is on the data complexity of model checking but we also derive new results for logically defined counting and enumeration problems. Our approach is based on modular reductions of these problems into the corresponding problems of various classes of Boolean formulas. We illustrate our approach via several new tractability/intractability results.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Descriptive Complexity of $\#\textrm{AC}^0$ Functions

We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC^0 appear as classes of this hierarchy. In this way, we unconditionally place #AC^0 properly in a strict hierarchy of arithmetic classes within #P. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. We argue that our approach is better suited to study arithmetic circuit classes such as #AC^0 which can be descriptively characterized as a class in our framework.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Describability via ubiquity and eutaxy in Diophantine approximation

We present a comprehensive framework for the study of the size and large intersection properties of sets of limsup type that arise naturally in Diophantine approximation and multifractal analysis. This setting encompasses the classical ubiquity techniques, as well as the mass and the large intersection transference principles, thereby leading to a thorough description of the properties in terms of Hausdorff measures and large intersection classes associated with general gauge functions. The sets issued from eutaxic sequences of points and optimal regular systems may naturally be described within this framework. The discussed applications include the classical homogeneous and inhomogeneous approximation, the approximation by algebraic numbers, the approximation by fractional parts, the study of uniform and Poisson random coverings, and the multifractal analysis of L{é}vy processes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Hypergraph Acyclicity and Propositional Model Counting

We show that the propositional model counting problem #SAT for CNF- formulas with hypergraphs that allow a disjoint branches decomposition can be solved in polynomial time. We show that this class of hypergraphs is incomparable to hypergraphs of bounded incidence cliquewidth which were the biggest class of hypergraphs for which #SAT was known to be solvable in polynomial time so far. Furthermore, we present a polynomial time algorithm that computes a disjoint branches decomposition of a given hypergraph if it exists and rejects otherwise. Finally, we show that some slight extensions of the class of hypergraphs with disjoint branches decompositions lead to intractable #SAT, leaving open how to generalize the counting result of this paper.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Metric Diophantine approximation on the middle-third Cantor set

Let $μ\geq 2$ be a real number and let $\Mcal(μ)$ denote the set of real numbers approximable at order at least $μ$ by rational numbers. More than eighty years ago, Jarní k and, independently, Besicovitch established that the Hausdorff dimension of $\Mcal(μ)$ is equal to $2/μ$. We investigate the size of the intersection of $\Mcal(μ)$ with Ahlfors regular compact subsets of the interval $[0, 1]$. In particular, we propose a conjecture for the exact value of the dimension of $\Mcal(μ)$ intersected with the middle-third Cantor set and give several results supporting this conjecture. We especially show that the conjecture holds for a natural probabilistic model that is intended to mimic the distribution of the rationals. The core of our study relies heavily on dimension estimates concerning the set of points lying in an Ahlfors regular set and approximated at a given rate by a system of random points.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Structural Tractability of Counting of Solutions to Conjunctive Queries

In this paper we explore the problem of counting solutions to conjunctive queries. We consider a parameter called the \emph{quantified star size} of a formula $φ$ which measures how the free variables are spread in $φ$. We show that for conjunctive queries that admit nice decomposition properties (such as being of bounded treewidth or generalized hypertree width) bounded quantified star size exactly characterizes the classes of queries for which counting the number of solutions is tractable. This also allows us to fully characterize the conjunctive queries for which counting the solutions is tractable in the case of bounded arity. To illustrate the applicability of our results, we also show that computing the quantified star size of a formula is possible in time $n^{O(k)}$ for queries of generalized hypertree width $k$. Furthermore, quantified star size is even fixed parameter tractable parameterized by some other width measures, while it is $\W{1}$-hard for generalized hypertree width and thus unlikely to be fixed parameter tractable. We finally show how to compute an approximation of quantified star size in polynomial time where the approximation ratio depends on the width of the input.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The arithmetic complexity of tensor contractions

We investigate the algebraic complexity of tensor calulus. We consider a generalization of iterated matrix product to tensors and show that the resulting formulas exactly capture VP, the class of polynomial families efficiently computable by arithmetic circuits. This gives a natural and robust characterization of this complexity class that despite its naturalness is not very well understood so far.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Detection of an anomalous cluster in a network

We consider the problem of detecting whether or not, in a given sensor network, there is a cluster of sensors which exhibit an "unusual behavior." Formally, suppose we are given a set of nodes and attach a random variable to each node. We observe a realization of this process and want to decide between the following two hypotheses: under the null, the variables are i.i.d. standard normal; under the alternative, there is a cluster of variables that are i.i.d. normal with positive mean and unit variance, while the rest are i.i.d. standard normal. We also address surveillance settings where each sensor in the network collects information over time. The resulting model is similar, now with a time series attached to each node. We again observe the process over time and want to decide between the null, where all the variables are i.i.d. standard normal, and the alternative, where there is an emerging cluster of i.i.d. normal variables with positive mean and unit variance. The growth models used to represent the emerging cluster are quite general and, in particular, include cellular automata used in modeling epidemics. In both settings, we consider classes of clusters that are quite general, for which we obtain a lower bound on their respective minimax detection rate and show that some form of scan statistic, by far the most popular method in practice, achieves that same rate to within a logarithmic factor. Our results are not limited to the normal location model, but generalize to any one-parameter exponential family when the anomalous clusters are large enough.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Complexity of Weighted Counting for Acyclic Conjunctive Queries

This paper is a study of weighted counting of the solutions of acyclic conjunctive queries ($\ACQ$). The unweighted quantifier free version of this problem is known to be tractable (for combined complexity), but it is also known that introducing even a single quantified variable makes it $\sP$-hard. We first show that weighted counting for quantifier-free $\ACQ$ is still tractable and that even minimalistic extensions of the problem lead to hard cases. We then introduce a new parameter for quantified queries that permits to isolate large island of tractability. We show that, up to a standard assumption from parameterized complexity, this parameter fully characterizes tractable subclasses for counting weighted solutions of $\ACQ$ queries. Thus we completely determine the tractability frontier for weighted counting for $\ACQ$.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Fifty Years of the Spectrum Problem: Survey and New Results

In 1952, Heinrich Scholz published a question in the Journal of Symbolic Logic asking for a characterization of spectra, i.e., sets of natural numbers that are the cardinalities of finite models of first order sentences. Günter Asser asked whether the complement of a spectrum is always a spectrum. These innocent questions turned out to be seminal for the development of finite model theory and descriptive complexity. In this paper we survey developments over the last 50-odd years pertaining to the spectrum problem. Our presentation follows conceptual developments rather than the chronological order. Originally a number theoretic problem, it has been approached in terms of recursion theory, resource bounded complexity theory, classification by complexity of the defining sentences, and finally in terms of structural graph theory. Although Scholz' question was answered in various ways, Asser's question remains open. One appendix paraphrases the contents of several early and not easily accesible papers by G. Asser, A. Mostowski, J. Bennett and S. Mo. Another appendix contains a compendium of questions and conjectures which remain open.

0 citations0 reviewsNo code linkedOpen access