International Journal of Foundations of Computer Science

Given a set P of red points and a set Q of blue points in the plane, of total size n, we investigate the problem of finding triangles with a given angle $𝜃$ that (a) contain all points of Q, (b) avoid all points of P, and (c) are minimal, i.e. their three sides are tangent to the convex hull of Q. Such triangles are called minimal separating $𝜃$-triangles. We give an algorithm for reporting all combinatorially different minimal separating $𝜃$-triangles in $O(nlogn)$ time.

We study the maximum speed of quantum computation and how it is affected by limitations on physical resources. We show how the resulting concepts generalize to a broader class of physical models of computation within dynamical systems and introduce a specific algebraic structure representing these speed limits. We derive a family of quantum speed limit results in resource-constrained quantum systems with pure states and a finite dimensional state space, by using a geometric method based on right invariant action functionals on $SU(N)$. We show that when the action functional is bi-invariant, the minimum time for implementing any quantum gate using a potentially time-dependent Hamiltonian is equal to the minimum time when using a constant Hamiltonian, thus constant Hamiltonians are time optimal for these constraints. We give an explicit formula for the time in these cases, in terms of the resource constraint. We show how our method produces a rich family of speed limit results, of which the generalized Margolus–Levitin theorem and the Mandelstam–Tamm inequality are special cases. We discuss the broader context of geometric approaches to speed limits in physical computation, including the way geometric approaches to quantum speed limits are a model for physical speed limits to computation arising from a limited resource.

A vulnerability parameter the neighbor rupture degree can be used to obtain the vulnerability of a spy network. The neighbor rupture degree of a noncomplete connected graph $G$ is defined to be

In this paper, we give constructions of several classes of Boolean functions with four-valued Walsh spectra, which are derived from the indirect sum construction. The Walsh spectra and spectrum distributions of these functions are determined. The result of functions with four-valued Walsh spectra derived from Bent functions is used to research Bent functions and o-polynomials. By investigating the indirect sum, we also give constructions of plateaued functions and functions with five-valued Walsh spectra.

We offer efficient and practical solutions of Yao’s millionaires’ problem without using any one-way functions. Some of the solutions involve physical principles, while others are purely mathematical. One of our solutions (based on physical principles) yields a public-key encryption protocol secure against (passive) computationally unbounded adversary. In that protocol, the legitimate parties are not assumed to be computationally unbounded.

Two-prime Sidelnikov sequence introduced by Brandstätter et al. in 2010 was shown to enjoy nice pseudorandom properties. It was shown to be balanced only in the case $p$ and $q$ are twin primes or $p$ and $q$ are cousin primes with $p\equiv q\equiv 3(mod4)$. In the case $gcd(p-1,q-1)=2$, where $p$ and $q$ are two distinct primes, a modification of the binary two-prime Sidelnikov sequence is proposed in this paper. We show that the new defined sequence is always balanced. And we also study the autocorrelation of the new defined sequence showing that it possesses nice autocorrelation feature.

The problem of two node-disjoint paths is to identify two paths ${{𝒬}}_1$ and ${{𝒬}}_2$ from source $s\in V$ to target $t\in V$ without any common intermediate node in a communication network $G=(V,E)$, where each node (vertex) in $V$ denotes a process and each edge $(p,q)\in E$ denotes a communication channel between nodes $p$ and $q$. In this paper, we present the first adaptive stabilizing algorithm for finding a pair of node-disjoint paths in a semi-anonymous arbitrary network in $O(D)$ rounds and the state-space complexity is $O(logD)$ bits per process, where $D$ is the diameter of the communication network. The algorithm assumes weakly fair distributed daemon and the knowledge of an upper bound on the number of processes by each process. If two disjoint paths exist between $s$ and $t$, two disjoint paths are guaranteed to be constructed. In addition, the algorithm detects if two node-disjoint paths exist or not. Since the proposed algorithm is stabilizing, it does not require initialization and is capable of withstanding transient faults. We view a fault that perturbs the state of the system but not its program as a transient fault. The proposed algorithm has a wide range of applications in ensuring reliability and security of sensor, mobile and fixed communication networks.