Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Symmetric Invertible Binary Pairing Functions
82
0
0.0
(
0
)
Added by
Jianrui Xie
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Jianrui Xie
Ask ChatGPT about the research
No Arabic abstract
We construct a symmetric invertible binary pairing function $F(m,n)$ on the set of positive integers with a property of $F(m,n)=F(n,m)$. Then we provide a complete proof of its symmetry and bijectivity, from which the construction of symmetric invertible binary pairing functions on any custom set of integers could be seen.
rate research
Read More
A ${00,01,10,11}$-valued function on the vertices of the $n$-cube is called a $t$-resilient $(n,2)$-function if it has the same number of $00$s, $01$s, $10$s and $11$s among the vertices of every subcube of dimension $t$. The Friedman and Fon-Der-Flaass bounds on the correlation immunity order say that such a function must satisfy $tle 2n/3-1$; moreover, the $(2n/3-1)$-resilient $(n,2)$-functions correspond to the equitable partitions of the $n$-cube with the quotient matrix $[[0,r,r,r],[r,0,r,r],[r,r,0,r],[r,r,r,0]]$, $r=n/3$. We suggest constructions of such functions and corresponding partitions, show connections with Latin hypercubes and binary $1$-perfect codes, characterize the non-full-rank and the reducible functions from the considered class, and discuss the possibility to make a complete characterization of the class.
We show that a Boolean degree $d$ function on the slice $binom{[n]}{k} = { (x_1,ldots,x_n) in {0,1} : sum_{i=1}^n x_i = k }$ is a junta, assuming that $k,n-k$ are large enough. This generalizes a classical result of Nisan and Szegedy on the hypercube. Moreover, we show that the maximum number of coordinates that a Boolean degree $d$ function can depend on is the same on the slice and the hypercube.
We present results on the existence of long arithmetic progressions in the Thue-Morse word and in a class of generalised Thue-Morse words. Our arguments are inspired by van der Waerdens proof for the existence of arbitrary long monochromatic arithmetic progressions in any finite colouring of the (positive) integers.
A fringe subtree of a rooted tree is a subtree consisting of one of the nodes and all its descendants. In this paper, we are specifically interested in the number of non-isomorphic trees that appear in the collection of all fringe subtrees of a binary tree. This number is analysed under two different random models: uniformly random binary trees and random binary search trees. In the case of uniformly random binary trees, we show that the number of non-isomorphic fringe subtrees lies between $c_1n/sqrt{ln n}(1+o(1))$ and $c_2n/sqrt{ln n}(1+o(1))$ for two constants $c_1 approx 1.0591261434$ and $c_2 approx 1.0761505454$, both in expectation and with high probability, where $n$ denotes the size (number of leaves) of the uniformly random binary tree. A similar result is proven for random binary search trees, but the order of magnitude is $n/ln n$ in this case. Our proof technique can also be used to strengthen known results on the number of distinct fringe subtrees (distinct in the sense of ordered trees). This quantity is of the same order of magnitude in both cases, but with slightly different constants in the upper and lower bounds.
We show that if $fcolon S_n to {0,1}$ is $epsilon$-close to linear in $L_2$ and $mathbb{E}[f] leq 1/2$ then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and moreover this is sharp: any such union is close to linear. This constitutes a sharp Friedgut-Kalai-Naor theorem for the symmetric group. Using similar techniques, we show that if $fcolon S_n to mathbb{R}$ is linear, $Pr[f otin {0,1}] leq epsilon$, and $Pr[f = 1] leq 1/2$, then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and this is also sharp; and that if $fcolon S_n to mathbb{R}$ is linear and $epsilon$-close to ${0,1}$ in $L_infty$ then $f$ is $O(epsilon)$-close in $L_infty$ to a union of disjoint cosets.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
