More Like this

1. Approximate polymorphisms

   https://doi.org/10.1145/3519935.3519966  

   Chase, Gilad; Filmus, Yuval; Minzer, Dor; Mossel, Elchanan; Saurabh, Nitin (January 2022, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing)
2. Approximate Sketches

   https://doi.org/10.1145/3639321  

   Tsan, Brian; Datta, Asoke; Izenov, Yesdaulet; Rusu, Florin (March 2024, Proceedings of the ACM on Management of Data)

   Sketches are single-pass small-space data summaries that can quickly estimate the cardinality of join queries. However, sketches are not directly applicable to join queries with dynamic filter conditions --- where arbitrary selection predicate(s) are applied --- since a sketch is limited to a fixed selection. While multiple sketches for various selections can be used in combination, they each incur individual storage and maintenance costs. Alternatively, exact sketches can be built during runtime for every selection. To make this process scale, a high-degree of parallelism --- available in hardware accelerators such as GPUs --- is required. Therefore, sketch usage for cardinality estimation in query optimization is limited. Following recent work that applies transformers to cardinality estimation, we design a novel learning-based method to approximate the sketch of any arbitrary selection, enabling sketches for join queries with filter conditions. We train a transformer on each table to estimate the sketch of any subset of the table, i.e., any arbitrary selection. Transformers achieve this by learning the joint distribution amongst table attributes, which is equivalent to a multidimensional sketch. Subsequently, transformers can approximate any sketch, enabling sketches for join cardinality estimation. In turn, estimating joins via approximate sketches allows tables to be modeled individually and thus scales linearly with the number of tables. We evaluate the accuracy and efficacy of approximate sketches on queries with selection predicates consisting of conjunctions of point and range conditions. Approximate sketches achieve similar accuracy to exact sketches with at least one order of magnitude less overhead. 

   more » « less
3. Securing Approximate Computing Systems via Obfuscating Approximate-Precise Boundary

   https://doi.org/10.1109/TCAD.2022.3168261  

   Yellu, Pruthvy; Yu, Qiaoyan (September 2022, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems)
4. Approximate causal abstraction

   Beckers, Sander; Eberhardt, Frederick; Halpern, Joseph Y. (July 2019, 35th Conference on Uncertainty in AI (UAI 2019))

   Scientific models describe natural phenomena at different levels of abstraction. Abstract descriptions can provide the basis for interventions on the system and explanation of observed phenomena at a level of granularity that is coarser than the most fundamental account of the system. Beckers and Halpern [2019], building on work of Rubenstein et al.[2017], developed an account of \emph{abstraction} for causal models that is exact. Here we extend this account to the more realistic case where an abstract causal model offers only an approximation of the underlying system. We show how the resulting account handles the discrepancy that can arise between low- and high-level causal models of the same system, and in the process provide an account of how one causal model approximates another, a topic of independent interest. Finally, we extend the account of approximate abstractions to probabilistic causal models, indicating how and where uncertainty can enter into an approximate abstraction. 

   more » « less
5. Approximate Causal Abstractions

   Beckers, Sander; Eberhardt, Frederick; Halpern, Joseph (January 2019, Proceedings of Uncertainty in Artificial Intelligence (UAI))

   Scientific models describe natural phenomena at different levels of abstraction. Abstract de- scriptions can provide the basis for interven- tions on the system and explanation of ob- served phenomena at a level of granularity that is coarser than the most fundamental account of the system. Beckers and Halpern (2019), building on work of Rubenstein et al. (2017), developed an account of abstraction for causal models that is exact. Here we extend this account to the more realistic case where an abstract causal model offers only an approx- imation of the underlying system. We show how the resulting account handles the discrep- ancy that can arise between low- and high- level causal models of the same system, and in the process provide an account of how one causal model approximates another, a topic of independent interest. Finally, we extend the account of approximate abstractions to prob- abilistic causal models, indicating how and where uncertainty can enter into an approxi- mate abstraction. 

   more » « less