Search

This work introduces advanced computational techniques for modeling the time evolution of compact binary systems using machine learning. The dynamics of compact binary systems, such as black holes and neutron stars, present significant nonlinear challenges due to the strong gravitational interactions and the requirement for precise numerical simulations. Traditional methods, like the post-Newtonian approximation, often require significant computational resources and face challenges in accuracy and efficiency. Here, we employed machine learning algorithms, including deep learning models like Long Short-Term Memory (LSTM) and Temporal Convolutional Network (TCN), to predict the future evolution of these systems based on extensive simulation data. Our results demonstrate that employing both LSTM and TCN even as black-box predictors for sequence prediction can also significantly improve the prediction accuracy without PINNs as PDE solvers with prior knowledge or inductive bias. By employing LSTM and TCN, we obtained $R^2$ values of 99.74\% and 99.19\% for the evolutionary orbits of compact binaries dataset, respectively. Our models demonstrate the ability to effectively capture the dynamics of the binaries, achieving high prediction performance with significantly reduced computational overhead by a factor of 40, compared to conventional numerical methods. This study paves the way for more effective and computationally scalable approaches to the understanding of gravitational phenomena and predictive modeling in gravitational-wave astronomy., Comment: pages, 6 figures, 7 tables, 1 algorithm

The correction map method means extended phase-space algorithm with correction map. In our research, we have developed a correction map method, specifically the dissipated correction map method with trapezoidal rule, for numerical simulations of gravitational waves from spinning compact binary systems. This new correction map method, denoted as $CM3$, has shown remarkable performance in various simulation results, such as phase space distance, dissipated energy error, and gravitational waveform, closely resembling the high-order precision implicit Gaussian algorithm. When compared to the previously used midpoint map which denoted as $C_2$, the $CM3$ consistently exhibits a closer alignment with the highly accurate Gaussian algorithm in waveform evolution and orbital trajectory analysis. Through detailed comparisons and analyses, it is evident that $CM3$ outperforms other algorithms, including $CM2$ and $C_2$ mentioned in this paper, in terms of accuracy and precision in simulating spinning compact binary systems. The incorporation of the trapezoidal rule and the optimization with a scale factor $\gamma$ have significantly enhanced the performance of $CM3$, making it a promising method for future numerical simulations in astrophysics. With the groundbreaking detection of gravitational waves by the LIGO/VIRGO collaboration, interest in this research domain has soared. Our work contributes valuable insights for the application of matched filtering techniques in the analysis of gravitational wave signals, enhancing the precision and reliability of these detection.

We propose depth from coupled optical differentiation, a low-computation passive-lighting 3D sensing mechanism. It is based on our discovery that per-pixel object distance can be rigorously determined by a coupled pair of optical derivatives of a defocused image using a simple, closed-form relationship. Unlike previous depth-from-defocus (DfD) methods that leverage spatial derivatives of the image to estimate scene depths, the proposed mechanism's use of only optical derivatives makes it significantly more robust to noise. Furthermore, unlike many previous DfD algorithms with requirements on aperture code, this relationship is proved to be universal to a broad range of aperture codes. We build the first 3D sensor based on depth from coupled optical differentiation. Its optical assembly includes a deformable lens and a motorized iris, which enables dynamic adjustments to the optical power and aperture radius. The sensor captures two pairs of images: one pair with a differential change of optical power and the other with a differential change of aperture scale. From the four images, a depth and confidence map can be generated with only 36 floating point operations per output pixel (FLOPOP), more than ten times lower than the previous lowest passive-lighting depth sensing solution to our knowledge. Additionally, the depth map generated by the proposed sensor demonstrates more than twice the working range of previous DfD methods while using significantly lower computation.

This paper proposes QDFO, a dataflow-based optimization approach to Microsoft QIR. QDFO consists of two main functions: one is to preprocess the QIR code so that the LLVM optimizer can capture more optimization opportunities, and the other is to optimize the QIR code so that duplicate loading and constructing of qubits and qubit arrays can be avoided. We evaluated our work on the IBM Challenge Dataset, the results show that our method effectively reduces redundant operations in the QIR code. We also completed a preliminary implementation of QDFO and conducted a case study on the real-world code. Our observational study indicates that the LLVM optimizer can further optimize the QIR code preprocessed by our algorithm. Both the experiments and the case study demonstrate the effectiveness of our approach.

