Search

Abstract: We introduce a new combinatorial auction format based on a simple, transparent pricing mechanism tailored for the hierarchical package structure proposed by Rothkopf, Pekeč, and Harstad to avoid computational complexity [Rothkopf, M., Pekeč, A., Harstad, R., 1998, Computationally manageable combinatorial auctions. Manage. Sci. 44, 1131–1147]. This combination provides the feedback necessary for bidders in multi-round auctions to discern winning bidding strategies for subsequent rounds and to coordinate responses to aggressive package bids. The resulting mechanism is compared to two leading alternatives in a series of laboratory experiments involving varying degrees of value synergies. Based on these “wind tunnel” tests the FCC has decided to use hierarchical package bidding in a segment of the upcoming 700 MHz auction. [ABSTRACT FROM AUTHOR]

Kidney exchange programs (KEPs) increase kidney transplantation by facilitating the exchange of incompatible donors. Increasing the scale of KEPs leads to more opportunities for transplants. Collaboration between transplant organizations (agents) is thus desirable. As agents are primarily interested in providing transplants for their own patients, collaboration requires balancing individual and common objectives. In this paper, we consider ex-post strategic behavior, where agents can modify a proposed set of kidney exchanges. We introduce the class of rejection-proof mechanisms, which propose a set of exchanges such that agents have no incentive to reject them. We provide an exact mechanism and establish that the underlying optimization problem is Σ 2 P -hard; we also describe computationally less demanding heuristic mechanisms. We show rejection-proofness can be achieved at a limited cost for typical instances. Furthermore, our experiments show that the proposed rejection-proof mechanisms also remove incentives for strategic behavior in the ex-ante setting, where agents withhold information. [ABSTRACT FROM AUTHOR]

In a series of papers we develop symbolic computation algorithms to investigate finiteness of central configurations for the planar n -body problem. Our approach is based on Albouy-Kaloshin's work on finiteness of central configurations for the 5-body problems. In their paper, bicolored graphs called zw -diagrams were introduced for possible scenarios when the finiteness conjecture fails, and proving finiteness amounts to exclusions of central configurations associated to these diagrams. Following their method, the amount of computations becomes enormous when there are more than five bodies. In this paper we introduce matrix algebra for determination of possible diagrams and asymptotic orders, devise several criteria to reduce computational complexity, and determine possible zw -diagrams by automated deductions. For the planar six-body problem, we show that there are at most 86 zw -diagrams. [ABSTRACT FROM AUTHOR]

• Application of the Shapley-Shubik index to determine the agents' strength in a dispersed decision-making system. • A new method for generating the local decisions within one cluster. • A new method of determining a set of global decisions. • The results that were obtained were compared with the results that were obtained in the previous papers. In this paper, dispersed knowledge – accumulated in several decision tables is considered. Dispersion of knowledge is not a part of the work of the system. We assume that the knowledge is already in the dispersed form when it provides to the system. An advanced process of detecting the relations between the decision tables and constructing coalitions is used. The purpose of this paper is to use the measure to determine the strength of the coalition. With this method, a simple method of combining vectors of decisions generated based on local decision tables was applied. The purpose of using the Shapley-Shubik index was to reduce the computational complexity compared to the approach proposed in the earlier papers. In this paper, the results of experiments are presented, and the two approaches are compared. Based on these results, some conclusions have been drawn. [ABSTRACT FROM AUTHOR]

The computational complexity of the word problem in HNN-extension of groups is studied. HNN-extension is a fundamental construction in combinatorial group theory. It is shown that the word problem for an ascending HNN-extension of a group H is logspace reducible to the so-called compressed word problem for H. The main result of the paper states that the word problem for an HNN-extension of a hyperbolic group H with cyclic associated subgroups can be solved in polynomial time. This result can be easily extended to fundamental groups of graphs of groups with hyperbolic vertex groups and cyclic edge groups. [ABSTRACT FROM AUTHOR]

• Efficient parallel computations for solving time consuming problems of multiple global optimization. • A general computational scheme of global optimization methods. • Parallel cooperative and competitive computational schemes for computer systems with shared and distributed memory. • Drastic reduction of the required calculations provided by the complete reuse of the calculated search information. This paper proposes an efficient approach for the parallel solution of computationally time consuming problems of multiple global optimization, in which minimized functions can be multiextremal and calculating function values may require huge amounts of computations. The proposed approach is based on the information-statistical theory of global optimization, within which a general computational scheme of global optimization methods is proposed. In the paper, this general scheme is expanded by the possible reuse of search information obtained in the process of computations when solving multiple global optimization problems. Within the framework of the proposed generalized scheme, parallel algorithms are proposed for computational systems with shared and distributed memory. Results of computational experiments demonstrated that the proposed approach can significantly reduce the computational complexity of solving multiple global optimization problems. [ABSTRACT FROM AUTHOR]

