More Like this

1. SAT-Inspired Eliminations for Superposition

   https://doi.org/10.1145/3565366  

   Vukmirović, Petar; Blanchette, Jasmin; Heule, Marijn J. (January 2023, ACM Transactions on Computational Logic)

   Optimized SAT solvers not only preprocess the clause set, they also transform it during solving as inprocessing. Some preprocessing techniques have been generalized to first-order logic with equality. In this article, we port inprocessing techniques to work with superposition, a leading first-order proof calculus, and we strengthen known preprocessing techniques. Specifically, we look into elimination of hidden literals, variables (predicates), and blocked clauses. Our evaluation using the Zipperposition prover confirms that the new techniques usefully supplement the existing superposition machinery. 

   more » « less
2. Adaptive Metareasoning for Bounded Rational Agents

   Svegliato, Justin; Zilberstein, Shlomo (July 2018, IJCAI-ECAI Workshop on Architectures and Evaluation for Generality, Autonomy and Progress in AI (AEGAP))

   In computational approaches to bounded rationality, metareasoning enables intelligent agents to optimize their own decision-making process in order to produce effective action in a timely manner. While there have been substantial efforts to develop effective meta-level control for anytime algorithms, existing techniques rely on extensive offline work, imposing several critical assumptions that diminish their effectiveness and limit their practical utility in the real world. In order to eliminate these assumptions, adaptive metareasoning enables intelligent agents to adapt to each individual instance of the problem at hand without the need for significant offline preprocessing. Building on our recent work, we first introduce a model-free approach to meta-level control based on reinforcement learning. We then present a meta-level control technique that uses temporal difference learning. Finally, we show empirically that our approach is effective on a common benchmark in meta-level control. 

   more » « less
3. Breaking RSA Generically Is Equivalent to Factoring, with Preprocessing

   https://doi.org/10.4230/LIPIcs.ITC.2024.8  

   Dachman-Soled, Dana; Loss, Julian; O'Neill, Adam (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Aggarwal, Divesh (Ed.)

   We investigate the relationship between the classical RSA and factoring problems when preprocessing is considered. In such a model, adversaries can use an unbounded amount of precomputation to produce an "advice" string to then use during the online phase, when a problem instance becomes known. Previous work (e.g., [Bernstein, Lange ASIACRYPT '13]) has shown that preprocessing attacks significantly improve the runtime of the best-known factoring algorithms. Due to these improvements, we ask whether the relationship between factoring and RSA fundamentally changes when preprocessing is allowed. Specifically, we investigate whether there is a superpolynomial gap between the runtime of the best attack on RSA with preprocessing and on factoring with preprocessing. Our main result rules this out with respect to algorithms that perform generic computation on the RSA instance x^e od N yet arbitrary computation on the modulus N, namely a careful adaptation of the well-known generic ring model of Aggarwal and Maurer (Eurocrypt 2009) to the preprocessing setting. In particular, in this setting we show the existence of a factoring algorithm with polynomially related parameters, for any setting of RSA parameters. Our main technical contribution is a set of new information-theoretic techniques that allow us to handle or eliminate cases in which the Aggarwal and Maurer result does not yield a factoring algorithm in the standard model with parameters that are polynomially related to those of the RSA algorithm. These techniques include two novel compression arguments, and a variant of the Fiat-Naor/Hellman tables construction that is tailored to the factoring setting. 

   more » « less
4. On a class of coupled Hamiltonian operators and their integrable hierarchies with two potentials

   Gu, Xiang; Ma, Wen-Xiu (July 2018, Mathematical methods in the applied sciences)

   We discuss at first in this paper the Gauge equivalence among several u‐linear Hamiltonian operators and present explicitly the associated Gauge transformation of Bäcklund type among them. We then establish the sufficient and necessary conditions for the linear superposition of the discussed u‐linear operators and matrix differential operators with constant coefficients of arbitrary order to be Hamiltonian, which interestingly shows that the resulting Hamiltonian operators survive only up to the third differential order. Finally, we explore a few illustrative examples of integrable hierarchies from Hamiltonian pairs embedded in the resulting Hamiltonian operators. 

   more » « less
5. Graph-based prior and forward models for inverse problems on manifolds with boundaries

   https://doi.org/10.1088/1361-6420/ac3994  

   Harlim, John; Jiang, Shixiao W; Kim, Hwanwoo; Sanz-Alonso, Daniel (January 2022, Inverse Problems)

   Abstract This paper develops manifold learning techniques for the numerical solution of PDE-constrained Bayesian inverse problems on manifolds with boundaries. We introduce graphical Matérn-type Gaussian field priors that enable flexible modeling near the boundaries, representing boundary values by superposition of harmonic functions with appropriate Dirichlet boundary conditions. We also investigate the graph-based approximation of forward models from PDE parameters to observed quantities. In the construction of graph-based prior and forward models, we leverage the ghost point diffusion map algorithm to approximate second-order elliptic operators with classical boundary conditions. Numerical results validate our graph-based approach and demonstrate the need to design prior covariance models that account for boundary conditions. 

   more » « less