26838 research outputs found
Sort by
Asymptotic bounds on the combinatorial diameter of random polytopes
No full textThe combinatorial diameter diam(P) of a polytope P is the maximum shortest path distance between any pair of vertices, where length is measured by the number of edges in the path. In this paper, we provide upper and lower bounds on the combinatorial diameter of a random “spherical” polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension. More precisely, for an n-dimensional polytope P defined by the intersection of m independent and identically distributed half-spaces whose supporting normals are chosen uniformly from the sphere, we show that diam(P) is Ω(nm1n-1) and O(n2m1n-1+n84n) with high probability when m≥2Ω(n)
A novel bio-inspired encoding for evolving cryptographic Boolean functions
No full textDiscovering Boolean functions that satisfy properties such as balancedness and nonlinearity is a complex optimization problem, which is crucial to important cryptographic constructions like block and stream ciphers. The difficulty of this problem lies in the search space growing super-exponentially in the number of variables. Evolutionary approaches, including Genetic Algorithms (GAs) and Genetic Programming (GP), have been successfully applied to overcome this difficulty. The major drawback of these methods is that they evolve functions through encodings that are either exponential in the input size or hard to interpret. We address this problem as follows. (i) We propose a new encoding for Boolean functions as reaction systems, a bio-inspired computational model which can be directly translated into the compact and easily interpretable Disjunctive Normal Form (DNF). (ii) We design EvoBRS, an evolutionary optimization framework that exploits this new representation to discover Boolean functions with maximum nonlinearity (bent functions), possibly under the balancedness constraint. (iii) We back up our novel paradigm with a refined theoretical analysis of independent interest. (iv) We conduct a rigorous experimental study, demonstrating that EvoBRS consistently discovers diverse, highly nonlinear Boolean functions with and without the balancedness constraint. EvoBRS proves particularly effective on balanced functions, successfully identifying balanced maximally nonlinear instances and outperforming both GP and state-of-the-art GAs. All the discovered functions are returned in a compact and easily interpretable DNF. A preliminary version of this work appeared in Ascone et al., GECCO 2025
Bidding in ancillary service markets: An analytical approach using extreme value theory
No full textTo enable the participation of stochastic distributed energy resources in ancillary service markets, the Danish transmission system operator, Energinet, mandates that flexibility providers satisfy a minimum 90% reliability requirement for reserve bids. This paper examines the bidding strategy of an electric vehicle aggregator under this regulation and develops a chance-constrained optimization model. In contrast to conventional sample-based approaches that demand large datasets to capture uncertainty, we propose an analytical reformulation that leverages extreme value theory to characterize the tail behavior of flexibility distributions. A case study with real-world charging data from 1400 residential electric vehicles in Denmark demonstrates that the analytical solution improves out-of-sample reliability, reducing bid violation rates by up to 8% relative to a sample-based benchmark. The method is also computationally more efficient, solving optimization problems up to 4.8 times faster while requiring substantially fewer samples to ensure compliance. Moreover, the proposed approach enables the construction of feasible bids with reliability levels as high as 99.95%, which would otherwise require prohibitively large scenario sets under the sample-based method. Beyond its computational and reliability advantages, the framework also provides actionable insights into how reliability thresholds influence aggregator bidding behavior and market participation. This study establishes a regulation-compliant, tractable, and risk-aware bidding methodology for stochastic flexibility aggregators, enhancing both market efficiency and power system security
Monogamy of highly symmetric states
No full textWe investigate the extent to which two particles can be maximally entangled when they are also similarly entangled with other particles on a complete graph, focusing on Werner, isotropic, and Brauer states. To address this, we formulate and solve optimization problems that draw on concepts from many-body physics, computational complexity, and quantum cryptography. We approach the problem by formalizing it as a semi-definite program (SDP), which we solve analytically using tools from representation theory. Notably, we determine the exact maximum values for the projection onto the maximally entangled state and the antisymmetric Werner state, thereby resolving long-standing open problems in the field of quantum extendibility. Our results are achieved by leveraging SDP duality, the representation theory of symmetric, unitary and orthogonal groups, and the Brauer algebra
The reversible simulator – a data-driven approach for solving forward and inverse problems
Full text linkInverse problems are prevalent across various fields of science and engineering, with applications spanning medical imaging, materials science, nondestructive testing, astrophysics, climate science, and seismology. These problems share a common goal: estimating a quantity of interest from measurements obtained
under specific experimental conditions. Traditionally, simulation and inference have been considered separate tasks. However, recent advancements in conditional variational inference offer a promising approach to integrate these tasks within a single framework. This paper reviews some of these advancements in the context of linear inverse problems, focusing on the use of straightforward generative models for inference and experimental design in computed tomography
Subsequence covers of words
Full text linkWe introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word C is an s-cover of a word S if the occurrences of C in S as subsequences cover all the positions in S. The s-covers seem to be computationally much harder than standard covers of words (cf. Apostolico et al. (1991) [1]), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler (1984) [6]). We give a linear-time algorithm for testing if a candidate word C is an s-cover of a word S over a polynomially-bounded integer alphabet. We also give an algorithm for finding a shortest s-cover of a word S, which in the case of a constant-sized alphabet, also runs in linear time. The words without proper s-cover are called s-primitive. We complement our algorithmic results with explicit lower and an upper bound on the length of a longest s-primitive word. Both bounds are exponential in the size of the alphabet. The upper bound presented here improves the bound given in the conference version of this paper [SPIRE 2022]
Comparison of visual saliency for dynamic point clouds: Task-free vs. task-dependent
Full text linkThis paper presents a Task-Free eye-tracking dataset for Dynamic Point Clouds (TF-DPC) aimed at investigating visual attention. The dataset is composed of eye gaze and head movements collected from 24 participants observing 19 scanned dynamic point clouds in a Virtual Reality (VR) environment with 6 degrees of freedom. We compare the visual saliency maps generated from this dataset with those from a prior task-dependent experiment (focused on quality assessment) to explore how high-level tasks influence human visual attention. To measure the similarity between these visual saliency maps, we apply the well-known Pearson correlation coefficient and an adapted version of the Earth Mover's Distance metric, which takes into account both spatial information and the degrees of saliency. Our experimental results provide both qualitative and quantitative insights, revealing significant differences in visual attention due to task influence. This work enhances our understanding of the visual attention for dynamic point cloud (specifically human figures) in VR from gaze and human movement trajectories, and highlights the impact of task-dependent factors, offering valuable guidance for advancing visual saliency models and improving VR perception
On testing and learning quantum junta channels
Full text linkWe consider the problems of testing and learning quantum k-junta channels, which are n-qubit to n-qubit quantum channels acting non-trivially on at most k out of n qubits and leaving the rest of qubits unchanged. We show the following. 1) An O(k)-query algorithm to distinguish whether the given channel is k-junta channel or is far from any k-junta channels, and a lower bound Ω√(k) on the number of queries and 2) An O(4k)-query algorithm to learn a k-junta channel, and a lower bound Ω(4k/k) on the number of queries. This partially answers an open problem raised by (Chen et al. 2023). In order to settle these problems, we develop a Fourier analysis framework over the space of superoperators and prove several fundamental properties, which extends the Fourier analysis over the space of operators introduced in (Montanaro and Osborne, 2010). The distance metric we consider in this paper is obtained by Fourier analysis, which is essentially the L2-distance between Choi representations. Besides, we introduce Influence-Sample to replace Fourier-Sample proposed in(Atici and Servedio, 2007). Our Influence-Sample includes only single-qubit operations and results in only constant-factor decrease in efficiency
Scientific machine learning: A symbiosis
Full text linkThis editorial serves as a preface to the "Scientific Machine Learning" (SciML) special issue of the AIMS Foundations of Data Science journal. In this piece, we contend that SciML exists in a symbiotic relationship with the fields of computational science and engineering (CSE) and machine learning (ML). We highlight the progress (and limitations) of CSE and reflect on the recent successes of ML. While ML creates significant possibilities for advancing simulation techniques, it lacks the mathematical guarantees that are typically found in CSE. We argue that as SciML develops and embraces the remarkable capabilities of ML, it will support, not replace, traditional methods of CSE. We then overview some existing challenges and opportunities in this interdisciplinary field and close by introducing the special issue papers