Search

In this article, we present a framework for deploying an aerial multi-agent system in large-scale subterranean environments with minimal infrastructure for supporting multi-agent operations. The multi-agent objective is to optimally and reactively allocate and execute inspection tasks in a mine, which are entered by a mine operator on-the-fly. The assignment of currently available tasks to the team of agents is accomplished through an auction-based system, where the agents bid for available tasks, which are used by a central auctioneer to optimally assigns tasks to agents. A mobile Wi-Fi mesh supports inter-agent communication and bi-directional communication between the agents and the task allocator, while the task execution is performed completely infrastructure-free. Given a task to be accomplished, a reliable and modular agent behavior is synthesized by generating behavior trees from a pool of agent capabilities, using a back-chaining approach. The auction system in the proposed framework is reactive and supports addition of new operator-specified tasks on-the-go, at any point through a user-friendly operator interface. The framework has been validated in a real underground mining environment using three aerial agents, with several inspection locations spread in an environment of almost 200 meters. The proposed framework can be utilized for missions involving rapid inspection, gas detection, distributed sensing and mapping etc. in a subterranean environment. The proposed framework and its field deployment contributes towards furthering reliable automation in large-scale subterranean environments to offload both routine and dangerous tasks from human operators to autonomous aerial robots., Comment: Submitted to IEEE Transactions on Field Robotics

We show that the complete Sp(2)-invariant expanding solitons for Bryant's Laplacian flow on the anti-self-dual bundle of the 4-sphere form a 1-parameter family, and that they are all asymptotically conical (AC). We determine their asymptotic cones, and prove that this cone determines the complete expander (up to scale). Neither the unique Sp(2)-invariant torsion-free G_2-cone nor the asymptotic cone of the explicit AC Sp(2)-invariant shrinker from arxiv:2112.09095 occurs as the asymptotic cone of a complete AC Sp(2)-invariant expander. We determine all possible end behaviours of Sp(2)-invariant solitons, identifying novel forward-complete end solutions for both expanders and shrinkers with faster-than-Euclidean volume growth. We conjecture that there exists a 1-parameter family of complete SU(3)-invariant expanders on the anti-self-dual bundle of the complex projective plane CP^2 with such asymptotic behaviour. We also conjecture that, in contrast to the Sp(2)-invariant case, there exist complete SU(3)-invariant AC expanders with asymptotic cone matching that of the explicit AC SU(3)-invariant shrinker from arxiv:2112.09095. The latter conjecture suggests that Laplacian flow may naturally implement a type of surgery in which a CP^2 shrinks to a conically singular point, but after which the flow can be continued smoothly, expanding a topologically different CP^2 from the singularity., Comment: 62 pages, 2 figures

Proactive collision avoidance measures are imperative in environments where humans and robots coexist. Moreover, the introduction of high quality legged robots into workplaces highlighted the crucial role of a robust, fully autonomous safety solution for robots to be viable in shared spaces or in co-existence with humans. This article establishes for the first time ever an innovative Detect-Track-and-Avoid Architecture (DTAA) to enhance safety and overall mission performance. The proposed novel architectyre has the merit ot integrating object detection using YOLOv8, utilizing Ultralytics embedded object tracking, and state estimation of tracked objects through Kalman filters. Moreover, a novel heuristic clustering is employed to facilitate active avoidance of multiple closely positioned objects with similar velocities, creating sets of unsafe spaces for the Nonlinear Model Predictive Controller (NMPC) to navigate around. The NMPC identifies the most hazardous unsafe space, considering not only their current positions but also their predicted future locations. In the sequel, the NMPC calculates maneuvers to guide the robot along a path planned by D$^{*}_{+}$ towards its intended destination, while maintaining a safe distance to all identified obstacles. The efficacy of the novelly suggested DTAA framework is being validated by Real-life experiments featuring a Boston Dynamics Spot robot that demonstrates the robot's capability to consistently maintain a safe distance from humans in dynamic subterranean, urban indoor, and outdoor environments.

