Search

The $\ell$-matroid intersection ($\ell$-MI) problem asks if $\ell$ given matroids share a common basis. Already for $\ell = 3$, notable canonical NP-complete special cases are $3$-Dimensional Matching and Hamiltonian Path on directed graphs. However, while these problems admit exponential-time algorithms that improve the simple brute force, the fastest known algorithm for $3$-MI is exactly brute force with runtime $2^{n}/poly(n)$, where $n$ is the number of elements. Our first result shows that in fact, brute force cannot be significantly improved, by ruling out an algorithm for $\ell$-MI with runtime $o\left(2^{n-5 \cdot n^{\frac{1}{\ell-1}} \cdot \log (n)}\right)$, for any fixed $\ell\geq 3$. The complexity gap between $3$-MI and the polynomially solvable $2$-matroid intersection calls for a better understanding of the complexity of intermediate problems. One such prominent problem is exact matroid intersection (EMI). Given two matroids whose elements are either red or blue and a number $k$, decide if there is a common basis which contains exactly $k$ red elements. We show that EMI does not admit a randomized polynomial time algorithm. This bound implies that the parameterized algorithm of Eisenbrand et al. (FOCS'24) for exact weight matroid cannot be generalized to matroid intersection. We further obtain: (i) an algorithm that solves $\ell$-MI faster than brute force in time $2^{n-\Omega\left(\log^2 (n)\right)} $ (ii) a parameterized running time lower bound of $2^{(\ell-2) \cdot k \cdot \log k} \cdot poly(n)$ for $\ell$-MI, where the parameter $k$ is the rank of the matroids. We obtain these two results by generalizing the Monotone Local Search technique of Fomin et al. (J. ACM'19). Broadly speaking, our generalization converts any parameterized algorithm for a subset problem into an exponential-time algorithm which is faster than brute-force.

Many problems in navigation and tracking require increasingly accurate characterizations of the evolution of uncertainty in nonlinear systems. Nonlinear uncertainty propagation approaches based on Gaussian mixture density approximations offer distinct advantages over sampling based methods in their computational cost and continuous representation. State-of-the-art Gaussian mixture approaches are adaptive in that individual Gaussian mixands are selectively split into mixtures to yield better approximations of the true propagated distribution. Despite the importance of the splitting process to accuracy and computational efficiency, relatively little work has been devoted to mixand selection and splitting direction optimization. The first part of this work presents splitting methods that preserve the mean and covariance of the original distribution. Then, we present and compare a number of novel heuristics for selecting the splitting direction. The choice of splitting direction is informed by the initial uncertainty distribution, properties of the nonlinear function through which the original distribution is propagated, and a whitening based natural scaling method to avoid dependence of the splitting direction on the scaling of coordinates. We compare these novel heuristics to existing techniques in three distinct examples involving Cartesian to polar coordinate transformation, Keplerian orbital element propagation, and uncertainty propagation in the circular restricted three-body problem.

In this work, we investigate trajectories that require thrust to maintain periodic structure in the circular restricted three-body problem (CR3BP). We produce bounds in position and velocity space for the energy-constrained reachable set of initial conditions. Our trajectories are energy-optimal and analyzed via linear analysis. We provide validation for our technique and analyze the cost of deviating in various directions to the reference. For our given reference, we find that it is relatively expensive to decrease perilune distance for orbits in the Earth-Moon system., Comment: Submitted to 2024 AAS/AIAA Astrodynamics Specialist Conference Proceedings

We present an experimental platform for linear-optical quantum information processing. Our setup utilizes multiphoton generation using a high-quality single-photon source, which is demultiplexed across multiple spatial channels, a custom-designed, programmable, low-loss photonic chip, and paired with high-efficiency single-photon detectors. We demonstrate the platform's capability in producing heralded arbitrary two-qubit dual-rail encoded states, a crucial building block for large-scale photonic quantum computers. The programmable chip was fully characterized through a calibration process that allowed us to create a numerical model accounting for fabrication imperfections and measurement errors. As a result, using on-chip quantum state tomography (QST), we achieved high-fidelity quantum state preparation, with a fidelity of 98.5\% specifically for the Bell state., Comment: 11 pages, 11 figures

Industrial control systems are becoming more distributed and interconnected to allow for interaction with modern computing infrastructures. Furthermore, the amount of data generated by these systems is increasing due to integration of more sensors and the need to increase the reliability of the system based on predictive data models. One challenge in accommodating this data and interconnectivity increase is the change of the architecture of these systems from monolithic to component based, distributed systems. Questions such as how to deploy and operate such distributed system with many sub-components arise. One approach is the use of kubernetes to orchestrate the different components as containers. The critical nature of the industrial control systems however often requires strict component isolation and network segmentation to satisfy security requirements. Cilium is a popular network overlay for kubernetes that enables definition of network policies between different components running as kubernetes pods. The network policies are crucial for maintaining the secure operation of the system, however analysis of deployed policies is often lacking. In this paper, we explore the use of a formal analysis of Cilium network policies using VDM-SL. We provide examples of Cilium policies, an approach how they could be formalised using VDM-SL and analyse several scenarios to validate the policies against a model of simple real-life system.

Graph-based machine learning models for materials properties show great potential to accelerate virtual high-throughput screening of large chemical spaces. However, in their simplest forms, graph-based models do not include any 3D information and are unable to distinguish stereoisomers such as those arising from different orderings of ligands around a metal center in coordination complexes. In this work we present a modification to revised autocorrelation descriptors, our molecular graph featurization method for machine learning various spin state dependent properties of octahedral transition metal complexes (TMCs). Inspired by analytical semi-empirical models for TMCs, the new modeling strategy is based on the many-body expansion (MBE) and allows one to tune the captured stereoisomer information by changing the truncation order of the MBE. We present the necessary modifications to include this approach in two commonly used machine learning methods, kernel ridge regression and feed-forward neural networks. On a test set composed of all possible isomers of binary transition metal complexes, the best MBE models achieve mean absolute errors of 2.75 kcal/mol on spin-splitting energies and 0.26 eV on frontier orbital energy gaps, a 30-40% reduction in error compared to models based on our previous approach. We also observe improved generalization to previously unseen ligands where the best-performing models exhibit mean absolute errors of 4.00 kcal/mol (i.e., a 0.73 kcal/mol reduction) on the spin-splitting energies and 0.53 eV (i.e., a 0.10 eV reduction) on the frontier orbital energy gaps. Because the new approach incorporates insights from electronic structure theory, such as ligand additivity relationships, these models exhibit systematic generalization from homoleptic to heteroleptic complexes, allowing for efficient screening of TMC search spaces.