The astonishing development of single-photon cameras has created an unprecedented opportunity for scientific and industrial imaging. However, the high data throughput generated by these 1-bit sensors creates a significant bottleneck for low-power applications. In this paper, we explore the possibility of generating a color image from a single binary frame of a single-photon camera. We evidently find this problem being particularly difficult to standard colorization approaches due to the substantial degree of exposure variation. The core innovation of our paper is an exposure synthesis model framed under a neural ordinary differential equation (Neural ODE) that allows us to generate a continuum of exposures from a single observation. This innovation ensures consistent exposure in binary images that colorizers take on, resulting in notably enhanced colorization. We demonstrate applications of the method in single-image and burst colorization and show superior generative performance over baselines. Project website can be found at https://vishal-s-p.github.io/projects/2023/generative_quanta_color.html., Comment: Accepted at IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2024

We present CT-Bound, a robust and fast boundary detection method for very noisy images using a hybrid Convolution and Transformer neural network. The proposed architecture decomposes boundary estimation into two tasks: local detection and global regularization. During the local detection, the model uses a convolutional architecture to predict the boundary structure of each image patch in the form of a pre-defined local boundary representation, the field-of-junctions (FoJ). Then, it uses a feed-forward transformer architecture to globally refine the boundary structures of each patch to generate an edge map and a smoothed color map simultaneously. Our quantitative analysis shows that CT-Bound outperforms the previous best algorithms in edge detection on very noisy images. It also increases the edge detection accuracy of FoJ-based methods while having a 3-time speed improvement. Finally, we demonstrate that CT-Bound can produce boundary and color maps on real captured images without extra fine-tuning and real-time boundary map and color map videos at ten frames per second.

Judgment aggregation is a framework to aggregate individual opinions on multiple, logically connected issues into a collective outcome. These opinions are cast by judges, which can be for example referees, experts, advisors or jurors, depending on the application and context. It is open to manipulative attacks such as \textsc{Manipulation} where judges cast their judgments strategically. Previous works have shown that most computational problems corresponding to these manipulative attacks are \NP-hard. This desired computational barrier, however, often relies on formulas that are either of unbounded size or of complex structure. We revisit the computational complexity for various \textsc{Manipulation} and \textsc{Bribery} problems in premise-based judgment aggregation, now focusing on simple and realistic formulas. We restrict all formulas to be clauses that are (positive) monotone, Horn-clauses, or have bounded length. For basic variants of \textsc{Manipulation}, we show that these restrictions make several variants, which were in general known to be \NP-hard, polynomial-time solvable. Moreover, we provide a P vs.\ NP dichotomy for a large class of clause restrictions (generalizing monotone and Horn clauses) by showing a close relationship between variants of \textsc{Manipulation} and variants of \textsc{Satisfiability}. For Hamming distance based \textsc{Manipulation}, we show that \NP-hardness even holds for positive monotone clauses of length three, but the problem becomes polynomial-time solvable for positive monotone clauses of length two. For \textsc{Bribery}, we show that \NP-hardness even holds for positive monotone clauses of length two, but it becomes polynomial-time solvable for the same clause set if there is a constant budget.

The equations of motion for a Lagrangian mainly refer to the acceleration equations, which can be obtained by the Euler--Lagrange equations. In the post-Newtonian Lagrangian form of general relativity, the Lagrangian systems can only maintain a certain post-Newtonian order and are incoherent Lagrangians since the higher-order terms are omitted. This truncation can cause some changes in the constant of motion. However, in celestial mechanics, Hamiltonians are more commonly used than Lagrangians. The conversion from Lagrangian to Hamiltonian can be achieved through the Legendre transformation. The coordinate momentum separable Hamiltonian can be computed by the symplectic algorithm, whereas the inseparable Hamiltonian can be used to compute the evolution of motion by the phase-space expansion method. Our recent work involves the design of a multi-factor correction map for the phase-space expansion method, known as the correction map method. In this paper, we compare the performance of the implicit algorithm in post-Newtonian Lagrangians and the correction map method in post-Newtonian Hamiltonians. Specifically, we investigate the extent to which both methods can uphold invariance of the motion's constants, such as energy conservation and angular momentum preservation. Ultimately, the results of numerical simulations demonstrate the superior performance of the correction map method, particularly with respect to angular momentum conservation.

Quantum computing has emerged as a promising domain for the machine learning (ML) area, offering significant computational advantages over classical counterparts. With the growing interest in quantum machine learning (QML), ensuring the correctness and robustness of software platforms to develop such QML programs is critical. A necessary step for ensuring the reliability of such platforms is to understand the bugs they typically suffer from. To address this need, this paper presents the first comprehensive study of bugs in QML frameworks. We inspect 391 real-world bugs collected from 22 open-source repositories of nine popular QML frameworks. We find that 1) 28% of the bugs are quantum-specific, such as erroneous unitary matrix implementation, calling for dedicated approaches to find and prevent them; 2) We manually distilled a taxonomy of five symptoms and nine root cause of bugs in QML platforms; 3) We summarized four critical challenges for QML framework developers. The study results provide researchers with insights into how to ensure QML framework quality and present several actionable suggestions for QML framework developers to improve their code quality., Comment: This paper will be appeared in the proceedings of the 2023 IEEE International Conference on Quantum Software (QSW 2023), July 2-8, 2023

