IEEE Transactions on Information Theory
Journal Prestige (SJR): 1.162 Citation Impact (citeScore): 3 Number of Followers: 28 Hybrid journal (It can contain Open Access articles) ISSN (Print) 00189448 Published by IEEE [228 journals] 
 IEEE Transactions on Information Theory publication information

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Presents a listing of the editorial board, board of governors, current staff, committee members, and/or society editors for this issue of the publication.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 IEEE Transactions on Information Theory information for authors

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Quadratically Constrained Myopic Adversarial Channels

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yihan Zhang;Shashank Vatedka;Sidharth Jaggi;Anand D. Sarwate;
Pages: 4901  4948
Abstract: We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noisetosignal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most $2log (n)$ bits in one subregime, and at most $Omega ({n})$ bits in the other subregime) available to the encoderdecoder pair. Our proof techniques involve a novel myopic listdecoding result for achievability, and a Plotkintype push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Entropic Compressibility of Lévy Processes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Julien Fageot;Alireza Fallah;Thibaut Horel;
Pages: 4949  4963
Abstract: In contrast to their seemingly simple and shared structure of independence and stationarity, Lévy processes exhibit a wide variety of behaviors, from the selfsimilar Wiener process to piecewiseconstant compound Poisson processes. Inspired by the recent paper of Ghourchian, Amini, and Gohari, we characterize their compressibility by studying the entropy of their double discretization (both in time and amplitude) in the regime of vanishing discretization steps. For a Lévy process with absolutely continuous marginals, this reduces to understanding the asymptotics of the differential entropy of its marginals at small times, for which we obtain a new local central limit theorem. We generalize known results for stable processes to the nonstable case, with a special focus on Lévy processes that are locally selfsimilar, and conceptualize a new compressibility hierarchy of Lévy processes, captured by their Blumenthal–Getoor index.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Resolution Limits of NonAdaptive 20 Questions Search for Multiple Targets

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Lin Zhou;Lin Bai;Alfred O. Hero;
Pages: 4964  4982
Abstract: We study the problem of simultaneous search for multiple targets over a multidimensional unit cube and derive fundamental resolution limits of nonadaptive querying procedures using the 20 questions estimation framework. The performance criterion that we consider is the achievable resolution, which is defined as the maximal $L_infty $ norm between the location vector and its estimated version where the maximization is over all target location vectors. The fundamental resolution limit is defined as the minimal achievable resolution of any nonadaptive query procedure, where each query has binary yes/no answers. We drive nonasymptotic and secondorder asymptotic bounds on the minimal achievable resolution, using tools from finite blocklength information theory. Specifically, in the achievability part, we relate the 20 questions problem to data transmission over a multiple access channel, use the information spectrum method by Han and borrow results from finite blocklength analysis for random access channel coding. In the converse part, we relate the 20 questions problem to data transmission over a pointtopoint channel and adapt finite blocklength converse results for channel coding. Our results extend the purely firstorder asymptotic analyses of Kaspi et al. (ISIT 2015) for the onedimensional case: we consider channels beyond the binary symmetric channel and derive nonasymptotic and secondorder asymptotic bounds on the performance of optimal nonadaptive query procedures.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Improved Bounds for (b, k)Hashing

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Stefano Della Fiore;Simone Costa;Marco Dalai;
Pages: 4983  4997
Abstract: For fixed integers $n$ and $bgeq k$ , let $A(b,k,n)$ the largest size of a subset of ${1,2,ldots,b}^{n}$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. Bounding $A(b,k,n)$ is a problem of relevant interest in information theory and computer science, relating to the zeroerror capacity with list decoding and to the study of $(b, k)$ hash families of functions. It is known that, for fixed $b$ and $k$ , $A(b,k,n)$ grows exponentially in $n$ . In this paper, we determine new exponential upper bounds for different values of $b$ and $k$ . A first bound on $A(b,k,n)$ for general $b$ and $k$ was derived by Fredman and Komlós in the ’80s and improved for certain $bneq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for general $b$ and $k$ by Guruswami and Riazanov, while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan, and by Costa and Dalai. In this paper, we strengthen the bounds for some specific values of $b$ and $k$ . Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinitedimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Asymptotics of Sequential Composite Hypothesis Testing Under Probabilistic
Constraints
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Jiachun Pan;Yonglong Li;Vincent Y. F. Tan;
Pages: 4998  5012
Abstract: We consider the sequential composite binary hypothesis testing problem in which one of the hypotheses is governed by a single distribution while the other is governed by a family of distributions whose parameters belong to a known set $Gamma $ . We would like to design a test to decide which hypothesis is in effect. Under the constraints that the probabilities that the length of the test, a stopping time, exceeds $n$ are bounded by a certain threshold $epsilon $ , we obtain certain fundamental limits on the asymptotic behavior of the sequential test as $n$ tends to infinity. Assuming that $Gamma $ is a convex and compact set, we obtain the set of all firstorder error exponents for the problem. We also prove a strong converse. Additionally, we obtain the set of secondorder error exponents under the assumption that the alphabet of the observations $mathcal {X}$ is finite. In the proof of secondorder asymptotics, a main technical contribution is the derivation of a central limittype result for a maximum of an uncountable set of loglikelihood ratios under suitable conditions. This result may be of independent interest. We also show that some important statistical models satisfy the conditions.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 A Strengthened Cutset Upper Bound on the Capacity of the Relay Channel and
Applications
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Abbas El Gamal;Amin Gohari;Chandra Nair;
Pages: 5013  5043
Abstract: We develop a new upper bound on the capacity of the relay channel that is tighter than previously known upper bounds. This upper bound is proved using traditional weak converse techniques involving mutual information inequalities and Gallagertype explicit identification of auxiliary random variables. We show that the new upper bound is strictly tighter than all previous bounds for the Gaussian relay channel with nonzero channel gains. When specialized to the relay channel with orthogonal receiver components, the bound resolves a conjecture by Kim on a class of deterministic relay channels. When further specialized to the class of productform relay channels with orthogonal receiver components, the bound resolves a generalized version of Cover’s relay channel problem, recovers the recent upper bound for the Gaussian case by Wu et al., and improves upon the recent bounds for the binary symmetric case by Wu et al. and Barnes et al., which were obtained using nontraditional geometric proof techniques. For the special class of a relay channel with orthogonal receiver components, we develop another upper bound on the capacity which utilizes an auxiliary receiver and show that it is strictly tighter than the bound by Tandon and Ulukus. Finally, we show through the Gaussian relay channel with i.i.d. relay output sequence that the bound with the auxiliary receiver can be strictly tighter than our main bound.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 The Feedback Capacity of Noisy Output Is the STate (NOST) Channels

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Eli Shemuel;Oron Sabag;Haim H. Permuter;
Pages: 5044  5059
Abstract: We consider finitestate channels (FSCs) where the channel state is stochastically dependent on the previous channel output. We refer to these as Noisy Output is the STate (NOST) channels. We derive the feedback capacity of NOST channels in two scenarios: with and without causal state information (CSI) available at the encoder. If CSI is unavailable, the feedback capacity is $C_{text {FB}}= max _{P(x y')} I(X;Y Y')$ , while if it is available at the encoder, the feedback capacity is $C_{text {FBCSI}}= max _{P(u y'),x(u,s')} I(U;Y Y')$ , where $U$ is an auxiliary RV with finite cardinality. In both formulas, the output process is a Markov process with stationary distribution. The derived formulas generalize special known instances from the literature, such as where the state is i.i.d. and where it is a deterministic function of the output. $C_{text {FB}}$ and $C_{text {FBCSI}}$ are also shown to be computable via convex optimization problem formulations. Finally, we present an example of an interesting NOST channel for which CSI available at the encoder does not increase the feedback capacity.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Optimal Locally Repairable Codes: An Improved Bound and Constructions

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Han Cai;Cuiling Fan;Ying Miao;Moshe Schwartz;Xiaohu Tang;
Pages: 5060  5074
Abstract: We study the Singletontype bound that provides an upper limit on the minimum distance of locally repairable codes. We present an improved bound by carefully analyzing the combinatorial structure of the repair sets. Thus, we show the previous bound is unachievable for certain parameters. We then also provide explicit constructions of optimal codes which show that for certain parameters the new bound is sharp. Additionally, as a byproduct, some previously known codes are shown to attain the new bound and are thus proved to be optimal.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Generic Decoding in the SumRank Metric

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Sven Puchinger;Julian Renner;Johan Rosenkilde;
Pages: 5075  5097
Abstract: We propose the first nontrivial generic decoding algorithm for codes in the sumrank metric. The new method combines ideas of wellknown generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rankmetric decoders. Furthermore, we give a formal hardness reduction, providing evidence that generic sumrank decoding is computationally hard. As a byproduct of the above, we solve some fundamental coding problems in the sumrank metric: we give an algorithm to compute the exact size of a sphere of a given sumrank radius, and also give an upper bound as a closed formula; and we study erasure decoding with respect to two different notions of support.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 MultipleLayer Integrated Interleaved Codes: A Class of Hierarchical
Locally Recoverable Codes
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Mario Blaum;
Pages: 5098  5111
Abstract: The traditional definition of Integrated Interleaved (II) codes generally assumes that the component nested codes are either ReedSolomon (RS) or shortened ReedSolomon codes. By taking general classes of codes, we present a recursive construction of Extended Integrated Interleaved (EII) codes into multiple layers, a problem that brought attention in literature for II codes. The multiple layer approach allows for a hierarchical scheme where each layer of the code provides for a different locality. In particular, we present the erasurecorrecting capability of the new codes and we show that they are ideally suited as Locally Recoverable codes (LRC) due to their hierarchical locality and the small finite field required by the construction. Properties of the multiple layer EII codes, like their minimum distance and dimension, as well as their erasure decoding algorithms, paritycheck matrices and performance analysis, are provided and illustrated with examples. Finally, we will observe that the paritycheck matrices of high layer EII codes have low density.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Sparse and Balanced MDS Codes Over Small Fields

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Tingting Chen;Xiande Zhang;
Pages: 5112  5125
Abstract: Maximum Distance Separable (MDS) codes with a sparse and balanced generator matrix are appealing in distributed storage systems for balancing and minimizing the computational load. Such codes have been constructed via ReedSolomon codes over large fields. In this paper, we focus on small fields. We prove that there exists an $[n,k]_{q}$ MDS code that has a sparse and balanced generator matrix for any $qgeq n1$ provided that $nleq 2k$ , by designing several algorithms with complexity running in polynomial time in $k$ and $n$ . For the case $n>2k$ , we give some constructions for $q=n=p^{s}$ and $k=p^{e}m$ based on sumsets, when $eleq s2$ and $mleq p1$ , or $e=s1$ and $m < frac {p}{2}$ .
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 CoordinateOrderingFree Upper Bounds for Linear InsertionDeletion Codes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Hao Chen;
Pages: 5126  5132
Abstract: In this paper we prove several coordinateorderingfree upper bounds on the insdel distances of linear codes. Our bounds are stronger than some previous known bounds. We apply these upper bounds to AGFC codes from some cyclic codes and one algebraicgeometric code with any rearrangement of coordinate positions. A strong upper bound on the insdel distances of ReedMuller codes with the special coordinate ordering is also given.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 A Galois Connection Approach to WeiType Duality Theorems

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yang Xu;Haibin Kan;Guangyue Han;
Pages: 5133  5144
Abstract: In 1991, Wei proved a duality theorem that established an interesting connection between the generalized Hamming weights of a linear code and those of its dual code. Wei’s duality theorem has since been extensively studied from different perspectives and extended to other settings. In this paper, we reexamine Wei’s duality theorem and its various extensions, henceforth referred to as Weitype duality theorems, from a new Galois connection perspective. Our approach is based on the observation that the generalized Hamming weights and the dimension/length profiles of a linear code form a Galois connection. The central result of this paper is a general Weitype duality theorem for two Galois connections between finite subsets of $mathbb {Z}$ , from which all the known Weitype duality theorems can be recovered. As corollaries of our central result, we prove new Weitype duality theorems for $w$ demimatroids defined over finite sets and $w$ demipolymatroids defined over modules with a composition series, which further allows us to unify and generalize all the known Weitype duality theorems established for codes endowed with various metrics.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Enumeration of Extended Irreducible Binary Goppa Codes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Bocong Chen;Guanghui Zhang;
Pages: 5145  5153
Abstract: The family of Goppa codes is one of the most interesting subclasses of linear codes. As the McEliece cryptosystem often chooses a random Goppa code as its key, knowledge of the number of inequivalent Goppa codes for fixed parameters may facilitate in the evaluation of the security of such a cryptosystem. In this paper we present a new approach to give an upper bound on the number of inequivalent extended irreducible binary Goppa codes. To be more specific, let $n>3$ be an odd prime number and $q=2^{n}$ ; let $rgeq 3$ be a positive integer satisfying $gcd (r,n)=1$ and $gcd big (r,q(q^{2}1)big)=1$ . We obtain an upper bound for the number of inequivalent extended irreducible binary Goppa codes of length $q+1$ and degree $r$ .
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

Q Ary NonOverlapping Codes: A Generating Function
Approach
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Geyang Wang;Qi Wang;
Pages: 5154  5164
Abstract: Nonoverlapping codes are a set of codewords in $bigcup _{n ge 2} mathbb {Z}_{q}^{n}$ , where $mathbb {Z}_{q} = {0,1, {dots },q1}$ , such that the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variablelength codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$ ary ones for $q> 2$ , and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large nonexpandable fixedlength nonoverlapping codes whose size can be explicitly determined; the generalization on the latter construction is the first attempt to generate $q$ ary variablelength nonoverlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$ ary nonoverlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the superior limit of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixedlength words that do not contain the codewords in a variablelength nonoverlapping code as subwors. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variablelength nonoverlapping codes.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Nonlinear Repair of ReedSolomon Codes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Roni Con;Itzhak Tamo;
Pages: 5165  5177
Abstract: The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cutset bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised by Guruswami and Wootters, 2017, on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cutset bound). This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Lastly, we show that the cutset bound for RS codes is not tight over prime fields by proving a tighter bound, using additive combinatorics ideas.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Convolutional Codes With a Maximum Distance Profile Based on Skew
Polynomials
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zitan Chen;
Pages: 5178  5184
Abstract: We construct a family of $(n,k)$ convolutional codes with degree $delta in {k,nk}$ that have a maximum distance profile. The field size required for our construction is $Theta (n^{2delta })$ , which improves upon the known constructions of convolutional codes with a maximum distance profile. Our construction is based on the theory of skew polynomials.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Precoding and Scheduling for AoI Minimization in MIMO Broadcast Channels

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Songtao Feng;Jing Yang;
Pages: 5185  5202
Abstract: In this paper, we consider a status updating system where updates are generated at a constant rate at $K$ sources and sent to the corresponding recipients through a noisefree broadcast channel. We assume that perfect channel state information (CSI) is available at the transmitter before each transmission, and the transmitter is able to utilize the CSI to precode the updates. Our object is to design optimal precoding schemes to minimize the summed average age of information (AoI) at the recipients. Under various assumptions on the size of each update $B$ , the number of transmit antennas $M$ , and the number of receive antennas $N$ at each user, this paper identifies the corresponding ageoptimal precoding and transmission scheduling strategies. Specifically, for the case when $N=1$ , a roundrobin based updating scheme is shown to be optimal. For the twouser systems with $N>B$ or $Mnotin [N:2N]$ , framed updating schemes are proven to be optimal. For other cases in the twouser systems, a framed alternating updating scheme is proven to be 2optimal.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 A Framework for Characterizing the Value of Information in Hidden Markov
Models
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zijing Wang;MihaiAlin Badiu;Justin P. Coon;
Pages: 5203  5216
Abstract: In this paper, a general framework is formalised to characterise the value of information (VoI) in hidden Markov models. Specifically, the VoI is defined as the mutual information between the current, unobserved status at the source and a sequence of observed measurements at the receiver, which can be interpreted as the reduction in the uncertainty of the current status given that we have noisy past observations of a hidden Markov process. We explore the VoI in the context of the noisy OrnsteinUhlenbeck process and derive its closedform expressions. Moreover, we investigate the effect of different sampling policies on VoI, deriving simplified expressions in different noise regimes and analysing statistical properties of the VoI in the worst case. We also study the optimal sampling policy to maximise the average information value under the sampling rate constraint. In simulations, the validity of theoretical results is verified, and the performance of VoI in Markov and hidden Markov models is also analysed. Numerical results further illustrate that the proposed VoI framework can support timely transmission in status update systems, and it can also capture the correlation properties of the underlying random process and the noise in the transmission environment.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Quantum Differentially Private Sparse Regression Learning

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yuxuan Du;MinHsiu Hsieh;Tongliang Liu;Shan You;Dacheng Tao;
Pages: 5217  5233
Abstract: The eligibility of various advanced quantum algorithms will be questioned if they can not guarantee privacy. To fill this knowledge gap, here we devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Concretely, given $N~d$ dimensional data points with $Nll d$ , we first prove that the optimal classical and quantum nonprivate Lasso requires $Omega (N+d)$ and $Omega (sqrt {N}+sqrt {d})$ runtime, respectively. We next prove that the runtime cost of QDP Lasso is dimension independent, i.e., $O(N^{5/2})$ , which implies that the QDP Lasso can be faster than both the optimal classical and quantum nonprivate Lasso. Last, we exhibit that the QDP Lasso attains a nearoptimal utility bound $tilde {O}(N^{2/3})$ with privacy guarantees and discuss the chance to realize it on nearterm quantum chips with advantages.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Linear Programming Bounds for Approximate Quantum Error Correction Over
Arbitrary Quantum Channels
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yingkai Ouyang;ChingYi Lai;
Pages: 5234  5247
Abstract: While quantum weight enumerators establish some of the best upper bounds on the minimum distance of quantum errorcorrecting codes, these bounds are not optimized to quantify the performance of quantum codes under the effect of arbitrary quantum channels that describe bespoke noise models. Herein, for any Kraus decomposition of any given quantum channel, we introduce corresponding quantum weight enumerators that naturally generalize the ShorLaflamme quantum weight enumerators. We establish an indirect linear relationship between these generalized quantum weight enumerators by introducing an auxiliary exact weight enumerator that completely quantifies the quantum code’s projector, and is independent of the underlying noise process. By additionally working within the framework of approximate quantum error correction, we establish a general framework for constructing a linear program that is infeasible whenever approximate quantum error correcting codes with corresponding parameters do not exist. Our linear programming framework allows us to establish the nonexistence of certain quantum codes that approximately correct amplitude damping errors, and obtain nontrivial upper bounds on the maximum dimension of a broad family of permutationinvariant quantum codes.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Statistically Robust, RiskAverse Best Arm Identification in MultiArmed
Bandits
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Anmol Kagrecha;Jayakrishnan Nair;Krishna Jagannathan;
Pages: 5248  5267
Abstract: Traditional multiarmed bandit (MAB) formulations usually make certain assumptions about the underlying arms’ distributions, such as bounds on the support or their tail behaviour. Moreover, such parametric information is usually ‘baked’ into the algorithms. In this paper, we show that specialized algorithms that exploit such parametric information are prone to inconsistent learning performance when the parameter is misspecified. Our key contributions are twofold: (i) We establish fundamental performance limits of statistically robust MAB algorithms under the fixedbudget pure exploration setting, and (ii) We propose two classes of algorithms that are asymptotically nearoptimal. Additionally, we consider a riskaware criterion for best arm identification, where the objective associated with each arm is a linear combination of the mean and the conditional value at risk (CVaR). Throughout, we make a very mild ‘bounded moment’ assumption, which lets us work with both lighttailed and heavytailed distributions within a unified framework.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 The Price of Competition: Effect Size Heterogeneity Matters in High
Dimensions
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Hua Wang;Yachong Yang;Weijie J. Su;
Pages: 5268  5294
Abstract: In highdimensional sparse regression, would increasing the signaltonoise ratio while fixing the sparsity level always lead to better model selection' For highdimensional sparse regression problems, surprisingly, in this paper we answer this question in the negative in the regime of linear sparsity for the Lasso method, relying on a new concept we term effect size heterogeneity. Roughly speaking, a regression coefficient vector has high effect size heterogeneity if its nonzero entries have significantly different magnitudes. From the viewpoint of this new measure, we prove that the false and true positive rates achieve the optimal tradeoff uniformly along the Lasso path when this measure is maximal in a certain sense, and the worst tradeoff is achieved when it is minimal in the sense that all nonzero effect sizes are roughly equal. Moreover, we demonstrate that the first false selection occurs much earlier when effect size heterogeneity is minimal than when it is maximal. The underlying cause of these two phenomena is, metaphorically speaking, the “competition” among variables with effect sizes of the same magnitude in entering the model. Taken together, our findings suggest that effect size heterogeneity shall serve as an important complementary measure to the sparsity of regression coefficients in the analysis of highdimensional regression problems. Our proofs use techniques from approximate message passing theory as well as a novel technique for estimating the rank of the first false variable.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 On Loss Functions and Regret Bounds for MultiCategory Classification

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zhiqiang Tan;Xinwei Zhang;
Pages: 5295  5313
Abstract: We develop new approaches in multiclass settings for constructing loss functions and establishing corresponding regret bounds with respect to the zeroone or costweighted classification loss. We provide new general representations of losses by deriving inverse mappings from a concave generalized entropy to a loss through a convex dissimilarity function related to the multidistribution $f$ divergence. This approach is then applied to study both hingelike losses and proper scoring rules. In the first case, we derive new hingelike convex losses, which are tighter extensions outside the probability simplex than related hingelike losses and geometrically simpler with fewer nondifferentiable edges. We also establish a classification regret bound in general for all losses with the same generalized entropy as the zeroone loss, thereby substantially extending and improving existing results. In the second case, we identify new sets of multiclass proper scoring rules through different types of dissimilarity functions and reveal interesting relationships between various composite losses currently in use. We also establish new classification regret bounds in general for multiclass proper scoring rules and, as applications, provide simple meaningful regret bounds for two specific sets of proper scoring rules. These results generalize, for the first time, previous twoclass regret bounds to multiclass settings.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Minimax OffPolicy Evaluation for MultiArmed Bandits

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Cong Ma;Banghua Zhu;Jiantao Jiao;Martin J. Wainwright;
Pages: 5314  5339
Abstract: We study the problem of offpolicy evaluation in the multiarmed bandit model with bounded rewards, and develop minimax rateoptimal procedures under three settings. First, when the behavior policy is known, we show that the Switch estimator, a method that alternates between the plugin and importance sampling estimators, is minimax rateoptimal for all sample sizes. Second, when the behavior policy is unknown, we analyze performance in terms of the competitive ratio, thereby revealing a fundamental gap between the settings of known and unknown behavior policies. When the behavior policy is unknown, any estimator must have meansquared error larger—relative to the oracle estimator equipped with the knowledge of the behavior policy— by a multiplicative factor proportional to the support size of the target policy. Moreover, we demonstrate that the plugin approach achieves this worstcase competitive ratio up to a logarithmic factor. Third, we initiate the study of the partial knowledge setting in which it is assumed that the minimum probability taken by the behavior policy is known. We show that the plugin estimator is optimal for relatively large values of the minimum probability, but is suboptimal when the minimum probability is low. In order to remedy this gap, we propose a new estimator based on approximation by Chebyshev polynomials that provably achieves the optimal estimation error. Numerical experiments on both simulated and real data corroborate our theoretical findings.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Convex Formulation of Overparameterized Deep Neural Networks

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Cong Fang;Yihong Gu;Weizhong Zhang;Tong Zhang;
Pages: 5340  5352
Abstract: The analysis of overparameterized neural networks has drawn significant attention in recent years. It was shown that such systems behave like convex systems under various restricted settings, such as for twolayer neural networks, and when learning is only restricted locally in the socalled neural tangent kernel space around specialized initializations. However, there is a lack of powerful theoretical techniques that can analyze fully trained deep neural networks under general conditions. This paper considers this fundamental problem by investigating such overparameterized deep neural networks when fully trained. Specifically, we characterize a deep neural network by its features’ distributions and propose a metric to intuitively measure the usefulness of feature representations. Under certain regularizers that bounds the metric, we show deep neural networks can be reformulated as a convex optimization and the system can guarantee effective feature representations in terms of the metric. Our new analysis is more consistent with empirical observations that deep neural networks are capable of learning efficient feature representations. Empirical studies confirm that predictions of our theory are consistent with results observed in practice.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Tsallis and Rényi Deformations Linked via a New λDuality

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: TingKam Leonard Wong;Jun Zhang;
Pages: 5353  5373
Abstract: Tsallis and Rényi entropies, which are monotone transformations of each other, are deformations of the celebrated Shannon entropy. Maximization of these deformed entropies, under suitable constraints, leads to the $q$ exponential family which has applications in nonextensive statistical physics, information theory and statistics. In previous informationgeometric studies, the $q$ exponential family was analyzed using classical convex duality and Bregman divergence. In this paper, we show that a generalized $lambda $ duality, where $lambda = 1  q$ is to be interpreted as the constant informationgeometric curvature, leads to a generalized exponential family which is essentially equivalent to the $q$ exponential family and has deep connections with Rényi entropy and optimal transport. Using this generalized convex duality and its associated logarithmic divergence, we show that our $lambda $ exponential family satisfies properties that parallel and generalize those of the exponential family. Under our framework, the Rényi entropy and divergence arise naturally, and we give a new proof of the Tsallis/Rényi entropy maximizing property of the $q$ exponential family. We also introduce a $lambda $ mixture family which may be regarded as the dual of the $lambda $ exponential family, and connect it with other mixturetype families. Finally, we discuss a duality between the $lambda $ exponential family and the $lambda $ logarithmic divergence, and study its statistical consequences.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 SDP Achieves Exact Minimax Optimality in Phase Synchronization

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Chao Gao;Anderson Y. Zhang;
Pages: 5374  5390
Abstract: We study the phase synchronization problem with noisy measurements $Y=z^{*}z^{* { mathrm {scriptscriptstyle H} }}+sigma Win mathbb {C}^{ntimes n}$ , where $z^{*}$ is an $n$ dimensional complex unitmodulus vector and $W$ is a complexvalued Gaussian random matrix. It is assumed that each entry $Y_{jk}$ is observed with probability $p$ . We prove that an SDP relaxation of the MLE achieves the error bound $(1+o(1))frac {sigma ^{2}}{2np}$ under a normalized squared $ell _{2}$ loss. This result matches the minimax lower bound of the problem, and even the leading constant is sharp. The analysis of the SDP is based on an equivalent nonconvex programming whose solution can be characterized as a fixed point of the generalized power iteration lifted to a higher dimensional space. This viewpoint unifies the proofs of the statistical optimality of three different methods: MLE, SDP, and generalized power method. The technique is also applied to the analysis of the SDP for $mathbb {Z}_{2}$ synchronization, and we achieve the minimax optimal error $exp left ({(1o(1))frac {np}{2sigma ^{2}}}right)$ with a sharp constant in the exponent.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Settling the Sharp Reconstruction Thresholds of Random Graph Matching

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yihong Wu;Jiaming Xu;Sophie H. Yu;
Pages: 5391  5417
Abstract: This paper studies the problem of recovering the hidden vertex correspondence between two edgecorrelated random graphs. We focus on the Gaussian model where the two graphs are complete graphs with correlated Gaussian weights and the ErdősRényi model where the two graphs are subsampled from a common parent ErdősRényi graph ${mathcal {G}}(n,p)$ . For dense ErdősRényi graphs with $p=n^{o(1)}$ , we prove that there exists a sharp threshold, above which one can correctly match all but a vanishing fraction of vertices and below which correctly matching any positive fraction is impossible, a phenomenon known as the “allornothing” phase transition. Even more strikingly, in the Gaussian setting, above the threshold all vertices can be exactly matched with high probability. In contrast, for sparse ErdősRényi graphs with $p=n^{Theta (1)}$ , we show that the allornothing phenomenon no longer holds and we determine the thresholds up to a constant factor. Along the way, we also derive the sharp threshold for exact recovery, sharpening the existing results in ErdősRényi graphs. The proof of the negative results builds upon a tight characterization of the mutual information based on the truncated secondmoment computation and an “area theorem” that relates the mutual information to the integral of the reconstruction error. The positive results follows from a tight analysis of the maximum likelihood estimator that takes into account the cycle structure of the induced permutation on the edges.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 XSecure TPrivate Federated Submodel Learning With Elastic Dropout
Resilience
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zhuqing Jia;Syed Ali Jafar;
Pages: 5418  5439
Abstract: Motivated by recent interest in federated submodel learning, this work explores the fundamental problem of privately reading from and writing to a database comprised of $K$ files (submodels) that are stored across $N$ distributed servers according to an $X$ secure threshold secret sharing scheme. One after another, various users wish to retrieve their desired file, locally process the information and then update the file in the distributed database while keeping the identity of their desired file private from any set of up to $T$ colluding servers. The availability of servers changes over time, so elastic dropout resilience is required. The main contribution of this work is an adaptive scheme, called ACSARW, that takes advantage of all currently available servers to reduce its communication costs, fully updates the database after each write operation even though the database is only partially accessible due to server dropouts, and ensures a memoryless operation of the network in the sense that the storage structure is preserved and future users may remain oblivious of the past history of server dropouts. The ACSARW construction builds upon crosssubspace alignment (CSA) codes that were originally introduced for $X$ secure $T$ private information retrieval and have been shown to be natural solutions for secure distributed batch matrix multiplication problems. ACSARW achieves the desired private read and write functionality with elastic dropout resilience, matches the best results for privateread from PIR literature, improves signifiantly upon available baselines for privatewrite, reveals a striking symmetry between upload and download costs, and exploits storage redundancy to accommodate arbitrary read and write dropout servers up to certain threshold values. It also answers in the affirmative an open question by Kairouz et al. for the case of partially colluding servers (i.e., tolerating collusion up to a threshold) by exploiting synergistic gains from the joint design of private read and write operations.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Keyless Covert Communication via Channel State Information

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Hassan Zivarifard;Matthieu R. Bloch;Aria Nosratinia;
Pages: 5440  5474
Abstract: We consider the problem of covert communication over a statedependent channel when the Channel State Information (CSI) is available either noncausally, causally, or strictly causally, either at the transmitter alone, or at both transmitter and receiver. Covert communication with respect to an adversary, called “warden,” is one in which, despite communication over the channel, the warden’s observation remains indistinguishable from an output induced by innocent channelinput symbols. Covert communication involves fooling an adversary in part by a proliferation of codebooks; for reliable decoding at the legitimate receiver, the codebook uncertainty is typically removed via a shared secret key that is unavailable to the warden. In contrast to previous work, we do not assume the availability of a large shared key at the transmitter and legitimate receiver. Instead, we only require a secret key with negligible rate to bootstrap the communication and our scheme extracts shared randomness from the CSI in a manner that keeps it secret from the warden, despite the influence of the CSI on the warden’s output. When CSI is available at the transmitter and receiver, we derive the covert capacity region. When CSI is only available at the transmitter, we derive inner and outer bounds on the covert capacity. We also provide examples for which the covert capacity is positive with knowledge of CSI but is zero without it.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Privacy Amplification With Tamperable Memory via NonMalleable TwoSource
Extractors
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Divesh Aggarwal;Maciej Obremski;João Ribeiro;Mark Simkin;Luisa Siniscalchi;
Pages: 5475  5495
Abstract: We extend the classical problem of privacy amplification to a setting where the active adversary, Eve, is also allowed to fully corrupt the internal memory (which includes the shared randomness, and local randomness tape) of one of the honest parties, Alice and Bob, before the execution of the protocol. We require that either one of Alice or Bob detects tampering, or they agree on a shared key that is indistinguishable from the uniform distribution to Eve. We obtain the following results: 1) we give a privacy amplification protocol via lowerror nonmalleable twosource extractors with one source having low minentropy. In particular, this implies the existence of such (nonefficient) protocols; 2) we show that even slight improvements to the stateoftheart explicit nonmalleable twosource extractors would lead to explicit lowerror, low minentropy twosource extractors, thereby resolving a longstanding open question. This suggests that obtaining (informationtheoretically secure) explicit nonmalleable twosource extractors for (1) might be hard; 3) we present explicit constructions of lowerror, low minentropy nonmalleable twosource extractors in the CRS model of (Garg, Kalai, Khurana, Eurocrypt 2020), assuming either the quasipolynomial hardness of DDH or the existence of nearlyoptimal collisionresistant hash functions; 4) we instantiate our privacy amplification protocol with the above mentioned nonmalleable twosource extractors in the CRS model, leading to explicit, computationallysecure protocols. This is not immediate from (1) because in the computational setting we need to make sure that, in particular, all randomness sources remain samplable throughout the proof. This requires upgrading the assumption of quasipolynomial hardness of DDH to subexponential hardness of DDH.We emphasize that each of the first three results can be read independently.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 StorageComputationCommunication Tradeoff in Distributed Computing:
Fundamental Limits and Complexity
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Qifa Yan;Sheng Yang;Michèle Wigger;
Pages: 5496  5512
Abstract: Distributed computing has become one of the most important frameworks in dealing with large computation tasks. In this paper, we propose a systematic construction of coded computing schemes for MapReducetype distributed systems. The construction builds upon placement delivery arrays (PDA), originally proposed by Yan et al. for coded caching schemes. The main contributions of our work are threefold. First, we identify a class of PDAs, called CompPDAs, and show how to obtain a coded computing scheme from any CompPDA. We also characterize the normalized number of stored files (storage load), computed intermediate values (computation load), and communicated bits (communication load), of the obtained schemes in terms of the CompPDA parameters. Then, we show that the performance achieved by CompPDAs describing MaddahAli and Niesen’s coded caching schemes matches a new informationtheoretic converse, thus establishing the fundamental region of all achievable performance triples. In particular, we characterize all the CompPDAs achieving the paretooptimal storage, computation, and communication (SCC) loads of the fundamental region. Finally, we investigate the file complexity of the proposed schemes, i.e., the smallest number of files required for implementation. In particular, we describe CompPDAs that achieve paretooptimal SCC triples with significantly lower file complexity than the originally proposed CompPDAs.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Disordered Complex Networks: Energy Optimal Lattices and Persistent
Homology
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Subhroshekhar Ghosh;Naoto Miyoshi;Tomoyuki Shirai;
Pages: 5513  5534
Abstract: Disordered complex networks are of fundamental interest in statistical physics, and they have attracted recent interest as stochastic models for information transmission over wireless networks. While mathematically tractable, a network based on the regulation Poisson point process model offers challenges visavis network efficiency. Strongly correlated alternatives, such as networks based on random matrix spectra (the Ginibre network), on the other hand offer formidable challenges in terms of tractability and robustness issues. In this work, we demonstrate that network models based on random perturbations of Euclidean lattices interpolate between Poisson and rigidly structured networks, and allow us to achieve the best of both worlds: significantly improve upon the Poisson model in terms of network efficacy measured by the Signal to Interference plus Noise Ratio (abbrv. SINR) and the related concept of coverage probabilities, at the same time retaining a considerable measure of mathematical and computational simplicity and robustness to erasure and noise. We investigate the optimal choice of the base lattice in this model, connecting it to the celebrated problem optimality of Euclidean lattices with respect to the Epstein Zeta function, which is in turn related to notions of lattice energy. This leads us to the choice of the triangular lattice in 2D and face centered cubic lattice in 3D, whose Gaussian perturbations we consider. We provide theoretical analysis and empirical investigations to demonstrate that the coverage probability decreases with increasing strength of perturbation, eventually converging to that of the Poisson network. In the regime of low disorder, our studies suggest an approximate statistical behaviour of the coverage function near a base station as a lognormal distribution with parameters depending on the Epstein Zeta function of the lattice, and related approximate dependenies for a powerlaw constant that governs the network coverage probability at large thresholds. In 2D, we determine the disorder strength at which the perturbed triangular lattice (abbrv. PTL) and the Ginibre networks are the closest measured by comparing their network topologies via a comparison of their Persistence Diagrams in the total variation as well as the symmetrized nearest neighbour distances. We demonstrate that, at this very same disorder, the PTL and the Ginibre networks exhibit very similar coverage probability distributions, with the PTL performing at least as well as the Ginibre. Thus, the PTL network at this disorder strength can be taken to be an effective substitute for the Ginibre network model, while at the same time offering the advantages of greater tractability both from theoretical and empirical perspectives.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 The Differential Spectrum of the Power Mapping x
pn
−3

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Haode Yan;Yongbo Xia;Chunlei Li;Tor Helleseth;Maosheng Xiong;Jinquan Luo;
Pages: 5535  5547
Abstract: Let $n$ be a positive integer and $p$ a prime. The power mapping $x^{p^{n}3}$ over ${mathbb {F}}_{p^{n}}$ has desirable differential properties, and its differential spectra for $p=2,,3$ have been determined. In this paper, for any odd prime $p$ , by investigating certain quadratic character sums and some equations over ${mathbb {F}}_{p^{n}}$ , we determine the differential spectrum of $x^{p^{n}3}$ with a unified approach. The obtained result shows that for any given odd prime $p$ , the differential spectrum can be expressed explicitly in terms of $n$ . Compared with previous results, a special elliptic curve over ${mathbb {F}}_{p}$ plays an important role in our computation for the general case $p ge 5$ .
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Some Upper Bounds and Exact Values on Linear Complexities Over F
M of
Sidelnikov Sequences for M = 2 and 3
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Min Zeng;Yuan Luo;GuoSheng Hu;HongYeop Song;
Pages: 5548  5560
Abstract: Sidelnikov sequences, a kind of cyclotomic sequences with many desired properties such as low correlation and variable alphabet sizes, can be employed to construct a polyphase sequence family that has many applications in highspeed data communications. Recently, cyclotomic numbers have been used to investigate the linear complexity of Sidelnikov sequences, mainly about binary ones, although the limitation on the orders of the available cyclotomic numbers makes it difficult. This paper continues to study the linear complexity over $mathbb {F}_{M}$ of $M$ ary Sidelnikov sequence of period $q1$ using Hasse derivative, which implies $q=p^{m}$ , $mgeq 1$ and $M (q1)$ . The $t$ th Hasse derivative formulas are presented in terms of cyclotomic numbers, and some upper bounds on the linear complexity for $M=2$ and 3 are obtained only with some additional restrictions on $q$ . Furthermore, concrete illustrations for several families of these sequences, such as $qequiv 1pmod {2}$ and $qequiv 1pmod {3}$ , show these upper bounds are tight and reachable; especially for $q=2times 3^{lambda }+1 (1leq lambda leq 20)$ , the exact linear complexities over $mathbb {F}_{3}$ of the ternary Sidelnikov sequences are determined; and it turns out that all the linear complexities of the sequences considered are very close to their periods.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 On NonDetectability of NonComputability and the Degree of
NonComputability of Solutions of Circuit and Wave Equations on Digital
Computers
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Holger Boche;Volker Pohl;
Pages: 5561  5578
Abstract: It is known that there exist mathematical problems of practical relevance which cannot be computed on a Turing machine. An important example is the calculation of the first derivative of continuously differentiable functions. This paper precisely classifies the noncomputability of the first derivative, and of the maximumnorm of the first derivative in the ZhengWeihrauch hierarchy. Based on this classification, the paper investigates whether it is possible that a Turing machine detects this noncomputability of the first derivative by observing the data of the problem, and whether it is possible to detect upper bounds for the peak value of the first derivative of continuously differentiable functions. So from a practical point of view, the question is whether it is possible to implement an exitflag functionality for observing noncomputability of the first derivative. This paper even studies two different types of exitflag functionality. A strong one, where the Turing machine always has to stop, and a weak one, where the Turing machine stops if and only if the input lies within the corresponding set of interest. It will be shown that noncomputability of the first derivative is not detectable by a Turing machine for two concrete examples, namely for the problem of computing the input–output behavior of simple analog circuits and for solutions of the threedimensional wave equation. In addition, it is shown that it is even impossible to detect an upper bound for the maximum norm of the first derivative. In particular, it is shown that all three problems are not even semidecidable. Finally, we briefly discuss implications of these results for analog and quantum computing.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)

 Macroscopic Analysis of Vector Approximate Message Passing in a