Sobel is one of the most popular edge detection operators used in image processing. To date, most users utilize the two-directional 3×3 Sobel operator as detectors because of its low computational cost and reasonable performance. Simultaneously, many studies have been conducted on using large multi-directional Sobel operators to satisfy their needs considering the high stability, but at an expense of speed. This paper proposes a fast graphics processing unit (GPU) kernel for the four-directional 5×5 Sobel operator. To improve kernel performance, we implement the kernel based on warp-level primitives, which can significantly reduce the number of memory accesses. In addition, we introduce the prefetching mechanism and operator transformation into the kernel to significantly reduce the computational complexity and data transmission latency. Compared with the OpenCV-GPU library, our kernel shows high performances of 6.7x speedup on a Jetson AGX Xavier GPU and 13x on a GTX 1650Ti GPU. • Implemented an efficient GPU kernel of a four-directional 5x5 Sobel operator. • Implemented GPU kernel based on warp-level primitives. • Hid latency caused by data transmission using the prefetching mechanism. • Accelerated the computation of diagonal directions using a two-step optimization approach. • Achieved an extremely high processing speed, which is almost 13x faster than that of the OpenCV-GPU library. [ABSTRACT FROM AUTHOR]

In this paper, we consider an infinite-dimensional phase retrieval problem to reconstruct real-valued signals living in a shift-invariant space from their phaseless samples taken either on the whole line or on a discrete set with finite sampling density. We characterize all phase retrievable signals in a real-valued shift-invariant space using their nonseparability. For nonseparable signals generated by some function with support length L , we show that they can be well approximated, up to a sign, from their noisy phaseless samples taken on a discrete set with sampling density 2 L − 1. In this paper, we also propose an algorithm with linear computational complexity to reconstruct nonseparable signals in a shift-invariant space from their phaseless samples corrupted by bounded noises. [ABSTRACT FROM AUTHOR]

Recently, the Randomized Kaczmarz algorithm (RK) draws much attention because of its low computational complexity and less requirement on computer memory. Many existing results on analysis focus on the behavior of RK in Euclidean spaces, and typically derive exponential converge rates with the base tending to one, as the condition number of the system increases. The dependence on the condition number largely restricts the application of these estimates. There are also results using relaxation (i.e., small step-sizes tending to zero as the sample size increases) to achieve polynomial convergence rates of RK in Hilbert spaces. In this paper, we prove the weak convergence (with polynomial rates) of RK with constant step-size in Hilbert spaces. As a consequence, the strong convergence of RK in Euclidean spaces is obtained with condition number-free polynomial rates. In the setting with noisy data, we study the relaxation technique and obtain a strong convergence of RK in Hilbert spaces, with the rates arbitrarily close to the minimax optimal ones. We apply the analysis to reproducing kernel-based online gradient descent learning algorithms and improve the state-of-the-art convergence estimate in the literature. [ABSTRACT FROM AUTHOR]

Acoustic source reconstruction techniques are an essential technical basis for noise source identification and fault diagnosis. How to computationally efficiently obtain the accurate estimation of acoustic source location and strength remains a fundamental challenge for acoustic source reconstruction techniques. To accommodate the needs of processing complex-valued signals, complex approximate message passing algorithm (CAMP) is considered. Benefiting from the Onsager correction term, the reconstruction performance and convergence speed of CAMP are enhanced. The computational complexity of CAMP is significantly reduced by avoiding matrix inversion in each iteration. Therefore, a sparse Equivalent Source Method (ESM) based on CAMP is proposed in this paper and named CAMP-ESM for achieving acoustic source reconstruction with increased accuracy and computational efficiency. Simulation results show in the mid-high frequency range, CAMP-ESM achieves the best reconstruction results in the shortest time compared to other ℓ 1 -based ESM. In addition, the proposed method achieves a good balance between reconstruction accuracy and computational efficiency compared to other state-of-the-art ESM methods. Two experiments verified that CAMP-ESM can accurately localize the acoustic source and quantify the acoustic power. [ABSTRACT FROM AUTHOR]