We exhibit supercritical trade-off for monotone circuits, showing that there are functions computable by small circuits for which any circuit must have depth super-linear or even super-polynomial in the number of variables, far exceeding the linear worst-case upper bound. We obtain similar trade-offs in proof complexity, where we establish the first size-depth trade-offs for cutting planes and resolution that are truly supercritical, i.e., in terms of formula size rather than number of variables, and we also show supercritical trade-offs between width and size for treelike resolution. Our results build on a new supercritical width-depth trade-off for resolution, obtained by refining and strengthening the compression scheme for the Cop-Robber game in [Grohe, Lichter, Neuen & Schweitzer 2023]. This yields robust supercritical trade-offs for dimension versus iteration number in the Weisfeiler-Leman algorithm, which also translate into trade-offs between number of variables and quantifier depth in first-order logic. Our other results follow from improved lifting theorems that might be of independent interest., Comment: 47 pages, 7 figures

For almost two decades, mixed integer programming (MIP) solvers have used graph-based conflict analysis to learn from local infeasibilities during branch-and-bound search. In this paper, we improve MIP conflict analysis by instead using reasoning based on cuts, inspired by the development of conflict-driven solvers for pseudo-Boolean optimization. Phrased in MIP terminology, this type of conflict analysis can be understood as a sequence of linear combinations, integer roundings, and cut generation. We leverage this MIP perspective to design a new conflict analysis algorithm based on mixed integer rounding cuts, which theoretically dominates the state-of-the-art method in pseudo-Boolean optimization using Chv\'atal-Gomory cuts. Furthermore, we extend this cut-based conflict analysis from pure binary programs to mixed binary programs and-in limited form-to general MIP with also integer-valued variables. We perform an empirical evaluation of cut-based conflict analysis as implemented in the open-source MIP solver SCIP, testing it on a large and diverse set of MIP instances from MIPLIB 2017. Our experimental results indicate that the new algorithm improves the default performance of SCIP in terms of running time, number of nodes in the search tree, and the number of instances solved.

Power system communication networks enable operators to remotely monitor and control field equipment. The sophistication of these networks is also increasing as operators continue the trend towards digitization, which is beneficial in integrating distributed energy resources. However, as the attack surface increases in size so too does the risk of cyberattacks. The topology, configuration and composition of communication networks is therefore confidential since this can provide information to attackers. As a result, the number of benchmarks available for research purposes is limited. A tool for procedurally generating communication network topologies is therefore proposed. While primarily intended as an enabler for public research into communication networks, this tool also allows general insights to be gained into the effect of communication network design on the vulnerability of networks to cyberattacks. The tool includes the ability to encapsulate network characteristics in JSON specification files, which is demonstrated with example Advanced Metering Infrastructure (AMI), Supervisory Control and Data Acquisition (SCADA) and Wide Area Monitoring (WAM) specification files. The SCADA network generation is then compared to a real-world case. Finally, the effect of network redundancy on the networks cyber resilience is investigated., Comment: 9 pages, 11 figures, originally presented at the 15th DACH+ Energy Informatics Doctoral Workshop

The breaking of space-time symmetries and the non-conservation of the associated Noether charges constitutes a central artifact in lattice field theory. In prior work we have shown how to overcome this limitation for classical actions describing point particle motion, using the world-line formalism of general relativity. The key is to treat coordinate maps (from an abstract parameter space into space-time) as dynamical and dependent degrees of freedom, which remain continuous after discretization of the underlying parameter space. Here we present latest results where we construct a reparameterization invariant classical action for scalar fields, which features dynamical coordinate maps. We highlight the following achievements of our approach: 1) global space-time symmetries remain intact after discretization and the associated Noether charges remain exactly preserved 2) coordinate maps adapt to the dynamics of the scalar field leading to adaptive grid resolution guided by the symmetries., Comment: 9 pages, 5 figures, talk presented at the 41st International Symposium on Lattice Field Theory (Lattice 2024), 28 July - 3 August 2024

We show that a reformulation of the governing equations for incompressible multi-phase flow in the volume of fluid setting leads to a well defined energy rate. Weak nonlinear inflow-outflow and solid wall boundary conditions complement the development and lead to an energy estimate in terms of external data. The new formulation combined with summation-by-parts operators lead to provably nonlinear energy stability.

