Author name cluster

Jonathan Lenchner

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

MFCS Conference 2024 Conference Paper

On the Number of Quantifiers Needed to Define Boolean Functions

Marco Carmosino
Ronald Fagin
Neil Immerman
Phokion G. Kolaitis
Jonathan Lenchner
Rik Sengupta

The number of quantifiers needed to express first-order (FO) properties is captured by two-player combinatorial games called multi-structural games. We analyze these games on binary strings with an ordering relation, using a technique we call parallel play, which significantly reduces the number of quantifiers needed in many cases. Ordered structures such as strings have historically been notoriously difficult to analyze in the context of these and similar games. Nevertheless, in this paper, we provide essentially tight bounds on the number of quantifiers needed to characterize different-sized subsets of strings. The results immediately give bounds on the number of quantifiers necessary to define several different classes of Boolean functions. One of our results is analogous to Lupanov’s upper bounds on circuit size and formula size in propositional logic: we show that every Boolean function on n-bit inputs can be defined by a FO sentence having (1+ε)n/log(n) + O(1) quantifiers, and that this is essentially tight. We reduce this number to (1 + ε)log(n) + O(1) when the Boolean function in question is sparse.

Details

NeSy Conference 2022 Conference Paper

Combining Fast and Slow Thinking for Human-like and Efficient Decisions in Constrained Environments

Marianna Bergamaschi Ganapini
Murray Campbell
Francesco Fabiano
Lior Horesh
Jonathan Lenchner
Andrea Loreggia
Nicholas Mattei
Francesca Rossi 0001

Current AI systems lack several important human capabilities, such as adaptability, generalizability, selfcontrol, consistency, common sense, and causal reasoning. We believe that existing cognitive theories of human decision making, such as the thinking fast and slow theory, can provide insights on how to advance AI systems towards some of these capabilities. In this paper, we propose a general architecture that is based on fast/slow solvers and a metacognitive component. We then present experimental results on the behavior of an instance of this architecture, for AI systems that make decisions about navigating in a constrained environment. We show how combining the fast and slow decision modalities, which can be implemented by learning and reasoning components respectively, allows the system to evolve over time and gradually pass from slow to fast thinking with enough experience, and that this greatly helps in decision quality, resource consumption, and efficiency.

Details

MFCS Conference 2022 Conference Paper

On the Number of Quantifiers as a Complexity Measure

Ronald Fagin
Jonathan Lenchner
Nikhil Vyas 0001
R. Ryan Williams

In 1981, Neil Immerman described a two-player game, which he called the "separability game" [Neil Immerman, 1981], that captures the number of quantifiers needed to describe a property in first-order logic. Immerman’s paper laid the groundwork for studying the number of quantifiers needed to express properties in first-order logic, but the game seemed to be too complicated to study, and the arguments of the paper almost exclusively used quantifier rank as a lower bound on the total number of quantifiers. However, last year Fagin, Lenchner, Regan and Vyas [Fagin et al. , 2021] rediscovered the game, provided some tools for analyzing them, and showed how to utilize them to characterize the number of quantifiers needed to express linear orders of different sizes. In this paper, we push forward in the study of number of quantifiers as a bona fide complexity measure by establishing several new results. First we carefully distinguish minimum number of quantifiers from the more usual descriptive complexity measures, minimum quantifier rank and minimum number of variables. Then, for each positive integer k, we give an explicit example of a property of finite structures (in particular, of finite graphs) that can be expressed with a sentence of quantifier rank k, but where the same property needs 2^Ω(k²) quantifiers to be expressed. We next give the precise number of quantifiers needed to distinguish two rooted trees of different depths. Finally, we give a new upper bound on the number of quantifiers needed to express s-t connectivity, improving the previous known bound by a constant factor.

Details

Highlights Conference 2021 Conference Abstract

New Progress with a Forgotten Logical Game

Jonathan Lenchner

We describe our rediscovery of an intriguing logical game, introduced by Immerman in 1981, but then, until now, never again mentioned in the literature. The game is played on two sets and of structures. These multi-structural games generalize Ehrenfeucht-Fraisse games. Whereas Ehrenfeucht-Fraisse games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the -round game if and only if there is a first-order sentence with at most quantifiers, where every structure in satisfies and no structure in satisfies. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders.

Details

AAAI Conference 2021 Conference Paper

Thinking Fast and Slow in AI

Grady Booch
Francesco Fabiano
Lior Horesh
Kiran Kate
Jonathan Lenchner
Nick Linck
Andreas Loreggia
Keerthiram Murgesan

This paper proposes a research direction to advance AI which draws inspiration from cognitive theories of human decision making. The premise is that if we gain insights about the causes of some human capabilities that are still lacking in AI (for instance, adaptability, generalizability, common sense, and causal reasoning), we may obtain similar capabilities in an AI system by embedding these causal components. We hope that the high-level description of our vision included in this paper, as well as the several research questions that we propose to consider, can stimulate the AI research community to define, try and evaluate new methodologies, frameworks, and evaluation metrics, in the spirit of achieving a better understanding of both human and machine intelligence.

PDF Details

ICRA Conference 2011 Conference Paper

Robotic mapping and monitoring of data centers

Christopher R. Mansley
Jonathan Connell
Canturk Isci
Jonathan Lenchner
Jeffrey O. Kephart
Suzanne McIntosh
Michael Schappert

We describe an inexpensive autonomous robot capable of navigating previously unseen data centers and monitoring key metrics such as air temperature 1. The robot provides real-time navigation and sensor data to commercial IBM software, thereby enabling real-time generation of the data center layout, a thermal map and other visualizations of energy dynamics. Once it has mapped a data center, the robot can efficiently monitor it for hot spots and other anomalies using intelligent sampling. We demonstrate the robot's effectiveness via experimental studies from two production data centers.

Details