research
∙
09/17/2023
Total Variation Distance Estimation Is as Easy as Probabilistic Inference
In this paper, we establish a novel connection between total variation (...
share
research
∙
08/08/2023
Tolerant Testing of High-Dimensional Samplers with Subcube Conditioning
We study the tolerant testing problem for high-dimensional samplers. Giv...
research
∙
06/25/2023
Solving the Identifying Code Set Problem with Grouped Independent Support
An important problem in network science is finding an optimal placement ...
research
∙
06/24/2023
On Scalable Testing of Samplers
In this paper we study the problem of testing of constrained samplers ov...
research
∙
06/19/2023
INC: A Scalable Incremental Weighted Sampler
The fundamental problem of weighted sampling involves sampling of satisf...
research
∙
06/19/2023
Scalable Probabilistic Routes
Inference and prediction of routes have become of interest over the past...
research
∙
06/17/2023
Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?
Given a Boolean formula ϕ over n variables, the problem of model countin...
research
∙
06/09/2023
Explaining SAT Solving Using Causal Reasoning
The past three decades have witnessed notable success in designing effic...
research
∙
05/16/2023
Rounding Meets Approximate Model Counting
The problem of model counting, also known as #SAT, is to compute the num...
research
∙
02/24/2023
Constraint Optimization over Semirings
Interpretations of logical formulas over semirings have applications in ...
research
∙
01/25/2023
Synthesis with Explicit Dependencies
Quantified Boolean Formulas (QBF) extend propositional logic with quanti...
research
∙
01/24/2023
Distinct Elements in Streams: An Algorithm for the (Text) Book
Given a data stream 𝒟 = ⟨ a_1, a_2, …, a_m ⟩ of m elements where each a_...
research
∙
12/19/2022
Fast Converging Anytime Model Counting
Model counting is a fundamental problem which has been influential in ma...
research
∙
11/22/2022
Support Size Estimation: The Power of Conditioning
We consider the problem of estimating the support size of a distribution...
research
∙
06/14/2022
On Approximating Total Variation Distance
Total variation distance (TV distance) is a fundamental notion of distan...
research
∙
06/02/2022
A Scalable Shannon Entropy Estimator
We revisit the well-studied problem of estimating the Shannon entropy of...
research
∙
06/01/2022
How Biased is Your Feature?: Computing Fairness Influence Functions with Global Sensitivity Analysis
Fairness in machine learning has attained significant focus due to the w...
research
∙
05/14/2022
Efficient Learning of Interpretable Classification Rules
Machine learning has become omnipresent with applications in various saf...
research
∙
02/21/2022
CCDD: A Tractable Representation for Model Counting and Uniform Sampling
Knowledge compilation concerns with the compilation of representation la...
research
∙
12/09/2021
Testing Probabilistic Circuits
Probabilistic circuits (PCs) are a powerful modeling framework for repre...
research
∙
10/18/2021
Arjun: An Efficient Independent Support Computation Technique and its Applications to Counting and Sampling
Given a Boolean formula φ over the set of variables X and a projection s...
research
∙
09/20/2021
Algorithmic Fairness Verification with Graphical Models
In recent years, machine learning (ML) algorithms have been deployed in ...
research
∙
08/12/2021
Engineering an Efficient Boolean Functional Synthesis Engine
Given a Boolean specification between a set of inputs and outputs, the p...
research
∙
05/24/2021
Partition Function Estimation: A Quantitative Study
Probabilistic graphical models have emerged as a powerful modeling tool ...
research
∙
05/19/2021
Program Synthesis as Dependency Quantified Formula Modulo Theory
Given a specification φ(X,Y) over inputs X and output Y, defined over a ...
research
∙
05/03/2021
Model Counting meets F0 Estimation
Constraint satisfaction problems (CSP's) and data stream models are two ...
research
∙
01/06/2021
Predicting Forest Fire Using Remote Sensing Data And Machine Learning
Over the last few decades, deforestation and climate change have caused ...
research
∙
10/24/2020
On Testing of Samplers
Given a set of items ℱ and a weight function 𝚠𝚝: ℱ↦ (0,1), the problem o...
research
∙
10/21/2020
Taming Discrete Integration via the Boon of Dimensionality
Discrete integration is a fundamental problem in computer science that c...
research
∙
09/14/2020
Justicia: A Stochastic SAT Approach to Formally Verify Fairness
As a technology ML is oblivious to societal good or bad, and thus, the f...
research
∙
08/14/2020
Induction Models on ℕ
Mathematical induction is a fundamental tool in computer science and mat...
research
∙
07/20/2020
Phase Transition Behavior in Knowledge Compilation
The study of phase transition behaviour in SAT has led to deeper underst...
research
∙
05/14/2020
Manthan: A Data Driven Approach for Boolean Function Synthesis
Boolean functional synthesis is a fundamental problem in computer scienc...
research
∙
05/11/2020
Designing New Phase Selection Heuristics
CDCL-based SAT solvers have transformed the field of automated reasoning...
research
∙
04/30/2020
Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice
Given a CNF formula F on n variables, the problem of model counting or #...
research
∙
02/17/2020
Scalable Quantitative Verification For Deep Neural Networks
Verifying security properties of deep neural networks (DNNs) is becoming...
research
∙
02/13/2020
Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning
We design efficient distance approximation algorithms for several classe...
research
∙
01/07/2020
IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules
The wide adoption of machine learning in the critical domains such as me...
research
∙
10/22/2019
Phase Transition Behavior of Cardinality and XOR Constraints
The runtime performance of modern SAT solvers is deeply connected to the...
research
∙
09/03/2019
Embedding Symbolic Knowledge into Deep Networks
In this work, we aim to leverage prior symbolic knowledge to improve the...
research
∙
06/25/2019
Quantitative Verification of Neural Networks And its Security Applications
Neural networks are increasingly employed in safety-critical domains. Th...
research
∙
12/11/2018
BOSPHORUS: Bridging ANF and CNF Solvers
Algebraic Normal Form (ANF) and Conjunctive Normal Form (CNF) are common...
research
∙
12/05/2018
MLIC: A MaxSAT-Based framework for learning interpretable classification rules
The wide adoption of machine learning approaches in the industry, govern...
research
∙
06/06/2018
Constrained Counting and Sampling: Bridging the Gap between Theory and Practice
Constrained counting and sampling are two fundamental problems in Comput...
research
∙
10/17/2017
The Hard Problems Are Almost Everywhere For Random CNF-XOR Formulas
Recent universal-hashing based approaches to sampling and counting cruci...
research
∙
10/14/2017
On Hashing-Based Approaches to Approximate DNF-Counting
Propositional model counting is a fundamental problem in artificial inte...
research
∙
12/21/2015
Constrained Sampling and Counting: Universal Hashing Meets SAT Solving
Constrained sampling and counting are two fundamental problems in artifi...
research
∙
11/24/2015
Approximate Probabilistic Inference via Word-Level Counting
Hashing-based model counting has emerged as a promising approach for lar...
research
∙
04/11/2014