Automatic font generation is of great benefit to improving the efficiency of font designers. Few-shot font generation aims to generate new fonts from a few reference samples, and has recently attracted a lot of attention from researchers. This is valuable but challenging, especially for ideograms with high diversity and complex structures. Existing models based on convolutional neural networks (CNNs) struggle to generate glyphs with accurate font style and stroke details in the few-shot setting. This paper proposes the TransFont, exploiting the long-range dependency modeling ability of the Vision Transformer (ViT) for few-shot font generation. For the first time, we empirically show that the ViT is better at glyph image generation than CNNs. Furthermore, based on the observation of the high redundancy in the glyph feature map, we introduce the glyph self-attention module for mitigating the quadratic computational and memory complexity of the pixel-level glyph image generation, along with several new techniques, i.e., multi-head multiple sampling, yz axis convolution, and approximate relative position bias. Extensive experiments on two Chinese font libraries show the superiority of our method over existing CNN-based font generation models, the proposed TransFont generates glyph images with more accurate font style and stroke details. • We propose TransFont, a pure transformer-based model for few-shot font generation, which empirically shows that the ViT is better at glyph image generation than CNNs, thanks to the ability in shape recognition. • We propose the glyph self-attention module for mitigating the quadratic computational and memory complexity of the self-attention mechanism on pixel-level glyph image generation, introducing several new techniques, i.e., multi-head multiple sampling, yz axis convolution, and approximate relative position bias. • We view TransFont as a simple but effective transformer baseline for future research, demonstrating its superiority over existing CNN-based font generation models on two challenging Chinese font libraries, FounderType and SinoType. The proposed TransFont generates glyph images with more accurate font style and stroke details. [ABSTRACT FROM AUTHOR]

In most cases in geometry, applying analytic or algebraic tools on coordinates helps to solve some difficult problems. For instance, proving that a geometrical construction problem is solvable using ruler and compass is often impossible within a synthetic geometry framework. But in an analytic geometry framework, it is a direct application of Galois theory after performing triangularizations. However, these algebraic tools lead to a large amount of computation. Their implementation in modern Computer Algebra Systems (CAS) are still too time consuming to provide an answer in a reasonable time. In addition, they require a lot of memory space which can grow exponentially with the size of the problem. Fortunately, some geometrical properties can be used to setup the algebraic systems so that they can be more efficiently computed. These properties turn polynomials into new ones so as to reduce both the degrees and the number of monomials. The present paper promotes this approach by considering two corpora of geometric construction problems, namely Wernick's and Connely's lists. These lists contain about 280 problems. The purpose is to determine their status i.e. whether they are constructible or not with ruler and compass. Some of these problems had unknown status that will be settled in this paper. More generally, the status of all problems of these corpora are fully automatically given by an approach combining geometry and algebra. [ABSTRACT FROM AUTHOR]

We present a new upper bound for the orders of derivatives in the Rosenfeld–Gröbner algorithm under weighted rankings. This algorithm computes a regular decomposition of a radical differential ideal in the ring of differential polynomials over a differential field of characteristic zero with an arbitrary number of commuting derivations. This decomposition can then be used to test for membership in the given radical differential ideal. In particular, this algorithm allows us to determine whether a system of polynomial PDEs is consistent. In the case of one derivation, such a bound was given by Golubitsky et al. (2008) . The only known bound in the case of several derivations was given by the authors of the present paper in 2016. The bound was achieved by associating to the algorithm antichain sequences whose lengths can be bounded using the results of León Sánchez and Ovchinnikov (2016) . In the present paper, the above result by the current authors is generalized and significantly improved. [ABSTRACT FROM AUTHOR]

The selective delayless subband structure stands out as a promising algorithmic choice for the multi-channel active control of vehicle interior noise, particularly in the context of road noise. This type of algorithm reduces the eigenvalue spread of the autocorrelation matrix of the signal by decomposing the signal into subbands, and the desired subbands are activated selectively, thus achieving a significant performance improvement while consuming less computational resources compared with the traditional fullband algorithms. Nevertheless, the effectiveness of the subband algorithm appears to be closely tied to the configuration of the primary disturbance signal. In cases where the primary disturbance signal encompasses both broadband and tonal components, the performance advantage of the subband algorithm becomes constrained. In this paper, we conduct a thorough comparative analysis of two extensively employed subband algorithms, namely the Morgan and the Milani methods, through simulations employing data obtained from a multi-channel active noise control (ANC) headrest system. The results indicate that the Morgan method outperforms the Milani method when configured optimally. Subsequently, we propose an enhanced version of the subband algorithm based on the Morgan method. The enhanced algorithm incorporates an additional sinusoidal noise canceller (SNC) subsystem and a narrowband active noise control (NANC) subsystem based on local secondary path modeling to address tonal components, while the selective subband structure is employed for controlling broadband components. In addition, the computational complexity of the algorithm is analyzed. The effectiveness of the proposed algorithm is validated through numerous simulations and the ANC tests conducted on an actual vehicle utilizing the multi-channel ANC headrest system. The performance of the proposed algorithm surpasses that of traditional selective subband and fullband algorithms, and balanced binaural noise reduction is achieved. [ABSTRACT FROM AUTHOR]

