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

Johannes Schmidt

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

ResearcherUnclaimed source record
Computational Complexitycond-mat.stat-mechLogic in Computer ScienceArtificial Intelligencemath.AGmath.NTnlin.CGphysics.soc-phquant-ph

Catalog footprint

What is connected

19works
9topics
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

19 published item(s)

preprint2025arXiv

Complexity of Faceted Explanations in Propositional Abduction

Abductive reasoning is a popular non-monotonic paradigm that aims to explain observed symptoms and manifestations. It has many applications, such as diagnosis and planning in artificial intelligence and database updates. In propositional abduction, we focus on specifying knowledge by a propositional formula. The computational complexity of tasks in propositional abduction has been systematically characterized - even with detailed classifications for Boolean fragments. Unsurprisingly, the most insightful reasoning problems (counting and enumeration) are computationally highly challenging. Therefore, we consider reasoning between decisions and counting, allowing us to understand explanations better while maintaining favorable complexity. We introduce facets to propositional abductions, which are literals that occur in some explanation (relevant) but not all explanations (dispensable). Reasoning with facets provides a more fine-grained understanding of variability in explanations (heterogeneous). In addition, we consider the distance between two explanations, enabling a better understanding of heterogeneity/homogeneity. We comprehensively analyze facets of propositional abduction in various settings, including an almost complete characterization in Post's framework.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework

Logic-based argumentation is a well-established formalism modelling nonmonotonic reasoning. It has been playing a major role in AI for decades, now. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this paper, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Parson et al., J. Log. Comput., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: first, we consider all possible propositional fragments of the problem within Schaefer's framework (STOC 1978), and then study different parameterizations for each of the fragment. We identify a list of reasonable structural parameters (size of the claim, support, knowledge-base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (paraNP and beyond).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Exact scaling solution of the mode coupling equations for non-linear fluctuating hydrodynamics in one dimension

We obtain the exact solution of the one-loop mode-coupling equations for the dynamical structure function in the framework of non-linear fluctuating hydrodynamics in one space dimension for the strictly hyperbolic case where all characteristic velocities are different. All solutions are characterized by dynamical exponents which are Kepler ratios of consecutive Fibonacci numbers, which includes the golden mean as a limiting case. The scaling form of all higher Fibonacci modes are asymmetric Lévy-distributions. Thus a hierarchy of new dynamical universality classes is established. We also compute the precise numerical value of the Prähofer-Spohn scaling constant to which scaling functions obtained from mode coupling theory are sensitive.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Sections, Homotopy Rational Points and Reductions of Curves

We study unramified sections of the fundamental group sequence of smooth projective curves of genus $\geq 2$ over $p$-adic fields together with an integral model. We are particularly interested in the induced specialized sections of the special fibre and how they relate to homotopy rational points over the residue field. Under mild assumptions, such a specialized section induces a unique homotopy rational point of the special fibre that is compatible with the original section of the generic fibre in cohomological settings. We give two applications of such specialized homotopy rational points around the $\ell$-adic cycle class of a section.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Weight in Enumeration

In our setting enumeration amounts to generate all solutions of a problem instance without duplicates. We address the problem of enumerating the models of B-formulae. A B-formula is a propositional formula whose connectives are taken from a fixed set B of Boolean connectives. Without imposing any specific order to output the solutions, this task is solved. We completely classify the complexity of this enumeration task for all possible sets of connectives B imposing the orders of (1) non-decreasing weight, (2) non-increasing weight; the weight of a model being the number of variables assigned to 1. We consider also the weighted variants where a non-negative integer weight is assigned to each variable and show that this add-on leads to more sophisticated enumeration algorithms and even renders previously tractable cases intractable, contrarily to the constraint setting. As a by-product we obtain complete complexity classifications for the optimization problems known as Min-Ones and Max-Ones which are in the B-formula setting two different tasks.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Defect-induced phase transition in the asymmetric simple exclusion process

We reconsider the long-standing question of the critical defect hopping rate $r_c$ in the one-dimensional totally asymmetric exclusion process (TASEP) with a slow bond (defect). For $r< r_c$ a phase separated state is observed due to queuing at the defect site whereas for $r\geq r_c$ the defect site has only local effects on the stationary state of the homogeneous system. Mean-field theory predicts $r_c=1$ (when hopping rates outside the defect bond are equal to 1) but numerical investigations seem to indicate $r_c \approx 0.80(2)$. Here we improve the numerics to show that $r_c > 0.99$ and give strong evidence that indeed $r_c=1$ as predicted by mean-field theory, and anticipated by recent theoretical findings.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Fibonacci family of dynamical universality classes

Universality is a well-established central concept of equilibrium physics. However, in systems far away from equilibrium a deeper understanding of its underlying principles is still lacking. Up to now, a few classes have been identified. Besides the diffusive universality class with dynamical exponent $z=2$ another prominent example is the superdiffusive Kardar-Parisi-Zhang (KPZ) class with $z=3/2$. It appears e.g. in low-dimensional dynamical phenomena far from thermal equilibrium which exhibit some conservation law. Here we show that both classes are only part of an infinite discrete family of non-equilibrium universality classes. Remarkably their dynamical exponents $z_α$ are given by ratios of neighbouring Fibonacci numbers, starting with either $z_1=3/2$ (if a KPZ mode exist) or $z_1=2$ (if a diffusive mode is present). If neither a diffusive nor a KPZ mode are present, all dynamical modes have the Golden Mean $z=(1+\sqrt{5})/2$ as dynamical exponent. The universal scaling functions of these Fibonacci modes are asymmetric Lévy distributions which are completely fixed by the macroscopic current-density relation and compressibility matrix of the system and hence accessible to experimental measurement.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Homotopy Rational Points of Brauer-Severi Varieties