Quantum Intermediate Representation (QIR) is a Microsoft-developed, LLVM-based intermediate representation for quantum program compilers. QIR aims to provide a general solution for quantum program compilers independent of front-end languages and back-end hardware, thus avoiding duplicate development of intermediate representations and compilers. Since it is still under development, QIR is described in natural language and lacks a formal definition, leading to ambiguity in its interpretation and a lack of rigor in implementing quantum functions. In this paper, we provide formal definitions for the data types and instruction sets of QIR, aiming to provide correctness and security guarantees for operations and intermediate code conversions in QIR. To validate our design, we show some samples of unsafe QIR code where errors can be detected by our formal approach.

Since the first detection of gravitational waves by the LIGO/VIRGO team, the related research field has attracted more attention. The spinning compact binaries system, as one of the gravitational-wave sources for broadband laser interferometers, has been widely studied by related researchers. In order to analyze the gravitational wave signals using matched filtering techniques, reliable numerical algorithms are needed. Spinning compact binaries systems in Post-Newtonian (PN) celestial mechanics have an inseparable Hamiltonian. The extended phase-space algorithm is an effective solution for the problem of this system. We have developed correction maps for the extended phase-space method in our previous work, which significantly improves the accuracy and stability of the method with only a momentum scale factor. In this paper, we will add more scale factors to modify the numerical solution in order to minimize the errors in the constants of motion. However, we find that these correction maps will result in a large energy bias in the subterms of the Hamiltonian in chaotic orbits, whose potential and kinetic energy, etc. are calculated inaccurately. We develop new correction maps to reduce the energy bias of the subterms of the Hamiltonian, which can instead improve the accuracy of the numerical solution and also provides a new idea for the application of the manifold correction in other algorithms.

We study the problem of allocating multiple types of resources to agents with Leontief preferences. The classic Dominant Resource Fairness (DRF) mechanism satisfies several desired fairness and incentive properties, but is known to have poor performance in terms of social welfare approximation ratio. In this work, we propose a new approximation ratio measure, called \emph{\fratio}, which is defined as the worst-case ratio between the optimal social welfare (resp. utilization) among all \emph{fair} allocations and that by the mechanism, allowing us to break the lower bound barrier under the classic approximation ratio. We then generalize DRF and present several new mechanisms with two and multiple types of resources that satisfy the same set of properties as DRF but with better social welfare and utilization guarantees under the new benchmark. We also demonstrate the effectiveness of these mechanisms through experiments on both synthetic and real-world datasets., Comment: Accepted to WINE 2022

Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might arise. We study the following problem to cope with such situations: Given an allocation of indivisible resources to agents with additive utility-based preferences, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources., Comment: Accepted to AAMAS'22

As quantum programming evolves, more and more quantum programming languages are being developed. As a result, debugging and testing quantum programs have become increasingly important. While bug fixing in classical programs has come a long way, there is a lack of research in quantum programs. To this end, this paper presents a comprehensive study on bug fixing in quantum programs. We collect and investigate 96 real-world bugs and their fixes from four popular quantum programming languages Qiskit, Cirq, Q#, and ProjectQ). Our study shows that a high proportion of bugs in quantum programs are quantum-specific bugs (over 80%), which requires further research in the bug fixing domain. We also summarize and extend the bug patterns in quantum programs and subdivide the most critical part, math-related bugs, to make it more applicable to the study of quantum programs. Our findings summarize the characteristics of bugs in quantum programs and provide a basis for studying testing and debugging quantum programs.

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where a resource may be shared by two neighbors in a social network and each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks., Comment: Accepted at the 36th AAAI Conference on Artificial Intelligence, AAAI-22

Given a set of agents qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of agents. Social qualification depends on the specific rule used to aggregate individual qualifications. The classical bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome in a certain way. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific agents socially qualified) or destructive (aiming at making specific agents socially disqualified) setting, we provide a comprehensive picture of the parameterized computational complexity landscape. Conceptually, we also consider a more fine-grained concept of bribery cost, where we ask how many single qualifications need to be changed, nonunit prices for different bribery actions, and a more general bribery goal that combines the constructive and destructive setting.

We study a variant of Set Cover where each element of the universe has some demand that determines how many times the element needs to be covered. Moreover, we examine two generalizations of this problem when a set can be included multiple times and when sets have different prices. We prove that all three problems are fixed-parameter tractable with respect to the combined parameter budget, the maximum number of elements missing in one of the sets, and the maximum number of sets in which one of the elements does not occur. Lastly, we point out how our fixed-parameter tractability algorithm can be applied in the context of bribery for the (collective-decision) group identification problem.