Bayesian Physics Informed Neural Networks (B-PINNs) have gained significant attention for inferring physical parameters and learning the forward solutions for problems based on partial differential equations. However, the overparameterized nature of neural networks poses a computational challenge for high-dimensional posterior inference. Existing inference approaches, such as particle-based or variance inference methods, are either computationally expensive for high-dimensional posterior inference or provide unsatisfactory uncertainty estimates. In this paper, we present a new efficient inference algorithm for B-PINNs that uses Ensemble Kalman Inversion (EKI) for high-dimensional inference tasks. By reframing the setup of B-PINNs as a traditional Bayesian inverse problem, we can take advantage of EKI's key features: (1) gradient-free, (2) computational complexity scales linearly with the dimension of the parameter spaces, and (3) rapid convergence with typically O (100) iterations. We demonstrate the applicability and performance of the proposed method through various types of numerical examples. We find that our proposed method can achieve inference results with informative uncertainty estimates comparable to Hamiltonian Monte Carlo (HMC)-based B-PINNs with a much reduced computational cost. These findings suggest that our proposed approach has great potential for uncertainty quantification in physics-informed machine learning for practical applications. • Proposed a gradient-free inference algorithm for Bayesian physics informed neural networks (BPINNs). • Reframed BPINNs as a classic inverse problem to utilize Ensemble Kalman Inversion (EKI). • Demonstrated our method achieves informative uncertainty estimates at lower cost. [ABSTRACT FROM AUTHOR]

We study a classic problem introduced thirty years ago by Eades and Wormald. Let G = (V , E , λ) be a weighted planar graph, where λ : E → R + is a length function. The Fixed Edge-Length Planar Realization problem (FEPR for short) asks whether there exists a planar straight-line realization of G , i.e., a planar straight-line drawing of G where the Euclidean length of each edge e ∈ E is λ (e). Cabello, Demaine, and Rote showed that the FEPR problem is NP-hard, even when λ assigns the same value to all the edges and the graph is triconnected. Since the existence of large triconnected minors is crucial to the known NP-hardness proofs, in this paper we investigate the computational complexity of the FEPR problem for weighted 2-trees, which are K 4 -minor free. We show the NP-hardness of the problem, even when λ assigns to the edges only up to four distinct lengths. Conversely, we show that the FEPR problem is linear-time solvable when λ assigns to the edges up to two distinct lengths, or when the input has a prescribed embedding. Furthermore, we consider the FEPR problem for weighted maximal outerplanar graphs and prove it to be linear-time solvable if their dual tree is a path, and cubic-time solvable if their dual tree is a caterpillar. Finally, we prove that the FEPR problem for weighted 2-trees is slice-wise polynomial in the length of the large path. [ABSTRACT FROM AUTHOR]

In this paper, we study constacyclic codes of length n = 7 p s over a finite field of characteristics p , where p ≠ 7 is an odd prime number and s a positive integer. The previous methods in the literature that were used to compute the Hamming distances of repeated-root constacyclic codes of lengths n p s with 1 ≤ n ≤ 6 cannot be applied to completely determine the Hamming distances of those with n = 7. This is due to the high computational complexity involved and the large number of unexpected intermediate results that arise during the computation. To overcome this challenge, we propose a computer-assisted method for determining the Hamming distances of simple-root constacyclic codes of length 7, and then utilize it to derive the Hamming distances of the repeated-root constacyclic codes of length 7 p s. Our method is not only straightforward to implement but also efficient, making it applicable to these codes with larger values of n as well. In addition, all self-orthogonal, dual-containing, self-dual, MDS and AMDS codes among them will also be characterized. [ABSTRACT FROM AUTHOR]