We study homotopy rational points of Brauer-Severi varieties over fields of characteristic zero. We are particularly interested if a Brauer-Severi variety admitting a homotopy rational point splits. The analogue statement turns out to be true for open subvarieties of twisted hyperplane arrangements. In the complete case, the obstruction turns out to be the pullback of the Chern class of a generator of the Picard group along the homotopy rational point. Moreover, we will show that every Brauer-Severi variety over a $p$-adic field with $p$-primary period admits a homotopy rational point.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

When is a bottleneck a bottleneck?

Bottlenecks, i.e. local reductions of capacity, are one of the most relevant scenarios of traffic systems. The asymmetric simple exclusion process (ASEP) with a defect is a minimal model for such a bottleneck scenario. One crucial question is "What is the critical strength of the defect that is required to create global effects, i.e. traffic jams localized at the defect position". Intuitively one would expect that already an arbitrarily small bottleneck strength leads to global effects in the system, e.g. a reduction of the maximal current. Therefore it came as a surprise when, based on computer simulations, it was claimed that the reaction of the system depends in non-continuous way on the defect strength and weak defects do not have a global influence on the system. Here we reconcile intuition and simulations by showing that indeed the critical defect strength is zero. We discuss the implications for the analysis of empirical and numerical data.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Complexity Classifications for logic-based Argumentation

We consider logic-based argumentation in which an argument is a pair (Fi,al), where the support Fi is a minimal consistent set of formulae taken from a given knowledge base (usually denoted by De) that entails the claim al (a formula). We study the complexity of three central problems in argumentation: the existence of a support Fi ss De, the validity of a support and the relevance problem (given psi is there a support Fi such that psi ss Fi?). When arguments are given in the full language of propositional logic these problems are computationally costly tasks, the validity problem is DP-complete, the others are SigP2-complete. We study these problems in Schaefer's famous framework where the considered propositional formulae are in generalized conjunctive normal form. This means that formulae are conjunctions of constraints build upon a fixed finite set of Boolean relations Ga (the constraint language). We show that according to the properties of this language Ga, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete or SigP2-complete. We present a dichotomous classification, P or DP-complete, for the verification problem and a trichotomous classification for the relevance problem into either polynomial, NP-complete, or SigP2-complete. These last two classifications are obtained by means of algebraic tools.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Non-KPZ modes in two-species driven diffusive systems

Using mode coupling theory and dynamical Monte-Carlo simulations we investigate the scaling behaviour of the dynamical structure function of a two-species asymmetric simple exclusion process, consisting of two coupled single-lane asymmetric simple exclusion processes. We demonstrate the appearence of a superdiffusive mode with dynamical exponent $z=5/3$ in the density fluctuations, along with a KPZ mode with $z=3/2$ and argue that this phenomenon is generic for short-ranged driven diffusive systems with more than one conserved density. When the dynamics is symmetric under the interchange of the two lanes a diffusive mode with $z=2$ appears instead of the non-KPZ superdiffusive mode.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis

Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the time complexity of the parameterized SAT($\cdot$) problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation $R$ such that SAT($R$) can be solved at least as fast as any other NP-hard SAT($\cdot$) problem. In this paper we extend this method and show that such languages also exist for the max ones problem (MaxOnes($Γ$)) and the Boolean valued constraint satisfaction problem over finite-valued constraint languages (VCSP($Δ$)). With the help of these languages we relate MaxOnes and VCSP to the exponential time hypothesis in several different ways.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Single Photon Transistor Mediated by Inter-State Rydberg Interaction

We report on the realization of an all-optical transistor by mapping gate and source photons into strongly interacting Rydberg excitations with different principal quantum numbers in an ultracold atomic ensemble. We obtain a record switch contrast of 40 % for a coherent gate input with mean photon number one and demonstrate attenuation of source transmission by over 10 photons with a single gate photon. We use our optical transistor to demonstrate the nondestructive detection of a single Rydberg atom with a fidelity of 0.72(4).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Paradigms for Parameterized Enumeration

The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First we define formally different notions of efficient enumeration in the context of parameterized complexity. Second we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Parameterized Complexity of Default Logic and Autoepistemic Logic

We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld etal. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XPnu), unless P=NP.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Complexity Classifications for Propositional Abduction in Post's Framework

In this paper we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining the world's behavior it aims at finding an explanation for some observed manifestation. In this paper we consider propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be \SigPtwo-complete in general. We focus on formulae in which the allowed connectives are taken from certain sets of Boolean functions. We consider different variants of the abduction problem in restricting both the manifestations and the hypotheses. For all these variants we obtain a complexity classification for all possible sets of Boolean functions. In this way, we identify easier cases, namely \NP-complete, \coNP-complete and polynomial cases. Thus, we get a detailed picture of the complexity of the propositional abduction problem, hence highlighting sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Complexity of Propositional Abduction for Restricted Sets of Boolean Functions

Abduction is a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observed manifestation. In this paper we focus on propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be SigmaP2-complete in general. We consider variants obtained by restricting the allowed connectives in the formulae to certain sets of Boolean functions. We give a complete classification of the complexity for all considerable sets of Boolean functions. In this way, we identify easier cases, namely NP-complete and polynomial cases; and we highlight sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.

0 citations0 reviewsNo code linkedOpen access