ModelMismatched Setting
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Takashi Takahashi;Yoshiyuki Kabashima;
Pages: 5579  5600
Abstract: In this study, macroscopic properties of the vector approximate message passing (VAMP) algorithm for inference of generalized linear models are investigated using a nonrigorous heuristic method of statistical mechanics when the true posterior cannot be used and the measurement matrix is a sample from rotationinvariant random matrix ensembles. The focus is on the correspondence between the nonrigorous replica analysis of statistical mechanics and the performance assessment of VAMP in the modelmismatched setting. The correspondence of this kind is wellknown when the measurement matrix has independent and identically distributed entries. However, when the measurement matrix follows a general rotationinvariant matrix ensemble, the correspondence has been validated only under limited cases, such as the Bayes optimal inference or the convex empirical risk minimization. The result presented in this paper is to extend the scope of such correspondence. Herein, we heuristically derive the explicit formula of stateevolution equations, which macroscopically describe VAMP dynamics for the current modelmismatched case, and show that their fixed point is generally consistent with the replica symmetric solution obtained by the replica method of statistical mechanics. We also show that the fixed point of VAMP can exhibit a microscopic instability, which indicates that message variables continue to move by VAMP while their macroscopically summarized quantities converge to fixed values. The critical condition the for microscopic instability agrees with that for breaking the replica symmetry that is derived within the nonrigorous replica analysis. The results of the numerical experiments crosscheck our findings.
PubDate: Aug. 2022
Issue No: Vol. 68, No. 8 (2022)