We introduce a novel construction procedure for one-dimensional summation-by-parts (SBP) operators. Existing construction procedures for FSBP operators of the form $D = P^{-1} Q$ proceed as follows: Given a boundary operator $B$, the norm matrix $P$ is first determined and then in a second step the complementary matrix $Q$ is calculated to finally get the FSBP operator $D$. In contrast, the approach proposed here determines the norm and complementary matrices, $P$ and $Q$, simultaneously by solving an optimization problem. The proposed construction procedure applies to classical SBP operators based on polynomial approximation and the broader class of function space SBP (FSBP) operators. According to our experiments, the presented approach yields a numerically stable construction procedure and FSBP operators with higher accuracy for diagonal norm difference operators at the boundaries than the traditional approach. Through numerical simulations, we highlight the advantages of our proposed technique., Comment: 18 pages, 8 Figures

We show that even though the Discontinuous Galerkin Spectral Element Method is stable for hyperbolic boundary-value problems, and the overset domain problem is well-posed in an appropriate norm, the energy of the approximation of the latter is bounded by data only for fixed polynomial order, mesh, and time. In the absence of dissipation, coupling of the overlapping domains is destabilizing by allowing positive eigenvalues in the system to be integrated in time. This coupling can be stabilized in one space dimension by using the upwind numerical flux. To help provide additional dissipation, we introduce a novel penalty method that applies dissipation at arbitrary points within the overlap region and depends only on the difference between the solutions. We present numerical experiments in one space dimension to illustrate the implementation of the well-posed penalty formulation, and show spectral convergence of the approximations when sufficient dissipation is applied.

We present a novel solution procedure for initial boundary value problems. The procedure is based on an action principle, in which coordinate maps are included as dynamical degrees of freedom. This reparametrization invariant action is formulated in an abstract parameter space and an energy density scale associated with the space-time coordinates separates the dynamics of the coordinate maps and of the propagating fields. Treating coordinates as dependent, i.e. dynamical quantities, offers the opportunity to discretize the action while retaining all space-time symmetries and also provides the basis for automatic adaptive mesh refinement (AMR). The presence of unbroken space-time symmetries after discretization also ensures that the associated continuum Noether charges remain exactly conserved. The presence of coordinate maps in addition provides new freedom in the choice of boundary conditions. An explicit numerical example for wave propagation in $1+1$ dimensions is provided, using recently developed regularized summation-by-parts finite difference operators., Comment: 50 pages, 12 figures

Building on the progress in Boolean satisfiability (SAT) solving over the last decades, maximum satisfiability (MaxSAT) has become a viable approach for solving NP-hard optimization problems, but ensuring correctness of MaxSAT solvers has remained an important concern. For SAT, this is largely a solved problem thanks to the use of proof logging, meaning that solvers emit machine-verifiable proofs of (un)satisfiability to certify correctness. However, for MaxSAT, proof logging solvers have started being developed only very recently. Moreover, these nascent efforts have only targeted the core solving process, ignoring the preprocessing phase where input problem instances can be substantially reformulated before being passed on to the solver proper. In this work, we demonstrate how pseudo-Boolean proof logging can be used to certify the correctness of a wide range of modern MaxSAT preprocessing techniques. By combining and extending the VeriPB and CakePB tools, we provide formally verified, end-to-end proof checking that the input and preprocessed output MaxSAT problem instances have the same optimal value. An extensive evaluation on applied MaxSAT benchmarks shows that our approach is feasible in practice.

We show that a specific skew-symmetric formulation of the nonlinear terms in the compressible Navier-Stokes equations leads to an energy rate in terms of surface integrals only. No dissipative volume integrals contribute to the energy rate. We also discuss boundary conditions that bounds the surface integrals.

It is well known that reformulating the original problem can be crucial for the performance of mixed-integer programming (MIP) solvers. To ensure correctness, all transformations must preserve the fea sibility status and optimal value of the problem, but there is currently no established methodology to express and verify the equivalence of two mixed-integer programs. In this work, we take a first step in this direction by showing how the correctness of MIP presolve reductions on 0-1 integer linear programs can be certified by using (and suitably extending) the VeriPB tool for pseudo-Boolean proof logging. Our experimental evaluation on both decision and optimization instances demonstrates the computational viability of the approach and leads to suggestions for future revisions of the proof format that will help to reduce the verbosity of the certificates and to accelerate the certification and verification process further.