In this paper we establish how alphabet size, treewidth and maximum degree of the underlying graph are key parameters which influence the overall computational complexity of finite freezing automata networks. First, we define a general decision problem, called Specification Checking Problem , that captures many classical decision problems such as prediction, nilpotency, predecessor, asynchronous reachability. Then, we present a fast-parallel algorithm that solves the general model checking problem when the three parameters are bounded, hence showing that the problem is in NC. Moreover, we show that the problem is in XP on the parameters tree-width and maximum degree. Finally, we show that these problems are hard from two different perspectives. First, the general problem is W[2]-hard when taking either treewidth or alphabet as single parameter and fixing the others. Second, the classical problems are hard in their respective classes when restricted to families of graph with sufficiently large treewidth. [ABSTRACT FROM AUTHOR]

3D human pose estimation in videos aims at locating the human joints in the 3D space given a temporal sequence. Motion information and skeleton context are two significant elements for pose estimation in videos. In this paper, we propose a SlowFastFormer (slow-fast transformer) network where two branches with different input rates are composed to encode these two different kinds of context. For the slow branch, skeleton context is well learned at a higher frame rate. For the fast branch, motion information is captured at a lower frame rate. Through these two branches, different kinds of context are encoded separately. We fuse these two branches at a later stage to fully utilize the skeleton context and motion information. Afterwards, a blending module is developed to promote the message exchange among multiple branches. In the blending stage, different kinds of context information are exchanged and feature representation is enhanced consequently. Lastly, a hierarchical supervision scheme is tailored where predictions of different levels are inferred in a progressive manner. Our approach achieves competitive performance with lower computation complexity on several benchmarks, i.e., Human3.6M, MPI-INF-3DHP and HumanEva-I. • A SlowFastFormer framework with lower computational complexity is developed to solve the task of 3D human pose estimation. • Features are progressively improved via parallel encoding and blending stages. • A hierarchical supervision scheme is proposed to refine the predictions. • Different kinds of transformer blocks are employed to perform the relation modelling. [ABSTRACT FROM AUTHOR]

Traditional functional linked neural networks (FLNNs) impose a significant computational burden due to their input expansion, primarily stemming from the utilization of digital filters. This paper presents a Laguerre FLNNs filter for nonlinear active noise control (NANC) systems. By employing the truncated Laguerre series, the presented filter achieves effective approximation of long primary paths with a reduced filter length. Moreover, we develop adaptive algorithms rooted in information-theoretic learning (ITL) within the framework of the Laguerre-FLNNs NANC model. Using the ITL criterions, a Laguerre filtered-s maximum correntropy criterion (LFsMCC) algorithm is derived and a Laguerre filtered-s quantized minimum error entropy criterion (LFsQMEE) algorithm is proposed by minimizing Renyi's quadratic entropy. To reduce the computation cost, an online vector quantization method is utilized to improve the LFsQMEE. This technique selectively quantizes the error vectors, reducing them to a smaller subset of samples within the codebook. Moreover, an enhanced LFsQMEE with a fiducial point is introduced. The steady-state performance and the computational complexity are analyzed. Theoretical analysis is validated through simulations and the control performance of the proposed model and algorithms is tested in experiments with both simulated and real paths. [ABSTRACT FROM AUTHOR]

The Non-Synchronous Measurements is particularly effective at expanding the operating frequency range of a single microphone array. The completed cross-spectral matrix of the synthetic array, when combined with high-resolution imaging algorithms, can yield accurate sound source identification results. However, when matrix completion algorithms are applied to large synthetic arrays, their computational complexity increases significantly. Furthermore, existing integrations with high-resolution imaging algorithms often encounter difficulties in the presence of coherent sound sources. To address this problem, this paper introduces the accelerated gradient descent algorithm for the covariance matrix fitting by orthogonal least squares. The matrix completion model for non-synchronous measurements is initially simplified through matrix decomposition, thereby enabling the rapid completion of the cross-spectral matrix using the accelerated gradient descent algorithm. This is then followed by the application of the covariance matrix fitting by orthogonal least squares to achieve quick and precise identification of coherent sound sources employing the completed cross-spectral matrix. The performance of the algorithm is evaluated using numerical simulations and validated through loudspeaker experiments in an anechoic chamber. The results from these simulations and experiments reveal that the proposed algorithm not only improves matrix completion performance on large synthetic arrays but also accurately identifies the locations and correlation coefficients of coherent sound sources. [ABSTRACT FROM AUTHOR]

