Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximate polymorphisms
181
0
0.0
(
0
)
Added by
Yuval Filmus
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
For a function $gcolon{0,1}^mto{0,1}$, a function $fcolon {0,1}^nto{0,1}$ is called a $g$-polymorphism if their actions commute: $f(g(mathsf{row}_1(Z)),ldots,g(mathsf{row}_n(Z))) = g(f(mathsf{col}_1(Z)),ldots,f(mathsf{col}_m(Z)))$ for all $Zin{0,1}^{ntimes m}$. The function $f$ is called an approximate polymorphism if this equality holds with probability close to $1$, when $Z$ is sampled uniformly. We study the structure of exact polymorphisms as well as approximate polymorphisms. Our results include: - We prove that an approximate polymorphism $f$ must be close to an exact polymorphism; - We give a characterization of exact polymorphisms, showing that besides trivial cases, only the functions $g = mathsf{AND}, mathsf{XOR}, mathsf{OR}, mathsf{NXOR}$ admit non-trivial exact polymorphisms. We also study the approximate polymorphism problem in the list-decoding regime (i.e., when the probability equality holds is not close to $1$, but is bounded away from some value). We show that if $f(x land y) = f(x) land f(y)$ with probability larger than $s_land approx 0.815$ then $f$ correlates with some low-degree character, and $s_land$ is the optimal threshold for this property. Our result generalize the classical linearity testing result of Blum, Luby and Rubinfeld, that in this language showed that the approximate polymorphisms of $g = mathsf{XOR}$ are close to XORs, as well as a recent result of Filmus, Lifshitz, Minzer and Mossel, showing that the approximate polymorphisms of AND can only be close to AND functions.
rate research
Read More
An arbitrary $mtimes n$ Boolean matrix $M$ can be decomposed {em exactly} as $M =Ucirc V$, where $U$ (resp. $V$) is an $mtimes k$ (resp. $ktimes n$) Boolean matrix and $circ$ denotes the Boolean matrix multiplication operator. We first prove an exact formula for the Boolean matrix $J$ such that $M =Mcirc J^T$ holds, where $J$ is maximal in the sense that if any 0 element in $J$ is changed to a 1 then this equality no longer holds. Since minimizing $k$ is NP-hard, we propose two heuristic algorithms for finding suboptimal but good decomposition. We measure the performance (in minimizing $k$) of our algorithms on several real datasets in comparison with other representative heuristic algorithms for Boolean matrix decomposition (BMD). The results on some popular benchmark datasets demonstrate that one of our proposed algorithms performs as well or better on most of them. Our algorithms have a number of other advantages: They are based on exact mathematical formula, which can be interpreted intuitively. They can be used for approximation as well with competitive coverage. Last but not least, they also run very fast. Due to interpretability issues in data mining, we impose the condition, called the column use condition, that the columns of the factor matrix $U$ must form a subset of the columns of $M$.
We introduce a general method to count unlabeled combinatorial structures and to efficiently generate them at random. The approach is based on pointing unlabeled structures in an unbiased way that a structure of size n gives rise to n pointed structures. We extend Polya theory to the corresponding pointing operator, and present a random sampling framework based on both the principles of Boltzmann sampling and on Polya operators. All previously known unlabeled construction principles for Boltzmann samplers are special cases of our new results. Our method is illustrated on several examples: in each case, we provide enumerative results and efficient random samplers. The approach applies to unlabeled families of plane and nonplane unrooted trees, and tree-like structures in general, but also to families of graphs (such as cacti graphs and outerplanar graphs) and families of planar maps.
Clique-width is a complexity measure of directed as well as undirected graphs. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss an extension of the notion of rank-width to edge-colored graphs. A C-colored graph is a graph where the arcs are colored with colors from the set C. There is not a natural notion of rank-width for C-colored graphs. We define two notions of rank-width for them, both based on a coding of C-colored graphs by edge-colored graphs where each edge has exactly one color from a field F and named respectively F-rank-width and F-bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for F-colored graphs and prove that F-colored graphs of bounded F-rank-width are characterised by a finite list of F-colored graphs to exclude as vertex-minors. A cubic-time algorithm to decide whether a F-colored graph has F-rank-width (resp. F-bi-rank-width) at most k, for fixed k, is also given. Graph operations to check MSOL-definable properties on F-colored graphs of bounded rank-width are presented. A specialisation of all these notions to (directed) graphs without edge colors is presented, which shows that our results generalise the ones in undirected graphs.
We introduce a definition of admissibility for subintervals in interval exchange transformations. Using this notion, we prove a property of the natural codings of interval exchange transformations, namely that any derived set of a regular interval exchange set is a regular interval exchange set with the same number of intervals. Derivation is taken here with respect to return words. We characterize the admissible intervals using a branching version of the Rauzy induction. We also study the case of regular interval exchange transformations defined over a quadratic field and show that the set of factors of such a transformation is primitive morphic. The proof uses an extension of a result of Boshernitzan and Carroll.
We describe in this paper a connection between bifix codes, symbolic dynamical systems and free groups. This is in the spirit of the connection established previously for the symbolic systems corresponding to Sturmian words. We introduce a class of sets of factors of an infinite word with linear factor complexity containing Sturmian sets and regular interval exchange sets, namemly the class of tree sets. We prove as a main result that for a uniformly recurrent tree set $F$, a finite bifix code $X$ on the alphabet $A$ is $F$-maximal of $F$-degree $d$ if and only if it is the basis of a subgroup of index $d$ of the free group on $A$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