Parametrized quantum circuits are essential components of variational quantum algorithms. Until now, optical implementations of these circuits have relied solely on adjustable linear optical units. In this study, we demonstrate that using programmable nonlinearities, rather than linear optics, offers a more efficient method for constructing quantum optical circuits -- especially quantum neural networks. This approach significantly reduces the number of adjustable parameters and the circuit depth needed to achieve high-fidelity operation. Specifically, we explored a quantum optical neural network (QONN) architecture composed of meshes of two-mode interferometers programmable by adjustable Kerr-like nonlinearities. We assessed the capabilities of our quantum optical neural network architecture and compared its performance to previously studied architectures that use multimode linear optics units. Additionally, we suggest future research directions for improving programmable quantum optical circuits., Comment: 17 pages, 16 figures

The stable-regenerative multiple-stable model has been shown recently to have distinct candidate extremal index and extremal index. To understand further this rare phenomenon, two more results are established here for the double-stable model. The first is the convergence of point processes for the clusters of extremes, enhancing the previous result on the weak convergence of random sup-measures. Most interestingly, the second result reveals a new phase transition at the mesoscopic level when computing the asymptotic exceedance probability over a block, $\mathbb P(\max_{k=1,\dots,d_n} X_k>b_n)$, as $n\to\infty$. Here, the mesoscopic level is referred to the fact that the block size $d_n$ is allowed to grow at the rate $n^\rho$ with $\rho\in[0,1]$, while the threshold $b_n$ is such that $\mathbb P(X_1>b_n)\sim 1/n$. The recently discovered discrepancy between the candidate extremal index and the extremal index is shown to be just a reflection of this phase transition that is prohibited by the anticlustering condition., Comment: 38 pages; corrected a few typos and implemented some minor edits

A search for the $K^{+} \to \pi^{0}\pi^{0}\pi^{0}e^+\nu$ decay is performed by the OKA collaboration. The search is based on $3.65 \times 10^9 ~ K^+$ decays. No signal is observed. The upper limit set is $BR(K^{+} \to \pi^{0}\pi^{0}\pi^{0}e^+\nu) < 5.4\times 10^{-8} ~ 90\%$ CL, 65 times lower than the one currently listed by PDG.

Linear methods are ubiquitous for control and estimation problems. In this work, we present a number of tensor operator norms as a means to approximately bound the error associated with linear methods and determine the situations in which that maximum error is encountered. An emphasis is placed on induced norms that can be computed in terms of matrix or tensor eigenvalues associated with coefficient tensors from higher-order Taylor series. These operator norms can be used to understand the performance and range of applicability of an algorithm exploiting linear approximations in different sets of coordinates. We examine uses of tensor operator norms in the context of linear and higher-order rendezvous guidance, coordinate selection for a filtering measurement model, and to present a unified treatment of nonlinearity indices for dynamical systems. Tensor norm computations can offer insights into these problems in one to two orders of magnitude less time than similarly accurate sampling methods while providing more general understanding of the error performance of linear or higher-order approximations.

We report low-loss multiscan waveguides fabricated in fused silica using femtosecond laser writing technology. The multiscan principle allows to tailor the writing regime to excel at key features of any integrated photonic platform: coupling losses and propagation losses. We optimized the writing parameters for different sizes of square-shaped waveguides and reached the mode overlap value with a standard single-mode optical fiber of above 98.8\% and demonstrated very low coupling losses of 0.2 dB/facet on average. Propagation losses in the fabricated waveguides amounted to 0.07 dB/cm. We applied the developed recipe to the fabrication of a fiber-coupled 25-channel interferometer with total insertion losses below 1 dB. The findings of this work are of interest for broad range of applications and in particular for optical information processing and quantum photonics., Comment: 12 pages, 9 figures

In this paper we introduce Sampling with a Black Box, a generic technique for the design of parameterized approximation algorithms for vertex deletion problems (e.g., Vertex Cover, Feedback Vertex Set, etc.). The technique relies on two components: $\bullet$ A Sampling Step. A polynomial time randomized algorithm which given a graph $G$ returns a random vertex $v$ such that the optimum of $G\setminus \{v\}$ is smaller by $1$ than the optimum of $G$ with some prescribed probability $q$. We show such algorithms exists for multiple vertex deletion problems. $\bullet$ A Black Box algorithm which is either an exact parameterized algorithm or a polynomial time approximation algorithm. Our technique combines these two components together. The sampling step is applied iteratively to remove vertices from the input graph, and then the solution is extended using the black box algorithm. The process is repeated sufficiently many times so that the target approximation ratio is attained with a constant probability. The main novelty of our work lies in the analysis of the framework and the optimization of the parameters it uses. We use the technique to derive parameterized approximation algorithm for several vertex deletion problems, including Feedback Vertex Set, $d$-Hitting Set and $\ell$-Path Vertex Cover. In particular, for every approximation ratio $1<\beta<2$, we attain a parameterized $\beta$-approximation for Feedback Vertex Set which is faster than the parameterized $\beta$-approximation of [Jana, Lokshtanov, Mandal, Rai and Saurabh, MFCS 23']. Furthermore, our algorithms are always faster than the algorithms attained using Fidelity Preserving Transformations [Fellows, Kulik, Rosamond, and Shachnai, JCSS 18'].

