Circuit Minimization with QBF and SAT-Based Exact Synthesis @SimonsInstituteTOC

Simons Institute | Circuit Minimization with QBF and SAT-Based Exact Synthesis @SimonsInstituteTOC | Uploaded 2 months ago | Updated 21 hours ago
Stefan Szeider (TU Wien)
https://simons.berkeley.edu/talks/stefan-szeider-tu-wien-2024-07-03
Synthesis of Models and Systems

In this talk, we will present new methods for re-synthesizing Boolean circuits for minimizing the number of gates. The proposed method rewrites small subcircuits with exact synthesis, where Individual synthesis tasks are encoded as Quantified Boolean Formulas (QBFs) or as SAT (propositional satisfiability) instances. A key aspect of this approach is how it handles "don't cares," which provides additional flexibility. A prototype implementation allowed us to break the record on the number of gates for some benchmark instances. Joint work with Franz-Xaver Reichl and Friedrich Slivovsky.

Sublinear time algorithms for better than 1/2 approximation algorithms for max-cut on expanders

Counterexample-Guided Inference of Modular Specifications

Machine learning models of differential gene expression

Computing a fixed point of contraction maps in polynomial queries

Bioacoustics and Machine Learning as Key Tools in Conservation

$Hypothesis selection with computational constraints Maryam Aliakbarpour (Rice University) https://simons.berkeley.edu/talks/maryam-aliakbarpour-rice-university-2024-06-21 Extroverted Sublinear Algorithms Hypothesis selection is a fundamental problem in learning theory and statistics. Given a dataset and a finite set of candidate distributions, the goal is to select a distribution that matches the data as well as possible. More specifically, suppose we have sample access to an unknown distribution $P$ over a domain $mathcal{X}$. We assume that $P$ is well-approximated by one of $n$ distributions in a class (called hypotheses), denoted $mathcal{H} coloneqq {H_1, H_2, ldots, H_n}$. The goal is to design an algorithm that outputs a distribution $hat{H} in mathcal{H}$ whose total variation distance from $P$ is nearly minimal. In this work, we study the hypothesis selection problem under memory and time constraints. In particular, we discuss how to achieve a nearly optimal tradeoff between memory usage and sample complexity. Additionally, we explore methods to obtain optimal accuracy via algorithms with nearly optimal time complexity.$

Lessons from Texas, COVID-19, and the 737 Max: Efficiency vs. Resilience | Richard M. Karp...

Conditional Sampling for Distribution Testing

Sparsifying Set Systems for Coverage Problems

A Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches