The concatenation of four Boolean bent functions $f=f_1||f_2||f_3||f_4$ is bent if and only if the dual bent condition $f_1^* + f_2^* + f_3^* + f_4^* =1$ is satisfied. However, to specify four bent functions satisfying this duality condition is in general quite a difficult task. Commonly, to simplify this problem, certain connections between $f_i$ are assumed, as well as functions $f_i$ of a special shape are considered, e.g., $f_i(x,y)=x\cdot\pi_i(y)+h_i(y)$ are Maiorana-McFarland bent functions. In the case when permutations $\pi_i$ of $\mathbb{F}_2^m$ have the $(\mathcal{A}_m)$ property and Maiorana-McFarland bent functions $f_i$ satisfy the additional condition $f_1+f_2+f_3+f_4=0$, the dual bent condition is known to have a relatively simple shape allowing to specify the functions $f_i$ explicitly. In this paper, we generalize this result for the case when Maiorana-McFarland bent functions $f_i$ satisfy the condition $f_1(x,y)+f_2(x,y)+f_3(x,y)+f_4(x,y)=s(y)$ and provide a construction of new permutations with the $(\mathcal{A}_m)$ property from the old ones. Combining these two results, we obtain a recursive construction method of bent functions satisfying the dual bent condition. Moreover, we provide a generic condition on the Maiorana-McFarland bent functions stemming from the permutations of $\mathbb{F}_2^m$ with the $(\mathcal{A}_m)$ property, such that their concatenation does not belong, up to equivalence, to the Maiorana-McFarland class. Using monomial permutations $\pi_i$ of $\mathbb{F}_{2^m}$ with the $(\mathcal{A}_m)$ property and monomial functions $h_i$ on $\mathbb{F}_{2^m}$, we provide explicit constructions of such bent functions. Finally, with our construction method, we explain how one can construct homogeneous cubic bent functions, noticing that only very few design methods of these objects are known.
相關內容
This paper focuses on representing the $L^{\infty}$-norm of finite-dimensional linear time-invariant systems with parameter-dependent coefficients. Previous studies tackled the problem in a non-parametric scenario by simplifying it to finding the maximum $y$-projection of real solutions $(x, y)$ of a system of the form $\Sigma=\{P=0, \, \partial P/\partial x=0\}$, where $P \in \Z[x, y]$. To solve this problem, standard computer algebra methods were employed and analyzed \cite{bouzidi2021computation}. In this paper, we extend our approach to address the parametric case. We aim to represent the "maximal" $y$-projection of real solutions of $\Sigma$ as a function of the given parameters. %a set of parameters $\alpha$. To accomplish this, we utilize cylindrical algebraic decomposition. This method allows us to determine the desired value as a function of the parameters within specific regions of parameter space.
This paper focuses on representing the $L^{\infty}$-norm of finite-dimensional linear time-invariant systems with parameter-dependent coefficients. Previous studies tackled the problem in a non-parametric scenario by simplifying it to finding the maximum $y$-projection of real solutions $(x, y)$ of a system of the form $\Sigma=\{P=0, \, \partial P/\partial x=0\}$, where $P \in \Z[x, y]$. To solve this problem, standard computer algebra methods were employed and analyzed \cite{bouzidi2021computation}. In this paper, we extend our approach to address the parametric case. We aim to represent the "maximal" $y$-projection of real solutions of $\Sigma$ as a function of the given parameters. %a set of parameters $\alpha$. To accomplish this, we utilize cylindrical algebraic decomposition. This method allows us to determine the desired value as a function of the parameters within specific regions of parameter space.
A $3$-uniform hypergraph is a generalization of simple graphs where each hyperedge is a subset of vertices of size $3$. The degree of a vertex in a hypergraph is the number of hyperedges incident with it. The degree sequence of a hypergraph is the sequence of the degrees of its vertices. The degree sequence problem for $3$-uniform hypergraphs is to decide if a $3$-uniform hypergraph exists with a prescribed degree sequence. Such a hypergraph is called a realization. Recently, Deza \emph{et al.} proved that the degree sequence problem for $3$-uniform hypergraphs is NP-complete. Some special cases are easy; however, polynomial algorithms have been known so far only for some very restricted degree sequences. The main result of our research is the following. If all degrees are between $\frac{2n^2}{63}+O(n)$ and $\frac{5n^2}{63}-O(n)$ in a degree sequence $D$, further, the number of vertices is at least $45$, and the degree sum can be divided by $3$, then $D$ has a $3$-uniform hypergraph realization. Our proof is constructive and in fact, it constructs a hypergraph realization in polynomial time for any degree sequence satisfying the properties mentioned above. To our knowledge, this is the first polynomial running time algorithm to construct a $3$-uniform hypergraph realization of a highly irregular and dense degree sequence.
Given an $m\times n$ binary matrix $M$ with $|M|=p\cdot mn$ (where $|M|$ denotes the number of 1 entries), define the discrepancy of $M$ as $\mbox{disc}(M)=\displaystyle\max_{X\subset [m], Y\subset [n]}\big||M[X\times Y]|-p|X|\cdot |Y|\big|$. Using semidefinite programming and spectral techniques, we prove that if $\mbox{rank}(M)\leq r$ and $p\leq 1/2$, then $$\mbox{disc}(M)\geq \Omega(mn)\cdot \min\left\{p,\frac{p^{1/2}}{\sqrt{r}}\right\}.$$ We use this result to obtain a modest improvement of Lovett's best known upper bound on the log-rank conjecture. We prove that any $m\times n$ binary matrix $M$ of rank at most $r$ contains an $(m\cdot 2^{-O(\sqrt{r})})\times (n\cdot 2^{-O(\sqrt{r})})$ sized all-1 or all-0 submatrix, which implies that the deterministic communication complexity of any Boolean function of rank $r$ is at most $O(\sqrt{r})$.
An $(r, \delta)$-locally repairable code ($(r, \delta)$-LRC for short) was introduced by Prakash et al. for tolerating multiple failed nodes in distributed storage systems, and has garnered significant interest among researchers. An $(r,\delta)$-LRC is called an optimal code if its parameters achieve the Singleton-like bound. In this paper, we construct three classes of $q$-ary optimal cyclic $(r,\delta)$-LRCs with new parameters by investigating the defining sets of cyclic codes. Our results generalize the related work of \cite{Chen2022,Qian2020}, and the obtained optimal cyclic $(r, \delta)$-LRCs have flexible parameters. A lot of numerical examples of optimal cyclic $(r, \delta)$-LRCs are given to show that our constructions are capable of generating new optimal cyclic $(r, \delta)$-LRCs.
In this paper, we consider a problem which we call LTL$_f$ model checking on paths: given a DFA $\mathcal{A}$ and a formula $\phi$ in LTL on finite traces, does there exist a word $w$ such that every path starting in a state of $\mathcal{A}$ and labeled by $w$ satisfies $\phi$? The original motivation for this problem comes from the constrained parts orienting problem, introduced in [Petra Wolf, "Synchronization Under Dynamic Constraints", FSTTCS 2020], where the input constraints restrict the order in which certain states are visited for the first or the last time while reading a word $w$ which is also required to synchronize $\mathcal{A}$. We identify very general conditions under which LTL$_f$ model checking on paths is solvable in polynomial space. For the particular constraints in the parts orienting problem, we consider PSPACE-complete cases and one NP-complete case. The former provide very strong lower bound for LTL$_f$ model checking on paths. The latter is related to (classical) LTL$_f$ model checking for formulas with the until modality only and with no nesting of operators. We also consider LTL$_f$ model checking of the power-set automaton of a given DFA, and get similar results for this setting. For all our problems, we consider the case where the required word must also be synchronizing, and prove that if the problem does not become trivial, then this additional constraint does not change the complexity.
We investigate an operator on classes of languages. For each class $C$, it outputs a new class $FO^2(I_C)$ associated with a variant of two-variable first-order logic equipped with a signature$I_C$ built from $C$. For $C = \{\emptyset, A^*\}$, we get the variant $FO^2(<)$ equipped with the linear order. For $C = \{\emptyset, \{\varepsilon\},A^+, A^*\}$, we get the variant $FO^2(<,+1)$, which also includes the successor. If $C$ consists of all Boolean combinations of languages $A^*aA^*$ where $a$ is a letter, we get the variant $FO^2(<,Bet)$, which also includes "between relations". We prove a generic algebraic characterization of the classes $FO^2(I_C)$. It smoothly and elegantly generalizes the known ones for all aforementioned cases. Moreover, it implies that if $C$ has decidable separation (plus mild properties), then $FO^2(I_C)$ has a decidable membership problem. We actually work with an equivalent definition of \fodc in terms of unary temporal logic. For each class $C$, we consider a variant $TL(C)$ of unary temporal logic whose future/past modalities depend on $C$ and such that $TL(C) = FO^2(I_C)$. Finally, we also characterize $FL(C)$ and $PL(C)$, the pure-future and pure-past restrictions of $TL(C)$. These characterizations as well imply that if \Cs is a class with decidable separation, then $FL(C)$ and $PL(C)$ have decidable membership.
In this paper we generalize the notion of $n$-equivalence relation introduced by Chen et al. in \cite{Chen2014} to classify constacyclic codes of length $n$ over a finite field $\Fq,$ where $q=p^r$ is a prime power, to the case of skew constacyclic codes without derivation. We call this relation $(n,\sigma)$-equivalence relation, where $n$ is the length of the code and $ \sigma$ is an automorphism of the finite field. We compute the number of $(n,\sigma)$-equivalence classes, and we give conditions on $ \lambda$ and $\mu$ for which $(\sigma, \lambda)$-constacyclic codes and $(\sigma, \lambda)$-constacyclic codes are equivalent with respect to our $(n,\sigma)$-equivalence relation. Under some conditions on $n$ and $q$ we prove that skew constacyclic codes are equivalent to cyclic codes. We also prove that when $q$ is even and $\sigma$ is the Frobenius autmorphism, skew constacyclic codes of length $n$ are equivalent to cyclic codes when $\gcd(n,r)=1$. Finally we give some examples as applications of the theory developed here.
The $L_{\infty}$ star discrepancy is a very well-studied measure used to quantify the uniformity of a point set distribution. Constructing optimal point sets for this measure is seen as a very hard problem in the discrepancy community. Indeed, optimal point sets are, up to now, known only for $n\leq 6$ in dimension 2 and $n \leq 2$ for higher dimensions. We introduce in this paper mathematical programming formulations to construct point sets with as low $L_{\infty}$ star discrepancy as possible. Firstly, we present two models to construct optimal sets and show that there always exist optimal sets with the property that no two points share a coordinate. Then, we provide possible extensions of our models to other measures, such as the extreme and periodic discrepancies. For the $L_{\infty}$ star discrepancy, we are able to compute optimal point sets for up to 21 points in dimension 2 and for up to 8 points in dimension 3. For $d=2$ and $n\ge 7$ points, these point sets have around a 50% lower discrepancy than the current best point sets, and show a very different structure.
In this paper we prove that the $\ell_0$ isoperimetric coefficient for any axis-aligned cubes, $\psi_{\mathcal{C}}$, is $\Theta(n^{-1/2})$ and that the isoperimetric coefficient for any measurable body $K$, $\psi_K$, is of order $O(n^{-1/2})$. As a corollary we deduce that axis-aligned cubes essentially "maximize" the $\ell_0$ isoperimetric coefficient: There exists a positive constant $q > 0$ such that $\psi_K \leq q \cdot \psi_{\mathcal{C}}$, whenever $\mathcal{C}$ is an axis-aligned cube and $K$ is any measurable set. Lastly, we give immediate applications of our results to the mixing time of Coordinate-Hit-and-Run for sampling points uniformly from convex bodies.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191