We study the $d$-dimensional knapsack problem. We are given a set of items, each with a $d$-dimensional cost vector and a profit, along with a $d$-dimensional budget vector. The goal is to select a set of items that do not exceed the budget in all dimensions and maximize the total profit. A PTAS with running time $n^{\Theta(d/\varepsilon)}$ has long been known for this problem, where $\varepsilon$ is the error parameter and $n$ is the encoding size. Despite decades of active research, the best running time of a PTAS has remained $O(n^{\lceil d/\varepsilon \rceil - d})$. Unfortunately, existing lower bounds only cover the special case with two dimensions $d = 2$, and do not answer whether there is a $n^{o(d/\varepsilon)}$-time PTAS for larger values of $d$. The status of exact algorithms is similar: there is a simple $O(n \cdot W^d)$-time (exact) dynamic programming algorithm, where $W$ is the maximum budget, but there is no lower bound which explains the strong exponential dependence on $d$. In this work, we show that the running times of the best-known PTAS and exact algorithm cannot be improved up to a polylogarithmic factor assuming Gap-ETH. Our techniques are based on a robust reduction from 2-CSP, which embeds 2-CSP constraints into a desired number of dimensions, exhibiting tight trade-off between $d$ and $\varepsilon$ for most regimes of the parameters. Informally, we obtain the following main results for $d$-dimensional knapsack. No $n^{o(d/\varepsilon \cdot 1/(\log(d/\varepsilon))^2)}$-time $(1-\varepsilon)$-approximation for every $\varepsilon = O(1/\log d)$. No $(n+W)^{o(d/\log d)}$-time exact algorithm (assuming ETH). No $n^{o(\sqrt{d})}$-time $(1-\varepsilon)$-approximation for constant $\varepsilon$. $(d \cdot \log W)^{O(d^2)} + n^{O(1)}$-time $\Omega(1/\sqrt{d})$-approximation and a matching $n^{O(1)}$-time lower~bound.

In the Unsplittable Flow on a Path problem UFP, we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a subpath. Our goal is to select a maximum profit subset of tasks such that the total demand of the selected tasks that use each edge $e$ is at most the capacity of $e$. Bag-UFP is the generalization of UFP where tasks are partitioned into bags, and we are allowed to select at most one task per bag. UFP admits a PTAS [Grandoni,M{\"o}mke,Wiese'22] but not an EPTAS [Wiese'17]. Bag-UFP is APX-hard [Spieksma'99] and the current best approximation is $O(\log n/\log\log n)$ [Grandoni,Ingala,Uniyal'15], where $n$ is the number of tasks. In this paper, we study the mentioned two problems when parameterized by the number $m$ of edges in the graph, with the goal of designing faster parameterized approximation algorithms. We present a parameterized EPTAS for Bag-UFP, and a substantially faster parameterized EPTAS for UFP (which is an FPTAS for $m=O(1)$). We also show that a parameterized FPTAS for UFP (hence for BagUFP) does not exist, therefore our results are qualitatively tight.

Transition states (TSs) are transient structures that are key in understanding reaction mechanisms and designing catalysts but challenging to be captured in experiments. Alternatively, many optimization algorithms have been developed to search for TSs computationally. Yet the cost of these algorithms driven by quantum chemistry methods (usually density functional theory) is still high, posing challenges for their applications in building large reaction networks for reaction exploration. Here we developed React-OT, an optimal transport approach for generating unique TS structures from reactants and products. React-OT generates highly accurate TS structures with a median structural root mean square deviation (RMSD) of 0.053{\AA} and median barrier height error of 1.06 kcal/mol requiring only 0.4 second per reaction. The RMSD and barrier height error is further improved by roughly 25\% through pretraining React-OT on a large reaction dataset obtained with a lower level of theory, GFN2-xTB. We envision that the remarkable accuracy and rapid inference of React-OT will be highly useful when integrated with the current high-throughput TS search workflow. This integration will facilitate the exploration of chemical reactions with unknown mechanisms.

Metal-organic frameworks (MOFs) are promising materials for gas sensing but are often limited to single-use detection. We demonstrate a hybridization strategy synergistically deploying conductive MOFs (cMOFs) and conductive polymers (cPs) as two complementary mixed ionic-electronic conductors in high-performing stand-alone chemiresistors. Our work presents significant improvement in i) sensor recovery kinetics, ii) cycling stability, and iii) dynamic range at room temperature. We demonstrate the effect of hybridization across well-studied cMOFs based on 2,3,6,7,10,11-hexahydroxytriphenylene (HHTP) and 2,3,6,7,10,11-hexaiminotripphenylene (HITP) ligands with varied metal nodes (Co, Cu, Ni). We conduct a comprehensive mechanistic study to relate energy band alignments at the heterojunctions between the MOFs and the polymer with sensing thermodynamics and binding kinetics. Our findings reveal that hole enrichment of the cMOF component upon hybridization leads to selective enhancement in desorption kinetics, enabling significantly improved sensor recovery at room temperature, and thus long-term response retention. This mechanism was further supported by density functional theory calculations on sorbate-analyte interactions. We also find that alloying cPs and cMOFs enables facile thin film co-processing and device integration, potentially unlocking the use of these hybrid conductors in diverse electronic applications.

Higher-order topological insulators (HOTIs) are unique materials hosting topologically protected states, whose dimensionality is at least by a factor of 2 lower than that of the bulk. Topological states in such insulators may be strongly confined in their corners that leads to considerable enhancement of nonlinear processes involving such states. However, all nonlinear HOTIs demonstrated so far were built on periodic bulk lattice materials. Here we demonstrate first \textit{nonlinear photonic} HOTI with the fractal origin. Despite their fractional effective dimensionality, the HOTIs constructed here on two different types of the Sierpi\'nski gasket waveguide arrays, may support topological corner states for unexpectedly wide range of coupling strengths, even in parameter regions where conventional HOTIs become trivial. We demonstrate thresholdless solitons bifurcating from corner states in nonlinear fractal HOTIs and show that their localization can be efficiently controlled by the input beam power. We observe sharp differences in nonlinear light localization on outer and multiple inner corners and edges representative for these fractal materials. Our findings not only represent a new paradigm for nonlinear topological insulators, but also open new avenues for potential applications of fractal materials to control the light flow., Comment: 10 pages, 5 figures

