A graph G is called {\em selfordered} (a.k.a asymmetric) if the identity permutation is its only automorphism. Equivalently, there is a unique isomorphism from G to any graph that is isomorphic to G. We say that G=(VE) is {\em robustly selfordered}if the size of the symmetric difference between E and the edgeset of the graph obtained by permuting V using any permutation :VV is proportional to the number of nonfixedpoints of . In this work, we initiate the study of the structure, construction and utility of robustly selfordered graphs. We show that robustly selfordered boundeddegree graphs exist (in abundance), and that they can be constructed efficiently, in a strong sense. Specifically, given the index of a vertex in such a graph, it is possible to find all its neighbors in polynomialtime (i.e., in time that is polylogarithmic in the size of the graph). We provide two very different constructions, in tools and structure. The first, a direct construction, is based on proving a sufficient condition for robust selfordering, which requires that an auxiliary graph, on {\em pairs} of vertices of the original graph, is expanding. In this case the original graph is (not only robustly selfordered but) also expanding. Themore »
Tight decomposition functions for mixed monotonicity
Mixed monotonicity is a property of a system’s vector field that says that the vector field admits a decomposition function, in a lifted space, that has some order preserving properties. It is recently shown that this property allows one to efficiently overapproximate the system’s onestep reachable set with a hyperinterval, which is obtained by evaluating the vector field’s decomposition function at two points. Such decomposition functions are usually not unique and some decompositions may not be tight in the sense that the resulting hyperintervals are not the smallest ones that contain the exact onestep reachable set, which leads to conservative
overapproximation. In this paper, we show that for a general class of functions, there exists a tight decomposition, which can be implicitly constructed as the solution of certain optimization problems. This implies that any function from Rn to Rm (hence any forward complete system) is mixedmonotone. However, the
usefulness of the constructed tight decomposition functions is limited by the fact that it might not be possible to evaluate them efficiently. We show that under certain conditions, the tight decompositions can reduce to a function with explicit expression, which can be directly evaluated. This result suggests that it is not mixed monotonicity itself, more »
 Award ID(s):
 1553873
 Publication Date:
 NSFPAR ID:
 10132223
 Journal Name:
 58th IEEE Conference on Decision and Control (CDC)
 Sponsoring Org:
 National Science Foundation
More Like this


Abstract The classical serendipity and mixed finite element spaces suffer from poor approximation on nondegenerate, convex quadrilaterals. In this paper, we develop families of direct serendipity and direct mixed finite element spaces, which achieve optimal approximation properties and have minimal local dimension. The set of local shape functions for either the serendipity or mixed elements contains the full set of scalar or vector polynomials of degree r , respectively, defined directly on each element (i.e., not mapped from a reference element). Because there are not enough degrees of freedom for global $$H^1$$ H 1 or $$H(\text {div})$$ H ( div ) conformity, exactly two supplemental shape functions must be added to each element when $$r\ge 2$$ r ≥ 2 , and only one when $$r=1$$ r = 1 . The specific choice of supplemental functions gives rise to different families of direct elements. These new spaces are related through a de Rham complex. For index $$r\ge 1$$ r ≥ 1 , the new families of serendipity spaces $${\mathscr {DS}}_{r+1}$$ DS r + 1 are the precursors under the curl operator of our direct mixed finite element spaces, which can be constructed to have reduced or full $$H(\text {div})$$ H (more »

The needs of a business (e.g., hiring) may require the use of certain features that are critical in a way that any discrimination arising due to them should be exempted. In this work, we propose a novel informationtheoretic decomposition of the total discrimination (in a counterfactual sense) into a nonexempt component, which quantifies the part of the discrimination that cannot be accounted for by the critical features, and an exempt component, which quantifies the remaining discrimination. Our decomposition enables selective removal of the nonexempt component if desired. We arrive at this decomposition through examples and counterexamples that enable us to first obtain a set of desirable properties that any measure of nonexempt discrimination should satisfy. We then demonstrate that our proposed quantification of nonexempt discrimination satisfies all of them. This decomposition leverages a body of work from information theory called Partial Information Decomposition (PID). We also obtain an impossibility result showing that no observational measure of nonexempt discrimination can satisfy all of the desired properties, which leads us to relax our goals and examine alternative observational measures that satisfy only some of these properties. We then perform a case study using one observational measure to show how one might trainmore »

The noise sensitivity of a Boolean function f: {0,1}^n  > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noisesensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone functionmore »

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 ofmore »