Author name cluster

Kuldeep Meel

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.

4 papers

1 author row

Highlights Conference 2023 Conference Abstract

Distinct Elements in Streams: An Algorithm for the (Text) Book

Kuldeep Meel

Given a data stream of m elements, the Distinct Elements problem is to estimate the number of distinct elements in the stream. Distinct Elements has been a subject of theoretical and empirical investigations over the past four decades resulting in space-optimal algorithms for it. However, all the current state-of-the-art algorithms are often difficult to analyze or impractical. I will present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with a knowledge of basic probability theory. In addition to the simplicity, the approach has significant theoretical and practical implications: our approach allowed us to resolve the open problem of (Discrete) Klee's Measure Problem in the streaming setting and build a state-of-the-art DNF counter in practice. Relevant publication: https: //arxiv. org/abs/2301. 10191 Contributed talk given by Kuldeep Meel Lunch Thursday 14h00 - 15h24, Contributed Talks Formal Methods and Learning | HS 3 | chair: Djordje Zikelic Automata, Algebra & Languages | HS 4 | chair: Mikolaj Bojanczyk Formal Methods and Learning | HS 3 | chair: Djordje Zikelic Automata, Algebra & Languages | HS 4 | chair: Mikolaj Bojanczyk

Details

AAAI Conference 2017 Conference Paper

Counting-Based Reliability Estimation for Power-Transmission Grids

Leonardo Duenas-Osorio
Kuldeep Meel
Roger Paredes
Moshe Vardi

Modern society is increasingly reliant on the functionality of infrastructure facilities and utility services. Consequently, there has been surge of interest in the problem of quantiﬁcation of system reliability, which is known to be #P-complete. Reliability also contributes to the resilience of systems, so as to effectively make them bounce back after contingencies. Despite diverse progress, most techniques to estimate system reliability and resilience remain computationally expensive. In this paper, we investigate how recent advances in hashingbased approaches to counting can be exploited to improve computational techniques for system reliability. The primary contribution of this paper is a novel framework, RelNet, that reduces the problem of computing reliability for a given network to counting the number of satisfying assignments of a Σ1 1 formula, which is amenable to recent hashing-based techniques developed for counting satisfying assignments of SAT formula. We then apply RelNet to ten real world powertransmission grids across different cities in the U. S. and are able to obtain, to the best of our knowledge, the ﬁrst theoretically sound a priori estimates of reliability between several pairs of nodes of interest. Such estimates will help managing uncertainty and support rational decision making for community resilience.

PDF Details

AAAI Conference 2016 Conference Paper

Approximate Probabilistic Inference via Word-Level Counting

Supratik Chakraborty
Kuldeep Meel
Rakesh Mistry
Moshe Vardi

Hashing-based model counting has emerged as a promising approach for large-scale probabilistic inference on graphical models. A key component of these techniques is the use of xor-based 2-universal hash functions that operate over Boolean domains. Many counting problems arising in probabilistic inference are, however, naturally encoded over ﬁnite discrete domains. Techniques based on bit-level (or Boolean) hash functions require these problems to be propositionalized, making it impossible to leverage the remarkable progress made in SMT (Satisﬁability Modulo Theory) solvers that can reason directly over words (or bit-vectors). In this work, we present the ﬁrst approximate model counter that uses word-level hashing functions, and can directly leverage the power of sophisticated SMT solvers. Empirical evaluation over an extensive suite of benchmarks demonstrates the promise of the approach.

PDF Details

AAAI Conference 2014 Conference Paper

Distribution-Aware Sampling and Weighted Model Counting for SAT

Supratik Chakraborty
Daniel Fremont
Kuldeep Meel
Sanjit Seshia
Moshe Vardi

Given a CNF formula and a weight for each assignment of values to variables, two natural problems are weighted model counting and distribution-aware sampling of satisfying assignments. Both problems have a wide variety of important applications. Due to the inherent complexity of the exact versions of the problems, interest has focused on solving them approximately. Prior work in this area scaled only to small problems in practice, or failed to provide strong theoretical guarantees, or employed a computationally-expensive most-probable-explanation (MPE) queries that assumes prior knowledge of a factored representation of the weight distribution. We identify a novel parameter, tilt, which is the ratio of the maximum weight of satisfying assignment to minimum weight of satisfying assignment and present a novel approach that works with a black-box oracle for weights of assignments and requires only an NP-oracle (in practice, a SAT-solver) to solve both the counting and sampling problems when the tilt is small. Our approach provides strong theoretical guarantees, and scales to problems involving several thousand variables. We also show that the assumption of small tilt can be significantly relaxed while improving computational efficiency if a factored representation of the weights is known.

PDF Details