More Like this

1. On Quantifying Literals in Boolean Logic and its Applications to Explainable AI (Extended Abstract)

   https://doi.org/10.24963/ijcai.2022/797  

   Darwiche, Adnan; Marquis, Pierre (July 2022, International Joint Conference on Artificial Intelligence (IJCAI))

   Quantified Boolean logic results from adding operators to Boolean logic for existentially and universally quantifying variables. This extends the reach of Boolean logic by enabling a variety of applications that have been explored over the decades. The existential quantification of literals (variable states) and its applications have also been studied in the literature. We complement this by studying universal literal quantification and its applications, particularly to explainable AI. We also provide a novel semantics for quantification and discuss the interplay between variable/literal and existential/universal quantification. We further identify classes of Boolean formulas and circuits that allow efficient quantification. Literal quantification is more fine-grained than variable quantification, which leads to a refinement of quantified Boolean logic with literal quantification as its primitive. 

   more » « less
2. A Diophantine definition of the constants in ℚ(𝕫)

   https://doi.org/10.1090/proc/17034  

   Garcia-Fritz, Natalia; Pasten, Hector (February 2025, Proceedings of the American Mathematical Society)

   It is an old problem in the area of Diophantine definability to determine whether $\mathbb{Q}$is Diophantine in $\mathbb{Q}\left(z\right)$. Conditional on two standard conjectures on elliptic surfaces, we provide a positive answer; namely, we show that such a Diophantine definition exists. 

   more » « less
3. InFillmore: Frame-Guided Language Generation with Bidirectional Context

   https://doi.org/10.18653/v1/2021.starsem-1.12  

   Ou, J.; Weir, N.; Belyy, A.; Yu, F.; Van Durme, B. (August 2021, Proceedings of the 10th Conference on Lexical and Computational Semantics)

   null (Ed.)

   We propose a structured extension to bidirectional-context conditional language generation, or “infilling,” inspired by Frame Semantic theory (Fillmore, 1976). Guidance is provided through two approaches: (1) model fine-tuning, conditioning directly on observed symbolic frames, and (2) a novel extension to disjunctive lexically constrained decoding that leverages frame semantic lexical units. Automatic and human evaluations confirm that frame-guided generation allows for explicit manipulation of intended infill semantics, with minimal loss in distinguishability from human-generated text. Our methods flexibly apply to a variety of use scenarios, and we provide an interactive web demo 

   more » « less
4. The Impact of Literal Sorting on Cardinality Constraint Encodings

   https://doi.org/10.1609/aaai.v39i11.33232  

   Reeves, Joseph E; Filipe, João; Hsu, Min-Chien; Martins, Ruben; Heule, Marijn_J H (April 2025, Proceedings of the AAAI Conference on Artificial Intelligence)

   The effectiveness of satisfiability solvers strongly depends on the quality of the encoding of a given problem into conjunctive normal form. Cardinality constraints are prevalent in numerous problems, prompting the development and study of various types of encoding. We present a novel approach to optimizing cardinality constraint encodings by exploring the impact of literal orderings within the constraints. By strategically placing related literals nearby each other, the encoding generates auxiliary variables in a hierarchical structure, enabling the solver to reason more abstractly about groups of related literals. Unlike conventional metrics such as formula size or propagation strength, our method leverages structural properties of the formula to redefine the roles of auxiliary variables to enhance the solver's learning capabilities. The experimental evaluation on benchmarks from the maximum satisfiability competition demonstrates that literal orderings can be more influential than the choice of the encoding type. Our literal ordering technique improves solver performance across various encoding techniques, underscoring the robustness of our approach. 

   more » « less
5. Act the Part: Learning Interaction Strategies for Articulated Object Part Discovery

   Gadre, Samir Yitzhak; Ehsani, Kiana; Song, Shuran (October 2021, Proceedings)

   People often use physical intuition when manipulating articulated objects, irrespective of object semantics. Motivated by this observation, we identify an important embodied task where an agent must play with objects to recover their parts. To this end, we introduce Act the Part (AtP) to learn how to interact with articulated objects to discover and segment their pieces. By coupling action selection and motion segmentation, AtP is able to isolate structures to make perceptual part recovery possible without semantic labels. Our experiments show AtP learns efficient strategies for part discovery, can generalize to unseen categories, and is capable of conditional reasoning for the task. Although trained in simulation, we show convincing transfer to real world data with no fine-tuning. A summery video, interactive demo, and code will be available at atp.cs.columbia.edu. 

   more » « less