Broadband correlated photon pairs (biphotons) are valuable in quantum metrology, but current generation methods either involve complex nonlinear structures or lack sufficient bandwidth and brightness. In this work, we theoretically describe and experimentally demonstrate a novel technique for generation of a bright collinear biphoton field with a broad spectrum, achieved by using a tightly focused pump in a bulk nonlinear crystal. As the most straightforward application of the source, we employ Michelson interferometer-based quantum optical coherence tomography (QOCT). Utilizing the source enables the demonstration of record resolution and dispersion cancellation for this QOCT scheme., Comment: 7 pages, 4 figures

A space-filling curve (SFC) maps points in a multi-dimensional space to one-dimensional points by discretizing the multi-dimensional space into cells and imposing a linear order on the cells. This way, an SFC enables the indexing of multi-dimensional data using a one-dimensional index such as a B+-tree. Choosing an appropriate SFC is crucial, as different SFCs have different effects on query performance. Currently, there are two primary strategies: 1) deterministic schemes, which are computationally efficient but often yield suboptimal query performance, and 2) dynamic schemes, which consider a broad range of candidate SFCs based on cost functions but incur significant computational overhead. Despite these strategies, existing methods cannot efficiently measure the effectiveness of SFCs under heavy query workloads and numerous SFC options. To address this problem, we propose means of constant-time cost estimations that can enhance existing SFC selection algorithms, enabling them to learn more effective SFCs. Additionally, we propose an SFC learning method that leverages reinforcement learning and our cost estimation to choose an SFC pattern efficiently. Experimental studies offer evidence of the effectiveness and efficiency of the proposed means of cost estimation and SFC learning.

The $K^{+} \to \pi^{+}\pi^{0}\pi^{0}\gamma$ decay is observed by the OKA collaboration. The branching ratio is measured to be $(4.1 \pm 0.9(stat) \pm 0.4(syst))\times 10^{-6}$. The branching ratio and $\gamma$ energy spectrum are consistent with ChPT prediction., Comment: arXiv admin note: text overlap with arXiv:2310.16429

A high statistics data sample of the $K^{+}$ decays is recorded by the OKA collaboration. A missing mass analysis is performed to search for a light invisible pseudoscalar axion-like particle (ALP) $a$ in the decay $K^{+} \to \pi^{+} \pi^{0} a$. No signal is observed, the upper limits for the branching ratio of the decay are calculated. The $90\%$ confidence level upper limit is changing from $2.5\cdot10^{-6}$ to $2\cdot10^{-7}$ for the ALP mass from 0 to 200 MeV/$c^{2}$, except for the region of $\pi^{0}$ mass, where the upper limit is $4.4\cdot10^{-6}$., Comment: 6 pages, 6 figures

We carried out a sensitive survey of C$_2$ and C$_3$ using the EDIBLES data set. We also expanded our searches to C$_4$, C$_5$, and $^{13}$C$^{12}$C isotopologue in the most molecule-rich sightlines. We fit synthetic spectra generated following a physical excitation model to the C$_2$ (2-0) Phillips band to obtain the C$_2$ column density ($N$) as well as the kinetic temperature ($T_\textrm{kin}$) and number density ($n$) of the host cloud. The C$_3$ molecule was measured through its $\tilde{A} - \tilde{X}$ (000-000) electronic origin band system. We simulated the excitation of this band with a double-temperature Boltzmann distribution. We present the largest combined survey of C$_2$ and C$_3$ to date in which the individual transitions can be resolved. In total we detected C$_2$ in 51 velocity components along 40 sightlines, and C$_3$ in 31 velocity components along 27 sightlines. The two molecules are detected in the same velocity components. We find a very good correlation between $N$(C$_2$) and $N$(C$_3$) with Pearson $r = 0.93$ and an average $N$(C$_2$)/$N$(C$_3$) ratio of 15.5$\pm$1.4. A comparison with the behaviour of the C$_2$ DIBs shows that there are no clear differences among sightlines with and without detection of C$_2$ and C$_3$. This is in direct contrast to the better-studied non-C$_2$ DIBs who have reduced strengths in molecule-rich environments. We also identify for the first time the $Q$(2), $Q$(3), and $Q$(4) transitions of the $^{13}$C$^{12}$C (2-0) Phillips band in a stacked average spectrum, and estimate the isotopic ratio of carbon $^{12}$C/$^{13}$C as 79$\pm$8. Our search for the C$_4$ and C$_5$ optical bands was unsuccessful., Comment: 31 pages, 23 figures. To appear in A&A

We consider disjoint and sliding blocks estimators of cluster indices for multivariate, regularly varying time series in the Peak-over-Threshold framework. We aim to provide a complete description of the limiting behaviour of these estimators. This is achieved by a precise expansion for the difference between the sliding and the disjoint blocks statistics. The rates in the expansion stem from internal clusters and boundary clusters. To obtain these rates we need to extend the existing results on vague convergence of cluster measures. We reveal dichotomous behaviour between small blocks and large blocks scenario., Comment: 52 pages

A blocks method is used to define clusters of extreme values in stationary time series. The cluster starts at the first large value in the block and ends at the last one. The block cluster measure (the point measure at clusters) encodes different aspects of extremal properties. Its limiting behaviour is handled by vague convergence, hence the set of test functions consists of bounded, shift-invariant functionals that vanish around zero. If unbounded or non shift-invariant functionals are considered, we may obtain convergence at a different rate, depending on the type of the functional and the block size (small vs. large blocks). There are two prominent examples of such functionals: the locations of large jumps and the cluster length. We obtain a comprehensive characterization of the limiting behaviour of the block cluster measure evaluated at such functionals for stationary, regularly varying time series. Once the convergence of the block cluster measure is established, we can proceed with consistency of the empirical cluster measure. Consistency holds in the small and moderate blocks scenario, while fails in the large blocks situation. Next, we continue with weak convergence of the empirical cluster processes. The starting point is the seminal paper by Drees and Rootzen (2010). Under the appropriate uniform integrability condition (related to small blocks) the results in the latter paper are still valid. In the moderate and large blocks scenario, the Drees and Rootzen empirical cluster process diverges, but converges weakly when re-normalized properly., Comment: 35 pages