Satisfiability of word equations problem is: Given two sequences consisting of letters and variables decide whether there is a substitution for the variables that turns this equation into true equality. The exact computational complexity of this problem remains unknown, with the best lower and upper bounds being, respectively, NP and PSPACE. Recently, the novel technique of recompression was applied to this problem, simplifying the known proofs and lowering the space complexity to (non-deterministic) O (n log ⁡ n). In this paper we show that satisfiability of word equations is in non-deterministic linear space, thus the language of satisfiable word equations is context-sensitive. We use the known recompression-based algorithm and additionally employ Huffman coding for letters. The proof, however, uses analysis of how the fragments of the equation depend on each other as well as a new strategy for non-deterministic choices of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with differentially private stochastic gradient descent (SGD) algorithms in the setting of stochastic convex optimization (SCO). Most of the existing work requires the loss to be Lipschitz continuous and strongly smooth, and the model parameter to be uniformly bounded. However, these assumptions are restrictive as many popular losses violate these conditions including the hinge loss for SVM, the absolute loss in robust regression, and even the least square loss in an unbounded domain. We significantly relax these restrictive assumptions and establish privacy and generalization (utility) guarantees for private SGD algorithms using output and gradient perturbations associated with non-smooth convex losses. Specifically, the loss function is relaxed to have an α -Hölder continuous gradient (referred to as α-Hölder smoothness) which instantiates the Lipschitz continuity (α = 0) and the strong smoothness (α = 1). We prove that noisy SGD with α -Hölder smooth losses using gradient perturbation can guarantee (ϵ , δ) -differential privacy (DP) and attain optimal excess population risk O ( d log ⁡ (1 / δ) n ϵ + 1 n ) , up to logarithmic terms, with the gradient complexity O (n 2 − α 1 + α + n). This shows an important trade-off between α -Hölder smoothness of the loss and the computational complexity for private SGD with statistically optimal performance. In particular, our results indicate that α -Hölder smoothness with α ≥ 1 / 2 is sufficient to guarantee (ϵ , δ) -DP of noisy SGD algorithms while achieving optimal excess risk with a linear gradient complexity O (n). [ABSTRACT FROM AUTHOR]

A finite dynamical system is a system consisting of some finite number of objects that take upon a value from some domain as a state, in which after initialization the states of the objects are updated based upon the states of the other objects and themselves according to a certain update schedule. This paper studies a subclass of finite dynamical systems the synchronous Boolean finite dynamical system ( synchronous BFDS , for short), where the states are Boolean and the state update takes place in discrete time and at the same on all objects. The paper is concerned with three problems, Convergence , Path Intersection , and Cycle Length, of the synchronous BFDS in which the state update functions (or the local state transition functions) are chosen from a predetermined finite basis of Boolean functions B . The paper results characterize their computational complexity. [ABSTRACT FROM AUTHOR]

A barrier certificate can separate the state space of a considered hybrid system (HS) into safe and unsafe parts according to the safety property to be verified. Therefore this notion has been widely used in the verification of HSs. A stronger condition on barrier certificates (BCs) means that fewer BCs can be synthesized, as the expressiveness of synthesized BCs is weaker. On the other hand, synthesizing more expressive BCs normally means higher complexity. Kong et al. (2013a) investigated how to relax the condition of BCs while still keeping their convexity so that one can synthesize more expressive BCs efficiently using semi-definite programming (SDP). In this paper, we first discuss how to relax the condition of BCs in a general way, while still keeping their convexity. Thus, one can utilize different weaker conditions flexibly to synthesize different kinds of BCs with more expressiveness efficiently using SDP, which gives more opportunities to verify the considered system. We also show how to combine two functions together to form a combined BC in order to prove a safety property under consideration, whereas neither of them may be a BC separately. In fact, the notion of combined BCs is strictly more expressive than that of BCs, so it further brings more chances to verify a considered system. Another contribution of this paper is to investigate how to avoid the unsoundness of SDP based approaches caused by numerical error through symbolic checking. [ABSTRACT FROM AUTHOR]

The parity argument principle states that every finite graph has an even number of odd degree vertices. We consider the problem whose totality is guaranteed by the parity argument on a graph with potential. In this paper, we show that the problem of finding an unknown odd-degree vertex or a local optimum vertex on a graph with potential is polynomially equivalent to EndOfPotentialLine if the maximum degree is at most three. However, even if the maximum degree is 4, such a problem is PPA ∩ PLS -complete. To show the complexity of this problem, we provide new results on multiple-source variants of EndOfPotentialLine , which is the canonical problem for EOPL. This result extends the work by Goldberg and Hollender; they studied similar variants of EndOfLine. [ABSTRACT FROM AUTHOR]