In a recently developed variational discretization scheme for second order initial value problems ( J. Comput. Phys. 498, 112652 (2024) ), it was shown that the Noether charge associated with time translation symmetry is exactly preserved in the interior of the simulated domain. The obtained solution also fulfils the naively discretized equations of motions inside the domain, except for the last two grid points. Here we provide an explanation for the deviations at the boundary as stemming from the Lagrange multipliers used to implement initial and connection conditions. We show explicitly that the Noether charge including the boundary corrections is exactly preserved at its continuum value over the whole simulation domain, including the boundary points., Comment: 9 pages, 1 figure. arXiv admin note: text overlap with arXiv:2307.04490

Magnetic resonance imaging has evolved as a key component for prostate cancer (PCa) detection, substantially increasing the radiologist workload. Artificial intelligence (AI) systems can support radiological assessment by segmenting and classifying lesions in clinically significant (csPCa) and non-clinically significant (ncsPCa). Commonly, AI systems for PCa detection involve an automatic prostate segmentation followed by the lesion detection using the extracted prostate. However, evaluation reports are typically presented in terms of detection under the assumption of the availability of a highly accurate segmentation and an idealistic scenario, omitting the propagation of errors between modules. For that purpose, we evaluate the effect of two different segmentation networks (s1 and s2) with heterogeneous performances in the detection stage and compare it with an idealistic setting (s1:89.90+-2.23 vs 88.97+-3.06 ncsPCa, P<.001, 89.30+-4.07 and 88.12+-2.71 csPCa, P<.001). Our results depict the relevance of a holistic evaluation, accounting for all the sub-modules involved in the system., Comment: Under review

An accurate prostate delineation and volume characterization can support the clinical assessment of prostate cancer. A large amount of automatic prostate segmentation tools consider exclusively the axial MRI direction in spite of the availability as per acquisition protocols of multi-view data. Further, when multi-view data is exploited, manual annotations and availability at test time for all the views is commonly assumed. In this work, we explore a contrastive approach at training time to leverage multi-view data without annotations and provide flexibility at deployment time in the event of missing views. We propose a triplet encoder and single decoder network based on U-Net, tU-Net (triplet U-Net). Our proposed architecture is able to exploit non-annotated sagittal and coronal views via contrastive learning to improve the segmentation from a volumetric perspective. For that purpose, we introduce the concept of inter-view similarity in the latent space. To guide the training, we combine a dice score loss calculated with respect to the axial view and its manual annotations together with a multi-view contrastive loss. tU-Net shows statistical improvement in dice score coefficient (DSC) with respect to only axial view (91.25+-0.52% compared to 86.40+-1.50%,P<.001). Sensitivity analysis reveals the volumetric positive impact of the contrastive loss when paired with tU-Net (2.85+-1.34% compared to 3.81+-1.88%,P<.001). Further, our approach shows good external volumetric generalization in an in-house dataset when tested with multi-view data (2.76+-1.89% compared to 3.92+-3.31%,P=.002), showing the feasibility of exploiting non-annotated multi-view data through contrastive learning whilst providing flexibility at deployment in the event of missing views., Comment: Under review