In a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algorithms, polynomial-time approximation algorithms and, more generally, parameterized approximation algorithms. In this work, we generalize those results to the weighted setting. More formally, we consider monotone subset minimization problems over a weighted universe of size $n$ (e.g., Vertex Cover, $d$-Hitting Set and Feedback Vertex Set). We consider a model where the algorithm is only given access to a subroutine that finds a solution of weight at most $\alpha \cdot W$ (and of arbitrary cardinality) in time $c^k \cdot n^{O(1)}$ where $W$ is the minimum weight of a solution of cardinality at most $k$. In the unweighted setting, Esmer et al. determine the smallest value $d$ for which a $\beta$-approximation algorithm running in time $d^n \cdot n^{O(1)}$ can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: for every fixed $\varepsilon>0$ we obtain a $\beta$-approximation algorithm running in time $O\left((d+\varepsilon)^{n}\right)$, for the same $d$ as in the unweighted setting. Similarly, we also extend a $\beta$-approximate brute-force search (in a model which only provides access to a membership oracle) to the weighted setting. Using existing approximation algorithms and exact parameterized algorithms for weighted problems, we obtain the first exponential-time $\beta$-approximation algorithms that are better than brute force for a variety of problems including Weighted Vertex Cover, Weighted $d$-Hitting Set, Weighted Feedback Vertex Set and Weighted Multicut.

This report describes the state of the art in verifiable computation. The problem being solved is the following: The Verifiable Computation Problem (Verifiable Computing Problem) Suppose we have two computing agents. The first agent is the verifier, and the second agent is the prover. The verifier wants the prover to perform a computation. The verifier sends a description of the computation to the prover. Once the prover has completed the task, the prover returns the output to the verifier. The output will contain proof. The verifier can use this proof to check if the prover computed the output correctly. The check is not required to verify the algorithm used in the computation. Instead, it is a check that the prover computed the output using the computation specified by the verifier. The effort required for the check should be much less than that required to perform the computation. This state-of-the-art report surveys 128 papers from the literature comprising more than 4,000 pages. Other papers and books were surveyed but were omitted. The papers surveyed were overwhelmingly mathematical. We have summarised the major concepts that form the foundations for verifiable computation. The report contains two main sections. The first, larger section covers the theoretical foundations for probabilistically checkable and zero-knowledge proofs. The second section contains a description of the current practice in verifiable computation. Two further reports will cover (i) military applications of verifiable computation and (ii) a collection of technical demonstrators. The first of these is intended to be read by those who want to know what applications are enabled by the current state of the art in verifiable computation. The second is for those who want to see practical tools and conduct experiments themselves., Comment: 54 pages

We introduce a programmable 8-port interferometer with the recently proposed error-tolerant architecture capable of performing a broad class of transformations. The interferometer has been fabricated with femtosecond laser writing and it is the largest programmable interferometer of this kind to date. We have demonstrated its advantageous error tolerance by showing an operation in a broad wavelength range from $920$ to $980$ nm, which is particularly relevant for quantum photonics due to efficient photon sources. Our work highlights the importance of developing novel architectures of programmable photonics for information processing., Comment: 14 pages, 11 figures, 1 Table

In [Math. Oper. Res., 2011], Fleischer et al. introduced a powerful technique for solving the generic class of separable assignment problems (SAP), in which a set of items of given values and weights needs to be packed into a set of bins subject to separable assignment constraints, so as to maximize the total value. The approach of Fleischer at al. relies on solving a configuration LP and sampling a configuration for each bin independently based on the LP solution. While there is a SAP variant for which this approach yields the best possible approximation ratio, for various special cases, there are discrepancies between the approximation ratios obtained using the above approach and the state-of-the-art approximations. This raises the following natural question: Can we do better by iteratively solving the configuration LP and sampling a few bins at a time? To assess the potential gain from iterative randomized rounding, we consider as a case study one interesting SAP variant, namely, Uniform Cardinality Constrained Multiple Knapsack, for which we answer this question affirmatively. The input is a set of items, each has a value and a weight, and a set of uniform capacity bins. The goal is to assign a subset of the items of maximum total value to the bins such that $(i)$ the capacity of any bin is not exceeded, and $(ii)$ the number of items assigned to each bin satisfies a given cardinality constraint. While the technique of Fleischer et al. yields a $\left(1-\frac{1}{e}\right)$-approximation for the problem, we show that iterative randomized rounding leads to an efficient polynomial time approximation scheme (EPTAS), thus essentially resolving the complexity status of the problem. Our analysis of iterative randomized rounding can be useful for solving other SAP variants.

The quantum Zeno effect refers to slowing down of the decay of a quantum system that is affected by frequent measurements. Nowadays, the significance of this paradigm is extended far beyond quantum systems, where it was introduced, finding physical and mathematical analogies in such phenomena as the suppression of output beam decay by sufficiently strong absorption introduced in guiding optical systems. In the latter case, the effect is often termed as macroscopic Zeno effect. Recent studies in optics, where enhanced transparency of the entire system was observed upon the increase of the absorption, were largely focused on the systems obeying parity-time symmetry, hence, the observed effect was attributed to the symmetry breaking. While manifesting certain similarities in the behavior of the transparency of the system with the mentioned studies, the macroscopic Zeno phenomenon reported here in topological photonic system is far more general in nature. In particular, we show that it does not require the existence of exceptional points, and that it is based on the suppression of decay for only a subspace of modes that can propagate in the system, alike the quantum Zeno dynamics. By introducing controlled losses in one of the arms of a topological insulator comprising two closely positioned Su-Schrieffer-Heeger arrays, we demonstrate the macroscopic Zeno effect, which manifests itself in an increase of the transparency of the system with respect to the topological modes created at the interface between two arrays. The phenomenon remains robust against disorder in the non-Hermitian topological regime. In contrast, coupling a topological array with a non-topological one results in a monotonic decrease in output power with increasing absorption.