Thanks to the powerful modeling capabilities of multi-head self attention (MSA), transformers have shown significant performance gains in vision tasks. However, as transformers require heavy computation, more efficient designs are required. In this paper, we present an efficient transformer architecture named GoLDFormer for image restoration. GoLDFormer extends the capability of window-based self-attention through two core designs. First, We propose a globally-enhanced window-based transformer block (G-WTB), which applies transposed attention to a compressed window representation rather than the spatial features, thus establishing connections between all windows with less computational complexity. Second, since the interactions between image content and window attention weights can be interpreted as spatially varying convolution, we introduce an adaptive filter structure into transformer models and propose a deformable filtering block (DFB) to enable cross-window connections. By adjusting the shape of the generated filters in the DFB, we can balance the computational costs and the degree of adjacent window interaction. Extensive experiments on several image restoration tasks demonstrate that GoLDFormer achieves competitive results against recent methods but with optimal computational costs. • We propose GoLDFormer, including two blocks, to enhance W-MSA globally and locally. • Globally-enhanced attention block captures global dependencies between all windows. • Deformable filtering block captures local dependencies by modifying filter size. • Our GoLDFormer achieves competitive results against recent lightweight methods. [ABSTRACT FROM AUTHOR]

Deep learning (DL) has been widely utilized in image compressive sensing (CS) to enhance the quality and speed of reconstruction. The typical deep network for CS reconstruction comprises an initial reconstruction subnetwork, followed by a cascaded deep refinement reconstruction subnetworks. This paper introduces a new low-complexity image CS deep reconstruction framework, GSRCS, which leverages multi-image based deep super-resolution technology to better address the cost constraints of practical applications. The proposed initial reconstruction module generates multiple low-resolution images in parallel by grouping the input measurements, while a high-quality, high-resolution reconstructed image is produced through a multi-image deep super-resolution network. The theoretical derivation and experimental results demonstrate that this method significantly reduces system complexity in terms of parameters and floating-point arithmetic operations, while achieving competitive reconstruction performance compared to the state-of-the-arts. Specifically, the average number of parameters is reduced by over 63%, and the computational complexity is decreased by more than 88%. [Display omitted] [ABSTRACT FROM AUTHOR]

• An efficient approach for image quality assessment is proposed. • It uses perceptual features such as texture, structure, and patterns to measure image quality. • The various experimentations are carried out on LIVE-II, TID2008, TID2013, and CSIQ datasets. • The proposed approach is efficient as compared to existing methods. In this paper, a human visual system (HVS) based no-reference image quality assessment model (NR-IQA) is proposed. This is an objective NR-IQA model that uses perceptual features such as structure and orientation to compute the loss of naturalness in the image. An adaptive feature extraction process is modeled to capture the underlying significant features of the images along with the noise. Moreover, the optimal subset of features is derived using the neighborhood component analysis and further used as inputs to the Gaussian process for regression. The various experimentations are carried out on LIVE, TID2008, and TID2013 databases to test the effectiveness of the proposed approach. It is observed that the presented model exhibits a competitive performance in comparison with the existing IQA approaches. Moreover, the computation complexity and run-time show the effectuality of the proposed approach. Further, the experiments show that the predicted score matches with human perceptions. Thus, the proposed model is more accurate, less complex, independent of distortions, and well-suited for real-time applications. [ABSTRACT FROM AUTHOR]

Lossy compression introduces artifacts, and many conventional in-loop filters have been adopted in the AV1 standard to reduce these artifacts. Researchers have explored deep learning-based filters to remove artifacts in the compression loop. However, the high computational complexity of CNN-based filters remains a challenge. In this paper, a Texture- and Motion-Aware Perception (TMAP) in-loop filter is proposed to addresses this issue by selectively applying CNNs to texture-rich and high-motion regions, while utilizing non-learning methods to detect these regions. The proposed method introduces a new CNN structure, the Dense-Dual-Field Network (DDFN), which leverages a larger receptive field to enhance the quality of reconstructed frames by incorporating more contextual information. Furthermore, to improve perceptual quality, a novel loss function integrating wavelet-based perceptual information is presented. Experimental results demonstrate the superiority of our proposed models over other lightweight CNN models, and the effectiveness of the perceptual loss function is validated using the VMAF metric. [ABSTRACT FROM AUTHOR]

