More Like this

1. Testing k-Monotonicity

   Canonne, C; Grigorescu, E.; Guo, S; Kumar, A; Wimmer, K. (January 2017, ITCS)

   A Boolean {\em $$k$$-monotone} function defined over a finite poset domain $${\cal D}$$ alternates between the values $$0$$ and $$1$$ at most $$k$$ times on any ascending chain in $${\cal D}$$. Therefore, $$k$$-monotone functions are natural generalizations of the classical {\em monotone} functions, which are the {\em $$1$$-monotone} functions. Motivated by the recent interest in $$k$$-monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing, we initiate a systematic study of $$k$$-monotone functions, in the property testing model. In this model, the goal is to distinguish functions that are $$k$$-monotone (or are close to being $$k$$-monotone) from functions that are far from being $$k$$-monotone. Our results include the following: \begin{enumerate} \item We demonstrate a separation between testing $$k$$-monotonicity and testing monotonicity, on the hypercube domain $$\{0,1\}^d$$, for $$k\geq 3$$; \item We demonstrate a separation between testing and learning on $$\{0,1\}^d$$, for $$k=\omega(\log d)$$: testing $$k$$-monotonicity can be performed with $$2^{O(\sqrt d \cdot \log d\cdot \log{1/\eps})}$$ queries, while learning $$k$$-monotone functions requires $$2^{\Omega(k\cdot \sqrt d\cdot{1/\eps})}$$ queries (Blais et al. (RANDOM 2015)). \item We present a tolerant test for functions $$f\colon[n]^d\to \{0,1\}$$ with complexity independent of $$n$$, which makes progress on a problem left open by Berman et al. (STOC 2014). \end{enumerate} Our techniques exploit the testing-by-learning paradigm, use novel applications of Fourier analysis on the grid $$[n]^d$, and draw connections to distribution testing techniques. 

   more » « less
2. Relationships between Global and Local Monotonicity of Operator

   Khanh, PD; Khoa, VVH; Martinez-Legaz, JE; Mordukhovich, BS (January 2025, Journal of Convex Analysis)

   The paper is devoted to establishing relationships between global and local monotonicity, as well as their maximality versions, for single-valued and set-valued mappings between fnite-dimensional and infnite-dimensional spaces. We frst show that for single-valued operators with convex domains in locally convex topological spaces, their continuity ensures that their global monotonicity agrees with the local one around any point of the graph. This also holds for set-valued mappings defned on the real line under a certain connectedness condition. The situation is diferent for set-valued operators in multidimensional spaces as demonstrated by an example of locally monotone operator on the plane that is not globally monotone. Finally, we invoke coderivative criteria from variational analysis to characterize both global and local maximal monotonicity of set-valued operators in Hilbert spaces to verify the equivalence between these monotonicity properties under the closedgraph and global hypomonotonicity assumptions. 

   more » « less
3. Measure of genuine coherence based of quasi-relative entropy

   Vershynina, Anna (February 2021, ArXivorg)

   null (Ed.)

   We present a genuine coherence measure based on a quasi-relative entropy as a difference between quasientropies of the dephased and the original states. The measure satisfies non-negativity and monotonicity under genuine incoherent operations (GIO). It is strongly monotone under GIO in two- and three-dimensions, or for pure states in any dimension, making it a genuine coherence monotone. We provide a bound on the error term in the monotonicity relation in terms of the trace distance between the original and the dephased states. Moreover, the lower bound on the coherence measure can also be calculated in terms of this trace distance. 

   more » « less
4. Improved Monotonicity Testers via Hypercube Embeddings

   https://doi.org/10.4230/LIPIcs.ITCS.2023.25  

   Braverman, Mark; Khot, Subhash; Kindler, Guy; Minzer, Dor (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Tauman_Kalai, Yael (Ed.)

   We show improved monotonicity testers for the Boolean hypercube under the p-biased measure, as well as over the hypergrid [m]ⁿ. Our results are: 1) For any p ∈ (0,1), for the p-biased hypercube we show a non-adaptive tester that makes Õ(√n/ε²) queries, accepts monotone functions with probability 1 and rejects functions that are ε-far from monotone with probability at least 2/3. 2) For all m ∈ ℕ, we show an Õ(√nm³/ε²) query monotonicity tester over [m]ⁿ. We also establish corresponding directed isoperimetric inequalities in these domains, analogous to the isoperimetric inequality in [Subhash Khot et al., 2018]. Previously, the best known tester due to Black, Chakrabarty and Seshadhri [Hadley Black et al., 2018] had Ω(n^{5/6}) query complexity. Our results are optimal up to poly-logarithmic factors and the dependency on m. Our proof uses a notion of monotone embeddings of measures into the Boolean hypercube that can be used to reduce the problem of monotonicity testing over an arbitrary product domains to the Boolean cube. The embedding maps a function over a product domain of dimension n into a function over a Boolean cube of a larger dimension n', while preserving its distance from being monotone; an embedding is considered efficient if n' is not much larger than n, and we show how to construct efficient embeddings in the above mentioned settings. 

   more » « less
5. Multivariate Monotone Inclusions in Saddle Form

   https://doi.org/10.1287/moor.2021.1161  

   Bùi, Minh N.; Combettes, Patrick L. (May 2022, Mathematics of Operations Research)

   We propose a novel approach to monotone operator splitting based on the notion of a saddle operator. Under investigation is a highly structured multivariate monotone inclusion problem involving a mix of set-valued, cocoercive, and Lipschitzian monotone operators, as well as various monotonicity-preserving operations among them. This model encompasses most formulations found in the literature. A limitation of existing primal-dual algorithms is that they operate in a product space that is too small to achieve full splitting of our problem in the sense that each operator is used individually. To circumvent this difficulty, we recast the problem as that of finding a zero of a saddle operator that acts on a bigger space. This leads to an algorithm of unprecedented flexibility, which achieves full splitting, exploits the specific attributes of each operator, is asynchronous, and requires to activate only blocks of operators at each iteration, as opposed to activating all of them. The latter feature is of critical importance in large-scale problems. The weak convergence of the main algorithm is established, as well as the strong convergence of a variant. Various applications are discussed, and instantiations of the proposed framework in the context of variational inequalities and minimization problems are presented. 

   more » « less