Floquet systems with periodically varying in time parameters enable realization of unconventional topological phases that do not exist in static systems with constant parameters and that are frequently accompanied by appearance of novel types of the topological states. Among such Floquet systems are the Su-Schrieffer-Heeger lattices with periodically-modulated couplings that can support at their edges anomalous $\pi$ modes of topological origin despite the fact that the lattice spends only half of the evolution period in topologically nontrivial phase, while during other half-period it is topologically trivial. Here, using Su-Schrieffer-Heeger arrays composed from periodically oscillating waveguides inscribed in transparent nonlinear optical medium, we report experimental observation of photonic anomalous $\pi$ modes residing at the edge or in the corner of the one- or two-dimensional arrays, respectively, and demonstrate a new class of topological $\pi$ solitons bifurcating from such modes in the topological gap of the Floquet spectrum at high powers. $\pi$ solitons reported here are strongly oscillating nonlinear Floquet states exactly reproducing their profiles after each longitudinal period of the structure. They can be dynamically stable in both one- and two-dimensional oscillating waveguide arrays, the latter ones representing the first realization of the Floquet photonic higher-order topological insulator, while localization properties of such $\pi$ solitons are determined by their power., Comment: 10 pages, 6 figures, to appear in Science Bulletin

We study a family of matroid optimization problems with a linear constraint (MOL). In these problems, we seek a subset of elements which optimizes (i.e., maximizes or minimizes) a linear objective function subject to (i) a matroid independent set, or a matroid basis constraint, (ii) additional linear constraint. A notable member in this family is budgeted matroid independent set (BM), which can be viewed as classic $0/1$-knapsack with a matroid constraint. While special cases of BM, such as knapsack with cardinality constraint and multiple-choice knapsack, admit a fully polynomial-time approximation scheme (Fully PTAS), the best known result for BM on a general matroid is an Efficient PTAS. Prior to this work, the existence of a Fully PTAS for BM, and more generally, for any problem in the family of MOL problems, has been open. In this paper, we answer this question negatively by showing that none of the (non-trivial) problems in this family admits a Fully PTAS. This resolves the complexity status of several well studied problems. Our main result is obtained by showing first that exact weight matroid basis (EMB) does not admit a pseudo-polynomial time algorithm. This distinguishes EMB from the special cases of $k$-subset sum and EMB on a linear matroid, which are solvable in pseudo-polynomial time. We then obtain unconditional hardness results for the family of MOL problems in the oracle model (even if randomization is allowed), and show that the same results hold when the matroids are encoded as part of the input, assuming $P \neq NP$. For the hardness proof of EMB, we introduce the $\Pi$-matroid family. This intricate subclass of matroids, which exploits the interaction between a weight function and the matroid constraint, may find use in tackling other matroid optimization problems.

We present Pathway, a new unified data processing framework that can run workloads on both bounded and unbounded data streams. The framework was created with the original motivation of resolving challenges faced when analyzing and processing data from the physical economy, including streams of data generated by IoT and enterprise systems. These required rapid reaction while calling for the application of advanced computation paradigms (machinelearning-powered analytics, contextual analysis, and other elements of complex event processing). Pathway is equipped with a Table API tailored for Python and Python/SQL workflows, and is powered by a distributed incremental dataflow in Rust. We describe the system and present benchmarking results which demonstrate its capabilities in both batch and streaming contexts, where it is able to surpass state-of-the-art industry frameworks in both scenarios. We also discuss streaming use cases handled by Pathway which cannot be easily resolved with state-of-the-art industry frameworks, such as streaming iterative graph algorithms (PageRank, etc.).

We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an $\ell$-matchoid $\cm$ on a ground set $E$, a profit function $p:E \rightarrow \mathbb{R}_{\geq 0}$, a cost function $c:E \rightarrow \mathbb{R}_{\geq 0}$, and a budget $B \in \mathbb{R}_{\geq 0}$, the goal is to find in the $\ell$-matchoid a feasible set $S$ of maximum profit $p(S)$ subject to the budget constraint, i.e., $c(S) \leq B$. The {\em budgeted $\ell$-matchoid} (BM) problem includes as special cases budgeted $\ell$-dimensional matching and budgeted $\ell$-matroid intersection. A strong motivation for studying BM from parameterized viewpoint comes from the APX-hardness of unbudgeted $\ell$-dimensional matching (i.e., $B = \infty$) already for $\ell = 3$. Nevertheless, while there are known FPT algorithms for the unbudgeted variants of the above problems, the {\em budgeted} variants are studied here for the first time through the lens of parameterized complexity. We show that BM parametrized by solution size is $W[1]$-hard, already with a degenerate single matroid constraint. Thus, an exact parameterized algorithm is unlikely to exist, motivating the study of {\em FPT-approximation schemes} (FPAS). Our main result is an FPAS for BM (implying an FPAS for $\ell$-dimensional matching and budgeted $\ell$-matroid intersection), relying on the notion of representative set $-$ a small cardinality subset of elements which preserves the optimum up to a small factor. We also give a lower bound on the minimum possible size of a representative set which can be computed in polynomial time.

We study the uniform $2$-dimensional vector multiple knapsack (2VMK) problem, a natural variant of multiple knapsack arising in real-world applications such as virtual machine placement. The input for 2VMK is a set of items, each associated with a $2$-dimensional weight vector and a positive profit, along with $m$ $2$-dimensional bins of uniform (unit) capacity in each dimension. The goal is to find an assignment of a subset of the items to the bins, such that the total weight of items assigned to a single bin is at most one in each dimension, and the total profit is maximized. Our main result is a $(1- \frac{\ln 2}{2} - \varepsilon)$-approximation algorithm for 2VMK, for every fixed $\varepsilon > 0$, thus improving the best known ratio of $(1 - \frac{1}{e}-\varepsilon)$ which follows as a special case from a result of [Fleischer at al., MOR 2011]. Our algorithm relies on an adaptation of the Round$\&$Approx framework of [Bansal et al., SICOMP 2010], originally designed for set covering problems, to maximization problems. The algorithm uses randomized rounding of a configuration-LP solution to assign items to $\approx m\cdot \ln 2 \approx 0.693\cdot m$ of the bins, followed by a reduction to the ($1$-dimensional) Multiple Knapsack problem for assigning items to the remaining bins.

