More Like this

1. NeuralSAT: A High-Performance Verification Tool for Deep Neural Networks

   https://doi.org/10.1007/978-3-031-98679-6_19  

   Duong, Hai; Nguyen, ThanhVu; Dwyer, Matthew B (July 2025, Springer Nature Switzerland)

   Abstract Deep Neural Networks (DNNs) are increasingly deployed in critical applications, where ensuring their safety and robustness is paramount. We present$$_\text {CAV25}$$ ${}_{\mathrm{CAV}25}$, a high-performance DNN verification tool that uses the DPLL(T) framework and supports a wide-range of network architectures and activation functions. Since its debut in VNN-COMP’23, in which it achieved the New Participant Award and ranked 4th overall,$$_\text {CAV25}$$ ${}_{\mathrm{CAV}25}$has advanced significantly, achieving second place in VNN-COMP’24. This paper presents and evaluates the latest development of$$_\text {CAV25}$$ ${}_{\mathrm{CAV}25}$, focusing on the versatility, ease of use, and competitive performance of the tool.$$_\text {CAV25}$$ ${}_{\mathrm{CAV}25}$is available at:https://github.com/dynaroars/neuralsat. 

   more » « less
2. Algorithms for covering multiple submodular constraints and applications

   https://doi.org/10.1007/s10878-022-00874-x  

   Chekuri, Chandra; Inamdar, Tanmay; Quanrud, Kent; Varadarajan, Kasturi; Zhang, Zhao (June 2022, Journal of Combinatorial Optimization)

   Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to R_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$ $f_1,f_2,\dots ,f_r$overNand requirements$$k_1,k_2,\ldots ,k_r$$ $k_1,k_2,\dots ,k_r$the goal is to find a minimum weight subset$$S \subseteq N$$ $S\subseteq N$such that$$f_i(S) \ge k_i$$ $f_i\left(S\right)\ge k_i$for$$1 \le i \le r$$ $1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$ $O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$ $k={\sum }_i{k}_i$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$ $(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{ϵ}logr)$in the cost. Second, we consider the special case when each$$f_i$$ $f_i$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems. 

   more » « less
3. Lower bounds for incidences

   https://doi.org/10.1007/s00222-025-01331-2  

   Cohen, Alex; Pohoata, Cosmin; Zakharov, Dmitrii (March 2025, Inventiones mathematicae)

   Abstract Let$$p_{1},\ldots ,p_{n}$$ $p_1,\dots ,p_n$be a set of points in the unit square and let$$T_{1},\ldots ,T_{n}$$ $T_1,\dots ,T_n$be a set of$$\delta $$ $\delta$-tubes such that$$T_{j}$$ $T_j$passes through$$p_{j}$$ $p_j$. We prove a lower bound for the number of incidences between the points and tubes under a natural regularity condition (similar to Frostman regularity). As a consequence, we show that in any configuration of points$$p_{1},\ldots , p_{n} \in [0,1]^{2}$$ $p_1,\dots ,p_n\in {[0,1]}^2$along with a line$$\ell _{j}$$ ${\ell }_j$through each point$$p_{j}$$ $p_j$, there exist$$j\neq k$$ $j\ne k$for which$$d(p_{j}, \ell _{k}) \lesssim n^{-2/3+o(1)}$$ $d(p_j,{\ell }_k)\lesssim n^{-2/3+o\left(1\right)}$. It follows from the latter result that any set of$$n$$ $n$points in the unit square contains three points forming a triangle of area at most$$n^{-7/6+o(1)}$$ $n^{-7/6+o\left(1\right)}$. This new upper bound for Heilbronn’s triangle problem attains the high-low limit established in our previous work arXiv:2305.18253. 

   more » « less
4. Global Well-Posedness for $$H^{-1}(\mathbb {R})$$ Perturbations of KdV with Exotic Spatial Asymptotics

   https://doi.org/10.1007/s00220-022-04522-7  

   Laurens, Thierry (November 2022, Communications in Mathematical Physics)

   Abstract Given a suitable solutionV(t, x) to the Korteweg–de Vries equation on the real line, we prove global well-posedness for initial data$$u(0,x) \in V(0,x) + H^{-1}(\mathbb {R})$$ $u(0,x)\in V(0,x)+H^{-1}\left(R\right)$. Our conditions onVdo include regularity but do not impose any assumptions on spatial asymptotics. We show that periodic profiles$$V(0,x)\in H^5(\mathbb {R}/\mathbb {Z})$$ $V(0,x)\in H^5(R/Z)$satisfy our hypotheses. In particular, we can treat localized perturbations of the much-studied periodic traveling wave solutions (cnoidal waves) of KdV. In the companion paper Laurens (Nonlinearity. 35(1):343–387, 2022.https://doi.org/10.1088/1361-6544/ac37f5) we show that smooth step-like initial data also satisfy our hypotheses. We employ the method of commuting flows introduced in Killip and Vişan (Ann. Math. (2) 190(1):249–305, 2019.https://doi.org/10.4007/annals.2019.190.1.4) where$$V\equiv 0$$ $V\equiv 0$. In that setting, it is known that$$H^{-1}(\mathbb {R})$$ $H^{-1}\left(R\right)$is sharp in the class of$$H^s(\mathbb {R})$$ $H^s\left(R\right)$spaces. 

   more » « less
5. On the Support of Anomalous Dissipation Measures

   https://doi.org/10.1007/s00021-024-00894-z  

   De_Rosa, Luigi; Drivas, Theodore D; Inversi, Marco (November 2024, Journal of Mathematical Fluid Mechanics)

   Abstract By means of a unifying measure-theoretic approach, we establish lower bounds on the Hausdorff dimension of the space-time set which can support anomalous dissipation for weak solutions of fluid equations, both in the presence or absence of a physical boundary. Boundary dissipation, which can occur at both the time and the spatial boundary, is analyzed by suitably modifying the Duchon & Robert interior distributional approach. One implication of our results is that any bounded Euler solution (compressible or incompressible) arising as a zero viscosity limit of Navier–Stokes solutions cannot have anomalous dissipation supported on a set of dimension smaller than that of the space. This result is sharp, as demonstrated by entropy-producing shock solutions of compressible Euler (Drivas and Eyink in Commun Math Phys 359(2):733–763, 2018.https://doi.org/10.1007/s00220-017-3078-4; Majda in Am Math Soc 43(281):93, 1983.https://doi.org/10.1090/memo/0281) and by recent constructions of dissipative incompressible Euler solutions (Brue and De Lellis in Commun Math Phys 400(3):1507–1533, 2023.https://doi.org/10.1007/s00220-022-04626-0 624; Brue et al. in Commun Pure App Anal, 2023), as well as passive scalars (Colombo et al. in Ann PDE 9(2):21–48, 2023.https://doi.org/10.1007/s40818-023-00162-9; Drivas et al. in Arch Ration Mech Anal 243(3):1151–1180, 2022.https://doi.org/10.1007/s00205-021-01736-2). For$$L^q_tL^r_x$$ $L_t^q{L}_x^r$suitable Leray–Hopf solutions of the$$d-$$ $d-$dimensional Navier–Stokes equation we prove a bound of the dissipation in terms of the Parabolic Hausdorff measure$$\mathcal {P}^{s}$$ $P^s$, which gives$$s=d-2$$ $s=d-2$as soon as the solution lies in the Prodi–Serrin class. In the three-dimensional case, this matches with the Caffarelli–Kohn–Nirenberg partial regularity. 

   more » « less