• A two-branch end-to-end dehazing network is proposed, which can solve the imbalances weight distribution problem between the detail and structural features. • Coordinate channel attention module is employed to extract the structural features and the dense pixel attention modules is employed to extract the detail features. • Extensive experiments are conducted on both synthetic and real-world dataset and performed well. Image dehazing is an ill-posed problem that has been extensively studied in recent years. Unfortunately, most existing deep dehazing models have high computational complexity and lack the dynamic adjustment of details, which hinders their application to high-resolution images in computational vision tasks. In this paper, we propose an efficient dual-path adaptive fusion dehazing network (DPAFD-Net) to directly restore a clear image from a hazy input. Moreover, we propose a pure subnetwork with encoder and decoder structures to further extract the structural information and progressively restore the haze-free image. To evaluate the effectiveness of the proposed method, we validate our approach on synthetic and real hazy images, where our method performs favourably against the state-of-the-art dehazing approaches. [ABSTRACT FROM AUTHOR]

Multi-exit architectures consist of a backbone and branch classifiers that offer shortened inference pathways to reduce the run-time of deep neural networks. In this paper, we analyze different branching patterns that vary in their allocation of computational complexity for the branch classifiers. Constant-complexity branching keeps all branches the same, while complexity-increasing and complexity-decreasing branching place more complex branches later or earlier in the backbone respectively. Through extensive experimentation on multiple backbones and datasets, we find that complexity-decreasing branches are more effective than constant-complexity or complexity-increasing branches, which achieve the best accuracy-cost trade-off. We investigate a cause by using knowledge consistency to probe the effect of adding branches onto a backbone. Our findings show that complexity-decreasing branching yields the least disruption to the feature abstraction hierarchy of the backbone, which explains the effectiveness of the branching patterns. [Display omitted] • We propose a novel multi-exit method to explore branching patterns with the same total branch FLOP. • KC explains the validity of complexity-decreasing pattern as its less disruption for the backbone. • A weighted ensemble for distillation training is effective to further improve the performance. [ABSTRACT FROM AUTHOR]

This paper presents an improved anisotropic diffusion method using region adaptive smoothing strength. Unlike existing methods, the proposed method uses an adaptive classifier to find a good estimate of the optimal smoothing strength for each iteration to consider the varying noise characteristics. Further, when training the classifiers, the usefulness of the training data is verified and less useful data are excluded to avoid degraded training results, thereby generating robust and improved denoising performance. For reduction of the computational complexity, this paper also proposes a simple region analysis technique. Consequently, the proposed method is appropriate for the devices that have relatively small computing power. Experimental results confirm that the proposed method outperforms AD-based benchmark methods by increased peak signal-to-noise ratio up to 2.37 dB and structural similarity up to 0.0557 for 10% noise level. [ABSTRACT FROM AUTHOR]

Studies in biological vision have always been a great source of inspiration for design of computer vision algorithms. In the past, several successful methods were designed with varying degrees of correspondence with biological vision studies, ranging from purely functional inspiration to methods that utilise models that were primarily developed for explaining biological observations. Even though it seems well recognised that computational models of biological vision can help in design of computer vision algorithms, it is a non-trivial exercise for a computer vision researcher to mine relevant information from biological vision literature as very few studies in biology are organised at a task level. In this paper we aim to bridge this gap by providing a computer vision task centric presentation of models primarily originating in biological vision studies. Not only do we revisit some of the main features of biological vision and discuss the foundations of existing computational studies modelling biological vision, but also we consider three classical computer vision tasks from a biological perspective: image sensing, segmentation and optical flow. Using this task-centric approach, we discuss well-known biological functional principles and compare them with approaches taken by computer vision. Based on this comparative analysis of computer and biological vision, we present some recent models in biological vision and highlight a few models that we think are promising for future investigations in computer vision. To this extent, this paper provides new insights and a starting point for investigators interested in the design of biology-based computer vision algorithms and pave a way for much needed interaction between the two communities leading to the development of synergistic models of artificial and biological vision. [ABSTRACT FROM AUTHOR]

In a recent work, Girard proposed a new and innovative approach to computational complexity based on the proofs-as-programs correspondence. In a previous paper, the authors showed how Girard's proposal succeeds in obtaining a new characterization of co-NL languages as a set of operators acting on a Hilbert Space. In this paper, we extend this work by showing that it is also possible to define a set of operators characterizing the class L of logarithmic space languages. [ABSTRACT FROM AUTHOR]