The goal of this paper is to understand how exponential-time approximation algorithms can be obtained from existing polynomial-time approximation algorithms, existing parameterized exact algorithms, and existing parameterized approximation algorithms. More formally, we consider a monotone subset minimization problem over a universe of size $n$ (e.g., Vertex Cover or Feedback Vertex Set). We have access to an algorithm that finds an $\alpha$-approximate solution in time $c^k \cdot n^{O(1)}$ if a solution of size $k$ exists (and more generally, an extension algorithm that can approximate in a similar way if a set can be extended to a solution with $k$ further elements). Our goal is to obtain a $d^n \cdot n^{O(1)}$ time $\beta$-approximation algorithm for the problem with $d$ as small as possible. That is, for every fixed $\alpha,c,\beta \geq 1$, we would like to determine the smallest possible $d$ that can be achieved in a model where our problem-specific knowledge is limited to checking the feasibility of a solution and invoking the $\alpha$-approximate extension algorithm. Our results completely resolve this question: (1) For every fixed $\alpha,c,\beta \geq 1$, a simple algorithm (``approximate monotone local search'') achieves the optimum value of $d$. (2) Given $\alpha,c,\beta \geq 1$, we can efficiently compute the optimum $d$ up to any precision $\varepsilon > 0$. Earlier work presented algorithms (but no lower bounds) for the special case $\alpha = \beta = 1$ [Fomin et al., J. ACM 2019] and for the special case $\alpha = \beta > 1$ [Esmer et al., ESA 2022]. Our work generalizes these results and in particular confirms that the earlier algorithms are optimal in these special cases., Comment: 80 pages, 5 figures

We study the statistical properties of a gas of interacting bosons trapped in a box potential in two and three dimensions. Our primary focus is the characteristic temperature $\tchar$, i.e. the temperature at which the fluctuations of the number of condensed atoms (or, in 2D, the number of motionless atoms) is maximal. Using the Fock State Sampling method, we show that $\tchar$ increases due to interaction. In 3D, this temperature converges to the critical temperature in the thermodynamic limit. In 2D we show the general applicability of the method by obtaining a generalized dependence of the characteristic temperature on the interaction strength. Finally, we discuss the experimental conditions necessary for the verification of our theoretical predictions., Comment: This article belongs to the special issue of Acta Physica Polonica A printed in honor of Professor Iwo Bialynicki-Birula on the occasion of his 90th birthday (Ed. Tomasz Sowinski, DOI:10.12693/APhysPolA.143.S0)

In the present work, we study the experimental data on the root mean square charge radii of the spherical atomic nuclei. The purpose of this analysis is to clarify what is the manifestation of the neutron shells in the considered observable and to find regularities in the behavior of the charge radii when a shell neutron is crossed. As the result, we have found manifestations of the shells N_sh=8,28,50 and 82. It turns out that the well-known shells with the neutron numbers 20 and 126 do not show up. The present analysis is performed by means of the relative charge radius x(N,N_sh,Z). This value is equal to the charge radius of a given isotope over the charge radius of the isotope of the given element with the closed neutron shell. It is shown that the values of x form groups corresponding to different values of N_sh. Prediction for unknown charge radius of sulfur-30 has been made.

We study both, experimentally and theoretically, propagation of light in the fs-laser written rotating square waveguide arrays and present the first experimental evidence of light localization induced by the rotation of periodic structure in the direction of light propagation. Such linear light localization occurs either in the corners of truncated square array, where it results from the interplay between the centrifugal effect and total internal reflection at the borders of truncated array, or in the center of array, where rotation creates effective attractive optical potential. The degree of localization of linear bulk and corner modes emerging due to the rotation increases with the increase of rotation frequency. Consequently, corner and bulk solitons in rotating wave-guide arrays become thresholdless for sufficiently large rotation frequencies, in contrast to solitons in non-rotating arrays that exist only above power threshold. Focusing nonlinearity enhances localization degree of corner modes, but surprising initially it leads to broadening of bulk nonlinear states, followed by their re-localization at high input powers. Our results open new prospects for control of evolution of nonlinear multidimensional excitations by dynamically varying potentials., Comment: 7 pages, 5 figures, to be appear on ACS Photonics

We study the budgeted laminar matroid independent set problem. The input is a ground set, where each element has a cost and a non-negative profit, along with a laminar matroid over the elements and a budget. The goal is to select a maximum profit independent set of the matroid whose total cost is bounded by the budget. Several well known special cases, where we have, e.g., no matroid constraint (the classic knapsack problem) or a uniform matroid constraint (knapsack with a cardinality constraint), admit a fully polynomial-time approximation scheme (FPTAS). In contrast, the budgeted matroid independent set (BMI) problem with a general matroid has an efficient polynomial-time approximation scheme (EPTAS) but does not admit an FPTAS. This implies an EPTAS for our problem, which is the best known result prior to this work. We present an FPTAS for budgeted laminar matroid independent set, improving the previous EPTAS for this matroid family and generalizing the FPTAS known for knapsack with a cardinality constraint and multiple-choice knapsack. Our scheme is based on a simple dynamic program which utilizes the tree-like structure of laminar matroids.