Background: Prostate cancer (PC) MRI-based risk calculators are commonly based on biological (e.g. PSA), MRI markers (e.g. volume), and patient age. Whilst patient age measures the amount of years an individual has existed, biological age (BA) might better reflect the physiology of an individual. However, surrogates from prostate MRI and linkage with clinically significant PC (csPC) remain to be explored. Purpose: To obtain and evaluate Prostate Age Gap (PAG) as an MRI marker tool for csPC risk. Study type: Retrospective. Population: A total of 7243 prostate MRI slices from 468 participants who had undergone prostate biopsies. A deep learning model was trained on 3223 MRI slices cropped around the gland from 81 low-grade PC (ncsPC, Gleason score <=6) and 131 negative cases and tested on the remaining 256 participants. Assessment: Chronological age was defined as the age of the participant at the time of the visit and used to train the deep learning model to predict the age of the patient. Following, we obtained PAG, defined as the model predicted age minus the patient's chronological age. Multivariate logistic regression models were used to estimate the association through odds ratio (OR) and predictive value of PAG and compared against PSA levels and PI-RADS>=3. Statistical tests: T-test, Mann-Whitney U test, Permutation test and ROC curve analysis. Results: The multivariate adjusted model showed a significant difference in the odds of clinically significant PC (csPC, Gleason score >=7) (OR =3.78, 95% confidence interval (CI):2.32-6.16, P <.001). PAG showed a better predictive ability when compared to PI-RADS>=3 and adjusted by other risk factors, including PSA levels: AUC =0.981 vs AUC =0.704, p<.001. Conclusion: PAG was significantly associated with the risk of clinically significant PC and outperformed other well-established PC risk factors., Comment: Under review

Conflict analysis has been successfully generalized from Boolean satisfiability (SAT) solving to mixed integer programming (MIP) solvers, but although MIP solvers operate with general linear inequalities, the conflict analysis in MIP has been limited to reasoning with the more restricted class of clausal constraint. This is in contrast to how conflict analysis is performed in so-called pseudo-Boolean solving, where solvers can reason directly with 0-1 integer linear inequalities rather than with clausal constraints extracted from such inequalities. In this work, we investigate how pseudo-Boolean conflict analysis can be integrated in MIP solving, focusing on 0-1 integer linear programs (0-1 ILPs). Phrased in MIP terminology, conflict analysis can be understood as a sequence of linear combinations and cuts. We leverage this perspective to design a new conflict analysis algorithm based on mixed integer rounding (MIR) cuts, which theoretically dominates the state-of-the-art division-based method in pseudo-Boolean solving. We also report results from a first proof-of-concept implementation of different pseudo-Boolean conflict analysis methods in the open-source MIP solver SCIP. When evaluated on a large and diverse set of 0-1 ILP instances from MIPLIB 2017, our new MIR-based conflict analysis outperforms both previous pseudo-Boolean methods and the clause-based method used in MIP. Our conclusion is that pseudo-Boolean conflict analysis in MIP is a promising research direction that merits further study, and that it might also make sense to investigate the use of such conflict analysis to generate stronger no-goods in constraint programming.

A stencil-adaptive SBP-SAT finite difference scheme is shown to display superconvergent behavior. Applied to the linear advection equation, it has a convergence rate $\mathcal{O}(\Delta x^4)$ in contrast to a conventional scheme, which converges at a rate $\mathcal{O}(\Delta x^3)$., Comment: 9 pages, 1 figure

Taking insight from the theory of general relativity, where space and time are treated on the same footing, we develop a novel geometric variational discretization for second order initial value problems (IVPs). By discretizing the dynamics along a world-line parameter, instead of physical time directly, we retain manifest translation symmetry and conservation of the associated continuum Noether charge. A non-equidistant time discretization emerges dynamically, realizing a form of automatic adaptive mesh refinement (AMR), guided by the system symmetries. Using appropriately regularized summation by parts finite difference operators, the continuum Noether charge, defined via the Killing vector associated with translation symmetry, is shown to be exactly preserved in the interior of the simulated time interval. The convergence properties of the approach are demonstrated with two explicit examples., Comment: 35 pages, 12 figures

We investigate the influence of uncertain data on solutions to initial boundary value problems. Uncertainty in the forcing function, initial conditions and boundary conditions are considered and we quantify their relative influence for short and long time calculations. It is shown that dissipative boundary conditions leading to energy bounds play a crucial role. For short time calculations, uncertainty in the initial data dominate. As time grows, the influence of initial data vanish exponentially fast. For longer time calculations, the uncertainty in the forcing function and boundary data dominate, as they grow in time. Errors due to the forcing function grows faster (linearly in time) than the ones due to the boundary data (grows as the square root of time). Roughly speaking, the results indicate that for short time calculations, the initial conditions are the most important, but for longer time calculations, focus should be on modelling efforts and boundary conditions. Our findings have impact on predictions where similar mathematical and numerical techniques are used for both short and long times as for example in regional weather and climate predictions.

