More Like this

1. Reduction games, provability and compactness

   https://doi.org/10.1142/S021906132250009X  

   Dzhafarov, Damir D. ; Hirschfeldt, Denis R. ; Reitzes, Sarah ( December 2022 , Journal of Mathematical Logic)

   Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [Formula: see text] principles over [Formula: see text]-models of [Formula: see text]. They also introduced a version of this game that similarly captures provability over [Formula: see text]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [Formula: see text] between two principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between [Formula: see text] principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [Formula: see text], uncovering new differences between their logical strengths. 

   more » « less
2. Residually finite dimensional algebras and polynomial almost identities

   https://doi.org/10.1142/S0219498822500384  

   Larsen, Michael ; Shalev, Aner ( February 2022 , Journal of Algebra and Its Applications)

   Let [Formula: see text] be a residually finite dimensional algebra (not necessarily associative) over a field [Formula: see text]. Suppose first that [Formula: see text] is algebraically closed. We show that if [Formula: see text] satisfies a homogeneous almost identity [Formula: see text], then [Formula: see text] has an ideal of finite codimension satisfying the identity [Formula: see text]. Using well known results of Zelmanov, we conclude that, if a residually finite dimensional Lie algebra [Formula: see text] over [Formula: see text] is almost [Formula: see text]-Engel, then [Formula: see text] has a nilpotent (respectively, locally nilpotent) ideal of finite codimension if char [Formula: see text] (respectively, char [Formula: see text]). Next, suppose that [Formula: see text] is finite (so [Formula: see text] is residually finite). We prove that, if [Formula: see text] satisfies a homogeneous probabilistic identity [Formula: see text], then [Formula: see text] is a coset identity of [Formula: see text]. Moreover, if [Formula: see text] is multilinear, then [Formula: see text] is an identity of some finite index ideal of [Formula: see text]. Along the way we show that if [Formula: see text] has degree [Formula: see text], and [Formula: see text] is a finite [Formula: see text]-algebra such that the probability that [Formula: see text] (where [Formula: see text] are randomly chosen) is at least [Formula: see text], then [Formula: see text] is an identity of [Formula: see text]. This solves a ring-theoretic analogue of a (still open) group-theoretic problem posed by Dixon, 

   more » « less
3. The Information Bottleneck and Geometric Clustering

   https://doi.org/10.1162/neco_a_01136  

   Strouse, DJ ; Schwab, David J. ( March 2019 , Neural Computation)

   The information bottleneck (IB) approach to clustering takes a joint distribution [Formula: see text] and maps the data [Formula: see text] to cluster labels [Formula: see text], which retain maximal information about [Formula: see text] (Tishby, Pereira, & Bialek, 1999 ). This objective results in an algorithm that clusters data points based on the similarity of their conditional distributions [Formula: see text]. This is in contrast to classic geometric clustering algorithms such as [Formula: see text]-means and gaussian mixture models (GMMs), which take a set of observed data points [Formula: see text] and cluster them based on their geometric (typically Euclidean) distance from one another. Here, we show how to use the deterministic information bottleneck (DIB) (Strouse & Schwab, 2017 ), a variant of IB, to perform geometric clustering by choosing cluster labels that preserve information about data point location on a smoothed data set. We also introduce a novel intuitive method to choose the number of clusters via kinks in the information curve. We apply this approach to a variety of simple clustering problems, showing that DIB with our model selection procedure recovers the generative cluster labels. We also show that, in particular limits of our model parameters, clustering with DIB and IB is equivalent to [Formula: see text]-means and EM fitting of a GMM with hard and soft assignments, respectively. Thus, clustering with (D)IB generalizes and provides an information-theoretic perspective on these classic algorithms. 

   more » « less
4. Network Inspection for Detecting Strategic Attacks

   https://doi.org/10.1287/opre.2021.2180  

   Dahan, Mathieu ; Sela, Lina ; Amin, Saurabh ( March 2022 , Operations Research)

   This article studies a problem of strategic network inspection, in which a defender (agency) is tasked with detecting the presence of multiple attacks in the network. An inspection strategy entails monitoring the network components, possibly in a randomized manner, using a given number of detectors. We formulate the network inspection problem [Formula: see text] as a large-scale bilevel optimization problem, in which the defender seeks to determine an inspection strategy with minimum number of detectors that ensures a target expected detection rate under worst-case attacks. We show that optimal solutions of [Formula: see text] can be obtained from the equilibria of a large-scale zero-sum game. Our equilibrium analysis involves both game-theoretic and combinatorial arguments and leads to a computationally tractable approach to solve [Formula: see text]. First, we construct an approximate solution by using solutions of minimum set cover (MSC) and maximum set packing (MSP) problems and evaluate its detection performance. In fact, this construction generalizes some of the known results in network security games. Second, we leverage properties of the optimal detection rate to iteratively refine our MSC/MSP-based solution through a column generation procedure. Computational results on benchmark water networks demonstrate the scalability, performance, and operational feasibility of our approach. The results indicate that utilities can achieve a high level of protection in large-scale networks by strategically positioning a small number of detectors. 

   more » « less
5. The Littlewood–Paley decomposition for periodic functions and applications to the Boussinesq equations

   https://doi.org/10.1142/s0219530519500234  

   Dai, Yichen ; Hu, Weiwei ; Wu, Jiahong ; Xiao, Bei ( July 2020 , Analysis and Applications)

   The Littlewood–Paley decomposition for functions defined on the whole space [Formula: see text] and related Besov space techniques have become indispensable tools in the study of many partial differential equations (PDEs) with [Formula: see text] as the spatial domain. This paper intends to develop parallel tools for the periodic domain [Formula: see text]. Taking advantage of the boundedness and convergence theory on the square-cutoff Fourier partial sum, we define the Littlewood–Paley decomposition for periodic functions via the square cutoff. We remark that the Littlewood–Paley projections defined via the circular cutoff in [Formula: see text] with [Formula: see text] in the literature do not behave well on the Lebesgue space [Formula: see text] except for [Formula: see text]. We develop a complete set of tools associated with this decomposition, which would be very useful in the study of PDEs defined on [Formula: see text]. As an application of the tools developed here, we study the periodic weak solutions of the [Formula: see text]-dimensional Boussinesq equations with the fractional dissipation [Formula: see text] and without thermal diffusion. We obtain two main results. The first assesses the global existence of [Formula: see text]-weak solutions for any [Formula: see text] and the existence and uniqueness of the [Formula: see text]-weak solutions when [Formula: see text] for [Formula: see text]. The second establishes the zero thermal diffusion limit with an explicit convergence rate. 

   more » « less