Introduction of controllable deformations into periodic materials that lead to disclinations in their structure opens novel routes for construction of higher-order topological insulators hosting topological states at disclinations. Appearance of these topological states is consistent with the bulk-disclination correspondence principle, and is due to the filling anomaly that results in fractional charges to the boundary unit cells. So far, topological disclination states were observed only in the linear regime, while the interplay between nonlinearity and topology in the systems with disclinations has been never studied experimentally. We report here bon the experimental observation of the nonlinear photonic disclination states in waveguide arrays with pentagonal or heptagonal disclination cores inscribed in transparent optical medium using the fs-laser writing technique. The transition between nontopological and topological phases in such structures is controlled by the Kekul\'e distortion coefficient $r$ with topological phase hosting simultaneously disclination states at the inner disclination core and spatially separated from them corner, zero-energy, and extended edge states at the outer edge of the structure. We show that the robust nonlinear disclination states bifurcate from their linear counterparts and that location of their propagation constants in the gap and, hence, their spatial localization can be controlled by their power. Nonlinear disclination states can be efficiently excited by Gaussian input beams, but only if they are focused into the waveguides belonging to the disclination core, where such topological states reside., Comment: 11 pages, 6 figures

The rapid development and application of foundation models have revolutionized the field of artificial intelligence. Large diffusion models have gained significant attention for their ability to generate photorealistic images and support various tasks. On-device deployment of these models provides benefits such as lower server costs, offline functionality, and improved user privacy. However, common large diffusion models have over 1 billion parameters and pose challenges due to restricted computational and memory resources on devices. We present a series of implementation optimizations for large diffusion models that achieve the fastest reported inference latency to-date (under 12 seconds for Stable Diffusion 1.4 without int8 quantization on Samsung S23 Ultra for a 512x512 image with 20 iterations) on GPU-equipped mobile devices. These enhancements broaden the applicability of generative AI and improve the overall user experience across a wide range of devices., Comment: 4 pages (not including references), 2 figures, 2 tables. Accepted to Efficient Deep Learning for Computer Vision workshop 2023

We report a design and implementation of a resource-efficient spatial demultiplexer which produces 4 indistinguishable photons with efficiency of 39.7% per channel. Our scheme is based on a free-space storage/delay line which accumulates 4 photons and releases them by a controlled polarization rotation using a single Pockels cell., Comment: 8 pages, 7 figures

Transition state (TS) search is key in chemistry for elucidating reaction mechanisms and exploring reaction networks. The search for accurate 3D TS structures, however, requires numerous computationally intensive quantum chemistry calculations due to the complexity of potential energy surfaces. Here, we developed an object-aware SE(3) equivariant diffusion model that satisfies all physical symmetries and constraints for generating sets of structures - reactant, TS, and product - in an elementary reaction. Provided reactant and product, this model generates a TS structure in seconds instead of hours required when performing quantum chemistry-based optimizations. The generated TS structures achieve a median of 0.08 {\AA} root mean square deviation compared to the true TS. With a confidence scoring model for uncertainty quantification, we approach an accuracy required for reaction rate estimation (2.6 kcal/mol) by only performing quantum chemistry-based optimizations on 14\% of the most challenging reactions. We envision the proposed approach useful in constructing large reaction networks with unknown mechanisms., Comment: 5 figures and 1 table

An ensemble of neutral excitations is constructed experimentally in the Laughlin liquid at the electron filling factor 1/3. The excitations are found to induce a nonlinear optical response, manifested as a quadratic dependence of the reflection signal on the excitation power. The reported experimental results indicate that the observed effect is due to the contribution of the coherent anti-Stokes-Stokes scattering of light from the excited Laughlin liquid., Comment: 5 two-column pages, 4 figures

We study the budgeted versions of the well known matching and matroid intersection problems. While both problems admit a polynomial-time approximation scheme (PTAS) [Berger et al. (Math. Programming, 2011), Chekuri, Vondrak and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit a fully PTAS (FPTAS), or even an efficient PTAS (EPTAS). In this paper we answer the second part of this question affirmatively, by presenting an EPTAS for budgeted matching and budgeted matroid intersection. A main component of our scheme is a novel construction of representative sets for desired solutions, whose cardinality depends only on $\varepsilon$, the accuracy parameter. Thus, enumerating over solutions within a representative set leads to an EPTAS. This crucially distinguishes our algorithms from previous approaches, which rely on exhaustive enumeration over the solution set. Our ideas for constructing representative sets may find use in tackling other budgeted optimization problems, and are thus of independent interest.

We observe linear and nonlinear light localization at the edges and in the corners of truncated moir\'e lattices created by the superposition of periodic mutually-twisted at Pythagorean angles square sublattices. Experimentally exciting corner linear modes in the fs-laser written moir\'e lattices we find drastic differences in their localization properties in comparison with the bulk excitations. We also address the impact of nonlinearity on the corner and bulk modes and experimentally observe the crossover from linear quasi-localized states to the surface solitons emerging at the higher input powers. Our results constitute the first experimental demonstration of localization phenomena induced by truncation of periodic moir\'e structures in photonic systems., Comment: 5 pages, 4 figures, to appear in Physical Review Letters

We present an algorithm of quantum engineering of large-amplitude>5 high-fidelity>0.99 even/odd Schrodinger cat states (SCSs) using a single mode squeezed vacuum (SMSV) state as resource. Set of k beam splitters (BSs) with arbitrary transmittance and reflectance coefficients sequentially following each other acts as a hub that redirects a multiphoton state into the measuring modes simultaneously measured by photon number resolving (PNR) detectors. We show that the multiphoton state splitting guarantees significant increase of the success probability of the cat state generator compared to its implementation in a single PNR detector version and imposes less requirements on ideal PNR detectors. We prove that the fidelity of the output SCSs and its success probability are in conflict with each other (which can be quantified) in a scheme with ineffective PNR detectors, especially when subtracting large (say, 100) number of photons, i.e., increasing the fidelity to perfect values leads to a sharp decrease in the success probability. In general, the strategy of subtracting up to 20 photons from initial SMSV in setup with two BSs is acceptable for achieving sufficiently high values of the fidelity and success probability at the output of the generator of the SCSs of amplitude <3 with two inefficient PNR detectors., Comment: 19 pages and 5 figures