Many applications rely on solving time-dependent partial differential equations (PDEs) that include second derivatives. Summation-by-parts (SBP) operators are crucial for developing stable, high-order accurate numerical methodologies for such problems. Conventionally, SBP operators are tailored to the assumption that polynomials accurately approximate the solution, and SBP operators should thus be exact for them. However, this assumption falls short for a range of problems for which other approximation spaces are better suited. We recently addressed this issue and developed a theory for first-derivative SBP operators based on general function spaces, coined function-space SBP (FSBP) operators. In this paper, we extend the innovation of FSBP operators to accommodate second derivatives. The developed second-derivative FSBP operators maintain the desired mimetic properties of existing polynomial SBP operators while allowing for greater flexibility by being applicable to a broader range of function spaces. We establish the existence of these operators and detail a straightforward methodology for constructing them. By exploring various function spaces, including trigonometric, exponential, and radial basis functions, we illustrate the versatility of our approach. The work presented here opens up possibilities for using second-derivative SBP operators based on suitable function spaces, paving the way for a wide range of applications in the future., Comment: 28 pages, 12 figures

A spin Hamiltonian, which characterizes interatomic interactions between spin moments, is highly valuable in predicting and comprehending the magnetic properties of materials. A deeper understanding of the microscopic origin of magnetic interactions can open new pathways toward realizing nanometer-scale systems for future spintronic devices. Here, we explore a method for explicitly calculating interatomic exchange interactions in non-collinear configurations of magnetic materials considering only a bilinear spin Hamiltonian in a local scenario. Based on density-functional theory (DFT) calculations of dimers adsorbed on metallic surfaces, and with a focus on the Dzyaloshinskii-Moriya interaction (DMI) which is essential for stabilizing chiral non-collinear magnetic states, we discuss the interpretation of the DMI when decomposed into microscopic electron and spin densities and currents. We clarify the distinct origins of spin currents induced in the system and their connection to the DMI. In addition, we reveal how non-collinearity affects the usual DMI, which is solely induced by spin-orbit coupling, and DMI-like interactions brought about by non-collinearity. We explain how the dependence of the DMI on the magnetic configuration establishes a connection between high-order magnetic interactions, enabling the transition from a local to a global spin Hamiltonian., Comment: 11 pages, 3 figures

In this article we develop a high order accurate method to solve the incompressible boundary layer equations in a provably stable manner.~We first derive continuous energy estimates,~and then proceed to the discrete setting.~We formulate the discrete approximation using high-order finite difference methods on summation-by-parts form and implement the boundary conditions weakly using the simultaneous approximation term method.~By applying the discrete energy method and imitating the continuous analysis,~the discrete estimate that resembles the continuous counterpart is obtained proving stability.~We also show that these newly derived boundary conditions removes the singularities associated with the null-space of the nonlinear discrete spatial operator.~Numerical experiments that verifies the high-order accuracy of the scheme and coincides with the theoretical results are presented.~The numerical results are compared with the well-known Blasius similarity solution as well as that resulting from the solution of the incompressible Navier Stokes equations.

We derive new boundary conditions and implementation procedures for nonlinear initial boundary value problems (IBVPs) with non-zero boundary data that lead to bounded solutions. The new boundary procedure is applied to nonlinear IBVPs in skew-symmetric form, including dissipative terms. The complete procedure has two main ingredients. In the first part (published in [1, 2]), the energy and entropy rate in terms of a surface integral with boundary terms was produced for problems with first derivatives. In this second part we complement it by adding second derivative terms and new nonlinear boundary procedures leading for boundary conditions with non-zero data. The new nonlinear boundary procedure generalise the well known characteristic boundary procedure for linear problems to the nonlinear setting. To introduce the procedure, a skew-symmetric scalar IBVP encompassing the linear advection equation and Burgers equation is analysed. Once the continuous analysis is done, we show that energy stable nonlinear discrete approximations follow by using summation-by-parts operators combined with weak boundary conditions. The scalar analysis is subsequently repeated for general nonlinear systems of equations. Finally, the new boundary procedure is applied to four important IBVPs in computational fluid dynamics: the incompressible Euler and Navier-Stokes, the shallow water and the compressible Euler equations., Comment: arXiv admin note: substantial text overlap with arXiv:2301.04568

