Cover Image

Engineering an Efficient Approximate DNF-Counter

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Soos, Mate, Sarkar, Uddalok, Aggarwal, Divesh, Chakraborty, Sourav, Meel, Kuldeep S., Obremski, Maciej
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Equivalence Testing: The Power of Bounded Adaptivity
by: Chakraborty, Diptarka, et al.
Published: (2024)

Instance Dependent Testing of Samplers using Interval Conditioning
by: Bhattacharyya, Rishiraj, et al.
Published: (2025)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

#CFG and #DNNF admit FPRAS
by: Meel, Kuldeep S., et al.
Published: (2024)

An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs
by: Meel, Kuldeep S., et al.
Published: (2024)

Towards practical FPRAS for #NFA: Exploiting the Power of Dependence
by: Meel, Kuldeep S., et al.
Published: (2025)

Approximating Queries on Probabilistic Graphs
by: Amarilli, Antoine, et al.
Published: (2023)

Scalable Algorithms for Approximate DNF Model Counting
by: Burkhardt, Paul, et al.
Published: (2026)

Distance Estimation for High-Dimensional Discrete Distributions
by: Kumar, Gunjan, et al.
Published: (2023)

Invertible Bloom Lookup Tables with Less Memory and Randomness
by: Fleischhacker, Nils, et al.
Published: (2023)

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
by: Aggarwal, Divesh, et al.
Published: (2024)

Algorithms Transcending the SAT-Symmetry Interface
by: Anders, Markus, et al.
Published: (2023)

DNF Learning via Locally Mixing Random Walks
by: Alman, Josh, et al.
Published: (2025)

Recursive lattice reduction -- A framework for finding short lattice vectors
by: Aggarwal, Divesh, et al.
Published: (2023)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
by: Aggarwal, Divesh, et al.
Published: (2025)

DNF formulas are efficiently testable with relative error
by: Chen, Xi, et al.
Published: (2026)

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
by: Aggarwal, Divesh, et al.
Published: (2020)

Enumerating models of DNF faster: breaking the dependency on the formula size
by: Capelli, Florent, et al.
Published: (2018)

Computational Explorations of Total Variation Distance
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Algorithms and Hardness for Estimating Statistical Similarity
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Learning DNF through Generalized Fourier Representations
by: Heidari, Mohsen, et al.
Published: (2025)

Mind the Gap? Not for SVP Hardness under ETH!
by: Aggarwal, Divesh, et al.
Published: (2025)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
by: Chakraborty, Sourav, et al.
Published: (2024)

From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation
by: Großmann, Ernestine, et al.
Published: (2025)

Sum-Of-Squares To Approximate Knapsack
by: Kothari, Pravesh K., et al.
Published: (2025)

Efficient and Practical Approximation Algorithms for Advertising in Content Feeds
by: Zhang, Guangyi, et al.
Published: (2025)

Clustering under Constraints: Efficient Parameterized Approximation Schemes
by: Bhore, Sujoy, et al.
Published: (2025)

RSVP: Beyond Weisfeiler Lehman Graph Isomorphism Test
by: Dutta, Sourav, et al.
Published: (2024)

Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
by: Andoni, Alexandr, et al.
Published: (2026)

Towards Efficient Data Structures for Approximate Search with Range Queries
by: Kian, Ladan, et al.
Published: (2026)

Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint
by: Rui, Xiaobin, et al.
Published: (2025)

Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion
by: McCauley, Samuel
Published: (2024)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
by: Kobayashi, Yasuaki, et al.
Published: (2020)

Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
by: Adudodla, Ankith Reddy, et al.
Published: (2025)

Assessing the Quality of Binomial Samplers: A Statistical Distance Framework
by: Sarkar, Uddalok, et al.
Published: (2025)

Online facility location with weights and congestion
by: Chakraborty, Arghya, et al.
Published: (2022)

Approximating $δ$-Covering
by: Hartmann, Tim A., et al.
Published: (2024)

On Approximating Cutwidth and Pathwidth
by: Bansal, Nikhil, et al.
Published: (2023)