We consider the graph $k$-colouring problem encoded as a set of polynomial equations in the standard way over $0/1$-valued variables. We prove that there are bounded-degree graphs that do not have legal $k$-colourings but for which the polynomial calculus proof system defined in [Clegg et al '96, Alekhnovich et al '02] requires linear degree, and hence exponential size, to establish this fact. This implies a linear degree lower bound for any algorithms based on Gr\"{o}bner bases solving graph $k$-colouring using this encoding. The same bound applies also for the algorithm studied in a sequence of papers [De Loera et al '08,'09,'11,'15] based on Hilbert's Nullstellensatz proofs for a slightly different encoding, thus resolving an open problem mentioned in [De Loera et al '08,'09,'11] and [Li '16]. We obtain our results by combining the polynomial calculus degree lower bound for functional pigeonhole principle (FPHP) formulas over bounded-degree bipartite graphs in [Mik\v{s}a and Nordstr\"{o}m '15] with a reduction from FPHP to $k$-colouring derivable by polynomial calculus in constant degree.

We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of how hard it is to decide exactly or approximately the number of pebbles needed for a given DAG in these games. We prove that the problem of eciding whether $s$~pebbles suffice to reversibly pebble a DAG $G$ is PSPACE-complete, as was previously shown for the standard pebble game in [Gilbert, Lengauer and Tarjan '80]. Via two different graph product constructions we then strengthen these results to establish that both standard and reversible pebbling space are PSPACE-hard to approximate to within any additive constant. To the best of our knowledge, these are the first hardness of approximation results for pebble games in an unrestricted setting (even for polynomial time). Also, since [Chan '13] proved that reversible pebbling is equivalent to the games in [Dymond and Tompa '85] and [Raz and McKenzie '99], our results apply to the Dymond--Tompa and Raz--McKenzie games as well, and from the same paper it follows that resolution depth is PSPACE-hard to determine up to any additive constant. We also obtain a multiplicative logarithmic separation between reversible and standard pebbling space. This improves on the additive logarithmic separation previously known and could plausibly be tight, although we are not able to prove this. We leave as an interesting open problem whether our additive hardness of approximation result could be strengthened to a multiplicative bound if the computational resources are decreased from polynomial space to the more common setting of polynomial time.

We extend the construction of so-called encapsulated global summation-by-parts operators to the general case of a mesh which is not boundary conforming. Owing to this development, energy stable discretizations of nonlinear and variable coefficient initial boundary value problems can be formulated in simple and straightforward ways using high-order accurate operators of generalized summation-by-parts type. Encapsulated features on a single computational block or element may include polynomial bases, tensor products as well as curvilinear coordinate transformations. Moreover, through the use of inner product preserving interpolation or projection, the global summation-by-parts property in extended to arbitrary multi-block or multi-element meshes with non-conforming nodal interfaces.

This work presents a study on label noise in medical image segmentation by considering a noise model based on Gaussian field deformations. Such noise is of interest because it yields realistic looking segmentations and because it is unbiased in the sense that the expected deformation is the identity mapping. Efficient methods for sampling and closed form solutions for the marginal probabilities are provided. Moreover, theoretically optimal solutions to the loss functions cross-entropy and soft-Dice are studied and it is shown how they diverge as the level of noise increases. Based on recent work on loss function characterization, it is shown that optimal solutions to soft-Dice can be recovered by thresholding solutions to cross-entropy with a particular a priori unknown threshold that efficiently can be computed. This raises the question whether the decrease in performance seen when using cross-entropy as compared to soft-Dice is caused by using the wrong threshold. The hypothesis is validated in 5-fold studies on three organ segmentation problems from the TotalSegmentor data set, using 4 different strengths of noise. The results show that changing the threshold leads the performance of cross-entropy to go from systematically worse than soft-Dice to similar or better results than soft-Dice.