BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Moshe Schwartz

Moshe Schwartz appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITcond-mat.stat-mechcond-mat.softmath.COquant-phcond-mat.dis-nncond-mat.mtrl-scinlin.CDphysics.data-anphysics.opticsComputation and Languagecond-mat.othermath-phmath.DSmath.MPmath.PRnlin.AOphysics.soc-phSocial and Information Networks

Catalog footprint

What is connected

46works
20topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

46 published item(s)

preprint2022arXiv

A Bound on the Minimal Field Size of LRCs, and Cyclic MR Codes That Attain It

We prove a new lower bound on the field size of locally repairable codes (LRCs). Additionally, we construct maximally recoverable (MR) codes which are cyclic. While a known construction for MR codes has the same parameters, it produces non-cyclic codes. Furthermore, we prove both necessary conditions and sufficient conditions that specify when the known non-cyclic MR codes may be permuted to become cyclic, thus proving our construction produces cyclic MR codes with new parameters. Furthermore, using our new bound on the field size, we show that the new cyclic MR codes have optimal field size in certain cases. Other known LRCs are also shown to have optimal field size in certain cases.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Perfect Codes Correcting a Single Burst of Limited-Magnitude Errors

Motivated by applications to DNA-storage, flash memory, and magnetic recording, we study perfect burst-correcting codes for the limited-magnitude error channel. These codes are lattices that tile the integer grid with the appropriate error ball. We construct two classes of such perfect codes correcting a single burst of length $2$ for $(1,0)$-limited-magnitude errors, both for cyclic and non-cyclic bursts. We also present a generic construction that requires a primitive element in a finite field with specific properties. We then show that in various parameter regimes such primitive elements exist, and hence, infinitely many perfect burst-correcting codes exist.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reviving a failed network through microscopic interventions

From mass extinction to cell death, complex networked systems often exhibit abrupt dynamic transitions between desirable and undesirable states. Such transitions are often caused by topological perturbations, such as node or link removal, or decreasing link strengths. The problem is that reversing the topological damage, namely retrieving the lost nodes or links, or reinforcing the weakened interactions, does not guarantee the spontaneous recovery to the desired functional state. Indeed, many of the relevant systems exhibit a hysteresis phenomenon, remaining in the dysfunctional state, despite reconstructing their damaged topology. To address this challenge, we develop a two-step recovery scheme: first - topological reconstruction to the point where the system can be revived, then dynamic interventions, to reignite the system's lost functionality. Applying this method to a range of nonlinear network dynamics, we identify the recoverable phase of a complex system, a state in which the system can be reignited by microscopic interventions, for instance, controlling just a single node. Mapping the boundaries of this dynamical phase, we obtain guidelines for our two-step recovery.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Improved Rank-Modulation Codes for DNA Storage with Shotgun Sequencing

We study permutations over the set of $\ell$-grams, that are feasible in the sense that there is a sequence whose $\ell$-gram frequency has the same ranking as the permutation. Codes, which are sets of feasible permutations, protect information stored in DNA molecules using the rank-modulation scheme, and read using the shotgun sequencing technique. We construct systematic codes with an efficient encoding algorithm, and show that they are optimal in size. The length of the DNA sequences that correspond to the codewords is shown to be polynomial in the code parameters. Non-systematic with larger size are also constructed.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On Tilings of Asymmetric Limited-Magnitude Balls

We study whether an asymmetric limited-magnitude ball may tile $\mathbb{Z}^n$. This ball generalizes previously studied shapes: crosses, semi-crosses, and quasi-crosses. Such tilings act as perfect error-correcting codes in a channel which changes a transmitted integer vector in a bounded number of entries by limited-magnitude errors. A construction of lattice tilings based on perfect codes in the Hamming metric is given. Several non-existence results are proved, both for general tilings, and lattice tilings. A complete classification of lattice tilings for two certain cases is proved.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Coding for Optimized Writing Rate in DNA Storage

A method for encoding information in DNA sequences is described. The method is based on the precision-resolution framework, and is aimed to work in conjunction with a recently suggested terminator-free template independent DNA synthesis method. The suggested method optimizes the amount of information bits per synthesis time unit, namely, the writing rate. Additionally, the encoding scheme studied here takes into account the existence of multiple copies of the DNA sequence, which are independently distorted. Finally, quantizers for various run-length distributions are designed.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Lattice Packings and Coverings of Asymmetric Limited-Magnitude Balls

We construct integer error-correcting codes and covering codes for the limited-magnitude error channel with more than one error. The codes are lattices that pack or cover the space with the appropriate error ball. Some of the constructions attain an asymptotic packing/covering density that is constant. The results are obtained via various methods, including the use of codes in the Hamming metric, modular $B_t$-sequences, $2$-fold Sidon sets, and sets avoiding arithmetic progression.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Optimal Locally Repairable Codes and Generalized Sector-Disk Codes

Optimal locally repairable codes with information locality are considered. Optimal codes are constructed, whose length is also order-optimal with respect to a new bound on the code length derived in this paper. The length of the constructed codes is super-linear in the alphabet size, which improves upon the well known pyramid codes, whose length is only linear in the alphabet size. The recoverable erasure patterns are also analyzed for the new codes. Based on the recoverable erasure patterns, we construct generalized sector-disk (GSD) codes, which can recover from disk erasures mixed with sector erasures in a more general setting than known sector-disk (SD) codes. Additionally, the number of sectors in the constructed GSD codes is super-linear in the alphabet size, compared with known SD codes, whose number of sectors is only linear in the alphabet size.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Gap between Scalar and Vector Solutions of Generalized Combination Networks

We study scalar-linear and vector-linear solutions to the generalized combination network. We derive new upper and lower bounds on the maximum number of nodes in the middle layer, depending on the network parameters. These bounds improve and extend the parameter range of known bounds. Using these new bounds we present a general lower bound on the gap in the alphabet size between scalar-linear and vector-linear solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Single-Error Detection and Correction for Duplication and Substitution Channels

Motivated by mutation processes occurring in in-vivo DNA-storage applications, a channel that mutates stored strings by duplicating substrings as well as substituting symbols is studied. Two models of such a channel are considered: one in which the substitutions occur only within the duplicated substrings, and one in which the location of substitutions is unrestricted. Both error-detecting and error-correcting codes are constructed, which can handle correctly any number of tandem duplications of a fixed length $k$, and at most a single substitution occurring at any time during the mutation process.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Clustering and Velocity Distributions in Granular Gases Cooling by Solid Friction

We present large-scale molecular dynamics simulations to study the free evolution of granular gases. Initially, the density of particles is homogeneous and the velocity follows a Maxwell-Boltzmann (MB) distribution. The system cools down due to solid friction between the granular particles. The density remains homogeneous, and the velocity distribution remains MB at early times, while the kinetic energy of the system decays with time. However, fluctuations in the density and velocity fields grow, and the system evolves via formation of clusters in the density field and the local ordering of velocity field, consistent with the onset of plug flow. This is accompanied by a transition of the velocity distribution function from MB to non-MB behaviour. We used equal-time correlation functions and structure factors of the density and velocity fields to study the morphology of clustering. From the correlation functions, we obtain the cluster size, $L$, as a function of time, $t$. We show that it exhibits power law growth with $L(t)\sim t^{1/3}$

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms

The ability to store data in the DNA of a living organism has applications in a variety of areas including synthetic biology and watermarking of patented genetically-modified organisms. Data stored in this medium is subject to errors arising from various mutations, such as point mutations, indels, and tandem duplication, which need to be corrected to maintain data integrity. In this paper, we provide error-correcting codes for errors caused by tandem duplications, which create a copy of a block of the sequence and insert it in a tandem manner, i.e., next to the original. In particular, we present two families of codes for correcting errors due to tandem-duplications of a fixed length, the first family can correct any number of errors while the second corrects a bounded number of errors. We also study codes for correcting tandem duplications of length up to a given constant $k$, where we are primarily focused on the cases of $k=2,3$. Finally, we provide a full classification of the sets of lengths allowed in tandem duplication that result in a unique root for all sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Encoding Semiconstrained Systems

Semiconstrained systems were recently suggested as a generalization of constrained systems, commonly used in communication and data-storage applications that require certain offending subsequences be avoided. In an attempt to apply techniques from constrained systems, we study sequences of constrained systems that are contained in, or contain, a given semiconstrained system, while approaching its capacity. In the case of contained systems we describe to such sequences resulting in constant-to-constant bit-rate block encoders and sliding-block encoders. Surprisingly, in the case of containing systems we show that a "generic" semiconstrained system is never contained in a proper fully-constrained system.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Limited-Magnitude Error-Correcting Gray Codes for Rank Modulation

We construct Gray codes over permutations for the rank-modulation scheme, which are also capable of correcting errors under the infinity-metric. These errors model limited-magnitude or spike errors, for which only single-error-detecting Gray codes are currently known. Surprisingly, the error-correcting codes we construct achieve a better asymptotic rate than that of presently known constructions not having the Gray property, and exceed the Gilbert-Varshamov bound. Additionally, we present efficient ranking and unranking procedures, as well as a decoding procedure that runs in linear time. Finally, we also apply our methods to solve an outstanding issue with error-detecting rank-modulation Gray codes (snake-in-the-box codes) under a different metric, the Kendall $τ$-metric, in the group of permutations over an even number of elements $S_{2n}$, where we provide asymptotically optimal codes.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Yield statistics of interpolated superoscillations

Yield Optimized Interpolated Superoscillations (YOIS) have been recently introduced as a means for possibly making the use of the phenomenon of superoscillation practical. In this paper we study how good is a superoscillation that is not optimal. Namely, by how much is the yield decreased when the signal departs from the optimal one. We consider two situations. One is the case where the signal strictly obeys the interpolation requirement and the other is when that requirement is relaxed. In the latter case the yield can be increased at the expense of deterioration of signal quality. An important conclusion is that optimizing superoscillations may be challenging in terms of the precision needed, however, storing and using them is not at all that sensitive. This is of great importance in any physical system where noise and error are inevitable.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

File Updates Under Random/Arbitrary Insertions And Deletions

A client/encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre/decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files/edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions/deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Paradoxical Quantum Scattering off a Time Dependent Potential?

We consider the quantum scattering off a time dependent barrier in one dimension. Our initial state is a right going eigenstate of the Hamiltonian at time t=0. It consists of a plane wave incoming from the left, a reflected plane wave on the left of the barrier and a transmitted wave on its right. We find that at later times, the evolving wave function has a finite overlap with left going eigenstates of the Hamiltonian at time t=0. For simplicity we present an exact result for a time dependent delta function potential. Then we show that our result is not an artifact of that specific choice of the potential. This surprising result does not agree with our interpretation of the eigenstates of the Hamiltonian at time t=0. A numerical study of evolving wave packets, does not find any corresponding real effect. Namely, we do not see on the right hand side of the barrier any evidence for a left going packet. Our conclusion is thus that the intriguing result mentioned above is intriguing only due to the semantics of the interpretation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Semi-constrained Systems

When transmitting information over a noisy channel, two approaches, dating back to Shannon's work, are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code, or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this paper we analyze a middle road, which we call a semiconstrained system. In such a system, which is an extension of the channel with cost constraints model, we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We address several key issues in this study. The first is proving closed-form bounds on the capacity which allow us to bound the asymptotics of the capacity. In particular, we bound the rate at which the capacity of the semiconstrained $(0,k)$-RLL tends to $1$ as $k$ grows. The second key issue is devising efficient encoding and decoding procedures that asymptotically achieve capacity with vanishing error. Finally, we consider delicate issues involving the continuity of the capacity and a relaxation of the definition of semiconstrained systems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Unusual Transitions Made Possible by Superoscillations

We present a physical scenario in which an electromagnetic field in a state consisted of photons whose energies are smaller than the energy gap of a two-state particle, interacts with the particle, for an arbitrarily long duration, as if it was consisted of photons whose energy matches the energy gap of the particle. This type of interaction is possible when the field is in a specially tailored state whose magnetic field's expectation value is a superoscillatory function.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Construction of Partial MDS (PMDS) and Sector-Disk (SD) Codes with Two Global Parity Symbols

Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while Sector-Disk (SD) codes are erasure codes that address the mixed failure mode of current RAID systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID~5 and RAID~6.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Flow equations for dense granular fluids: New insight from a first-principles derivation

We present a first-principles theory for plug-free dense granular flow. This is done by coarse-graining directly the microscopic dynamics and deriving an explicit relation between the macroscopic stress and strain rate tensors. The newly derived relation not only differs significantly from that of the existing empirical models for such flows but it also provides a novel understanding of the effect of rigid-like rotational regions in the flow.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On a periodicity measure and superoscillations

The phenomenon of superoscillation, where band limited signals can oscillate over some time period with a frequency higher than the band limit, is not only very interesting but it also seems to offer many practical applications. The first reason is that the superoscillation frequency can be exploited to perform tasks beyond the limits imposed by the lower bandwidth of the signal. The second reason is that it is generic and applies to any wave form, be it optical, electrical, sonic, or quantum mechanical. For practical applications, it is important to overcome two problems. The first problem is that an overwhelming proportion of the energy goes into the non superoscillating part of the signal. The second problem is the control of the shape of the superoscillating part of the signal. The first problem has been recently addressed by optimization of the super oscillation yield, the ratio of the energy in the superoscillations to the total energy of the signal. The second problem may arise when the superoscillation, is to mimic a high frequency purely perodic signal. This may be required, for example, when a superoscillating force is to drive a harmonic oscillator at a high resonance frequency. In this paper the degree of periodicity of a signal is defined and applied to some yield optimized superoscillating signals.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quasi-linear Network Coding

We present a heuristic for designing vector non-linear network codes for non-multicast networks, which we call quasi-linear network codes. The method presented has two phases: finding an approximate linear network code over the reals, and then quantizing it to a vector non-linear network code using a fixed-point representation. Apart from describing the method, we draw some links between some network parameters and the rate of the resulting code.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Rate-Distortion for Ranking with Incomplete Information

We study the rate-distortion relationship in the set of permutations endowed with the Kendall Tau metric and the Chebyshev metric. Our study is motivated by the application of permutation rate-distortion to the average-case and worst-case analysis of algorithms for ranking with incomplete information and approximate sorting algorithms. For the Kendall Tau metric we provide bounds for small, medium, and large distortion regimes, while for the Chebyshev metric we present bounds that are valid for all distortions and are especially accurate for small distortions. In addition, for the Chebyshev metric, we provide a construction for covering codes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sensitivity of Yield Optimized Superoscillations

Super oscillating signals are band limited signals that oscillate in some region faster than their largest Fourier component. Such signals have many obvious scientific and technological applications, yet their practical use is strongly limited by the fact that an overwhelming proportion of the energy goes into that part of the signal, which is not superoscillating. In a recent article the problem of optimization of such signals has been studied. In that article the concept of superoscillation yield is defined as the ratio of the energy in the super oscillations to the total energy of the signal, given the range in time and frequency of the superoscillations, which is imposed by forcing the signal to interpolate among a set of predetermined points. The optimization of the superoscillation yield consists of obtaining the Fourier coefficients of the low frequency components of which the signal consists, that maximize the yield under the interpolation constraint. Since in practical applications it is impossible to determine the Fourier coefficients with infinite precision, it is necessary to answer two questions. The first is how is the superoscillating nature of the signal affected by random small deviations in those Fourier coefficients and the second is how is the yield affected? These are the questions addressed in the present article. Limits on the necessary precision are obtained. Those limits seem not to be impractical.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Capacity of String-Replication Systems

It is known that the majority of the human genome consists of repeated sequences. Furthermore, it is believed that a significant part of the rest of the genome also originated from repeated sequences and has mutated to its current form. In this paper, we investigate the possibility of constructing an exponentially large number of sequences from a short initial sequence and simple replication rules, including those resembling genomic replication processes. In other words, our goal is to find out the capacity, or the expressive power, of these string-replication systems. Our results include exact capacities, and bounds on the capacities, of four fundamental string-replication systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Gray codes and Enumerative Coding for vector spaces

Gray codes for vector spaces are considered in two graphs: the Grassmann graph, and the projective-space graph, both of which have recently found applications in network coding. For the Grassmann graph, constructions of cyclic optimal codes are given for all parameters. As for the projective-space graph, two constructions for specific parameters are provided, as well some non-existence results. Furthermore, encoding and decoding algorithms are given for the Grassmannian Gray code, which induce an enumerative-coding scheme. The computational complexity of the algorithms is at least as low as known schemes, and for certain parameter ranges, the new scheme outperforms previously-known ones.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Systematic Error-Correcting Codes for Rank Modulation

The rank-modulation scheme has been recently proposed for efficiently storing data in nonvolatile memories. Error-correcting codes are essential for rank modulation, however, existing results have been limited. In this work we explore a new approach, \emph{systematic error-correcting codes for rank modulation}. Systematic codes have the benefits of enabling efficient information retrieval and potentially supporting more efficient encoding and decoding procedures. We study systematic codes for rank modulation under Kendall's $τ$-metric as well as under the $\ell_\infty$-metric. In Kendall's $τ$-metric we present $[k+2,k,3]$-systematic codes for correcting one error, which have optimal rates, unless systematic perfect codes exist. We also study the design of multi-error-correcting codes, and provide two explicit constructions, one resulting in $[n+1,k+1,2t+2]$ systematic codes with redundancy at most $2t+1$. We use non-constructive arguments to show the existence of $[n,k,n-k]$-systematic codes for general parameters. Furthermore, we prove that for rank modulation, systematic codes achieve the same capacity as general error-correcting codes. Finally, in the $\ell_\infty$-metric we construct two $[n,k,d]$ systematic multi-error-correcting codes, the first for the case of $d=O(1)$, and the second for $d=Θ(n)$. In the latter case, the codes have the same asymptotic rate as the best codes currently known in this metric.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Yield--Optimized Superoscillations

Superoscillating signals are band--limited signals that oscillate in some region faster their largest Fourier component. While such signals have many scientific and technological applications, their actual use is hampered by the fact that an overwhelming proportion of the energy goes into that part of the signal, which is not superoscillating. In the present article we consider the problem of optimization of such signals. The optimization that we describe here is that of the superoscillation yield, the ratio of the energy in the superoscillations to the total energy of the signal, given the range and frequency of the superoscillations. The constrained optimization leads to a generalized eigenvalue problem, which is solved numerically. It is noteworthy that it is possible to increase further the superoscillation yield at the cost of slightly deforming the oscillatory part of the signal, while keeping the average frequency. We show, how this can be done gradually, which enables a trade-off between the distortion and the yield. We show how to apply this approach to non-trivial domains, and explain how to generalize this to higher dimensions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Non-existence of Lattice Tilings by Quasi-crosses

We study necessary conditions for the existence of lattice tilings of $\R^n$ by quasi-crosses. We prove non-existence results, and focus in particular on the two smallest unclassified shapes, the $(3,1,n)$-quasi-cross and the $(3,2,n)$-quasi-cross. We show that for dimensions $n\leq 250$, apart from the known constructions, there are no lattice tilings of $\R^n$ by $(3,1,n)$-quasi-crosses except for ten remaining cases, and no lattice tilings of $\R^n$ by $(3,2,n)$-quasi-crosses except for eleven remaining cases.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Dynamical Inequality in Growth Models

A recent exponent inequality is applied to a number of dynamical growth models. Many of the known exponents for models such as the Kardar-Parisi-Zhang (KPZ) equation are shown to be consistent with the inequality. In some cases, such as the Molecular Beam Equation, the situation is more interesting, where the exponents saturate the inequality. As the acid test for the relative strength of four popular approximation schemes we apply the inequality to the exponents obtained for two Non Local KPZ systems. We find that all methods but one, the Self Consistent Expansion, violate the inequality in some regions of parameter space. To further demonstrate the usefulness of the inequality, we apply it to a specific model, which belongs to a family of models in which the inequality becomes an equality. We thus show that the inequality can easily yield results, which otherwise have to rely either on approximations or general beliefs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Exponent Inequalities in Dynamical Systems

In this letter we derive exponent inequalities relating the dynamic exponent $z$ to the steady state exponent $Γ$ for a general class of stochastically driven dynamical systems. We begin by deriving a general exact inequality, relating the response function and the correlation function, from which the various exponent inequalities emanate. We then distinguish between two classes of dynamical systems and obtain different and complementary inequalities relating $z$ and $Γ$. The consequences of those inequalities for a wide set of dynamical problems, including critical dynamics and Kardar-Parisi-Zhang-like problems are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Generalized Gray Codes for Local Rank Modulation

We consider the local rank-modulation scheme in which a sliding window going over a sequence of real-valued variables induces a sequence of permutations. Local rank-modulation is a generalization of the rank-modulation scheme, which has been recently suggested as a way of storing information in flash memory. We study Gray codes for the local rank-modulation scheme in order to simulate conventional multi-level flash cells while retaining the benefits of rank modulation. Unlike the limited scope of previous works, we consider code constructions for the entire range of parameters including the code length, sliding window size, and overlap between adjacent windows. We show our constructed codes have asymptotically-optimal rate. We also provide efficient encoding, decoding, and next-state algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Labeling Problem of Permutation Group Codes under the Infinity Metric

Codes over permutations under the infinity norm have been recently suggested as a coding scheme for correcting limited-magnitude errors in the rank modulation scheme. Given such a code, we show that a simple relabeling operation, which produces an isomorphic code, may drastically change the minimal distance of the code. Thus, we may choose a code structure for efficient encoding/decoding procedures, and then optimize the code's minimal distance via relabeling. We formally define the relabeling problem, and show that all codes may be relabeled to get a minimal distance at most 2. The decision problem of whether a code may be relabeled to distance 1 is shown to be NP-complete, and calculating the best achievable minimal distance after relabeling is proved hard to approximate. Finally, we consider general bounds on the relabeling problem. We specifically show the optimal relabeling distance of cyclic groups. A specific case of a general probabilistic argument is used to show $\agl(p)$ may be relabeled to a minimal distance of $p-O(\sqrt{p\ln p})$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quasi-Cross Lattice Tilings with Applications to Flash Memory

We consider lattice tilings of $\R^n$ by a shape we call a $(\kp,\km,n)$-quasi-cross. Such lattices form perfect error-correcting codes which correct a single limited-magnitude error with prescribed maximal-magnitudes of positive error and negative error (the ratio of which is called the balance ratio). These codes can be used to correct both disturb and retention errors in flash memories, which are characterized by having limited magnitudes and different signs. We construct infinite families of perfect codes for any rational balance ratio, and provide a specific construction for $(2,1,n)$-quasi-cross lattice tiling. The constructions are related to group splitting and modular $B_1$ sequences. We also study bounds on the parameters of lattice-tilings by quasi-crosses, connecting the arm lengths of the quasi-crosses and the dimension. We also prove constraints on group splitting, a specific case of which shows that the parameters of the lattice tiling of $(2,1,n)$-quasi-crosses is the only ones possible.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Snake-in-the-Box Codes for Rank Modulation

Motivated by the rank-modulation scheme with applications to flash memory, we consider Gray codes capable of detecting a single error, also known as snake-in-the-box codes. We study two error metrics: Kendall's $τ$-metric, which applies to charge-constrained errors, and the $\ell_\infty$-metric, which is useful in the case of limited magnitude errors. In both cases we construct snake-in-the-box codes with rate asymptotically tending to 1. We also provide efficient successor-calculation functions, as well as ranking and unranking functions. Finally, we also study bounds on the parameters of such codes.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Upper critical dimension of the KPZ equation

Numerical results for the Directed Polymer model in 1+4 dimensions in various types of disorder are presented. The results are obtained for system size considerably larger than that considered previously. For the extreme strong disorder case (Min-Max system), associated with the Directed Percolation model, the expected value of the meandering exponent, zeta = 0.5 is clearly revealed, with very week finite size effects. For the week disorder case, associated with the KPZ equation, finite size effects are stronger, but the value of seta is clearly seen in the vicinity of 0.57. In systems with "strong disorder" it is expected that the system will cross over sharply from Min-Max behavior at short chains to weak disorder behavior at long chains. This is indeed what we find. These results indicate that 1+4 is not the Upper Critical Dimension (UCD) in the week disorder case, and thus 4+1 does not seem to be the upper critical dimension for the KPZ equation.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Constant-Weight Gray Codes for Local Rank Modulation

We consider the local rank-modulation scheme in which a sliding window going over a sequence of real-valued variables induces a sequence of permutations. The local rank-modulation, as a generalization of the rank-modulation scheme, has been recently suggested as a way of storing information in flash memory. We study constant-weight Gray codes for the local rank-modulation scheme in order to simulate conventional multi-level flash cells while retaining the benefits of rank modulation. We provide necessary conditions for the existence of cyclic and cyclic optimal Gray codes. We then specifically study codes of weight 2 and upper bound their efficiency, thus proving that there are no such asymptotically-optimal cyclic codes. In contrast, we study codes of weight 3 and efficiently construct codes which are asymptotically-optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Da Vinci Fluids, catch-up dynamics and dense granular flow

We introduce and study a da Vinci Fluid, a fluid whose dissipation is dominated by solid friction. We analyse the flow rheology of a discrete model and then coarse-grain it to the continuum. We find that the model gives rise to behaviour that is characteristic of dense granular fluids. In particular, it leads to plug flow. We analyse the nucleation mechanism of plugs and their development. We find that plug boundaries generically expand and we calculate the growth rate of plug regions. In systems whose internal effective friction coefficient is relatively uniform we find that the linear size of plug regions grows as (time)$^{1/3}$. The suitability of the model to granular materials is discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Plug flow formation and growth in da Vinci Fluids

A new, da Vinci, fluid is described as a model for flow of dense granular matter. We postulate local properties of the fluid, which are generically different from ordinary fluids in that energy is dissipated by solid friction. We present the equation of flow of such a fluid and show that it gives rise to formation and growth of plug flow regions, which is characteristic of flow of granular matter. Simple explicit examples are presented to illustrate the evolution of plug flow regions.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Trajectory Codes for Flash Memory

Flash memory is well-known for its inherent asymmetry: the flash-cell charge levels are easy to increase but are hard to decrease. In a general rewriting model, the stored data changes its value with certain patterns. The patterns of data updates are determined by the data structure and the application, and are independent of the constraints imposed by the storage medium. Thus, an appropriate coding scheme is needed so that the data changes can be updated and stored efficiently under the storage-medium's constraints. In this paper, we define the general rewriting problem using a graph model. It extends many known rewriting models such as floating codes, WOM codes, buffer codes, etc. We present a new rewriting scheme for flash memories, called the trajectory code, for rewriting the stored data as many times as possible without block erasures. We prove that the trajectory code is asymptotically optimal in a wide range of scenarios. We also present randomized rewriting codes optimized for expected performance (given arbitrary rewriting sequences). Our rewriting codes are shown to be asymptotically optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2001arXiv

Shape fluctuations of a Deforamable Body in a Randomly Stirred Host Fluid

Consider a deformable body immersed in an incompressible fluid that is randomly stirred. Sticking to physical situations in which the body departs only slightly from its spherical shape, we investigate the deformations of the body. The shape is decomposed into spherical harmonic modes. We study the correlations of these modes for a general class of random flows that include the flow due to thermal agitation. Our results are general in the sense that they are applicable to any body that is described solely by the shape of its surface.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

Streched exponential in non-linear stochastic filed theories

We consider the time dependent two point function, <ϕ_q (t) ϕ_-q (0)> in non-linear stochastic field theories, for which the KPZ equation serves as a prototype. In particular we consider the small q's and long times such that ω_q t>>1 (ω_q being the corresponding decay rate). We find that, since the generic case has ω_q \propto q^μfor small q where μ>1, the decay of the two point function is given by a streched exponential in ω_qt multiplied by a factor of t, <ϕ_q (t) ϕ_-q (0)> \propto t^{β_d}exp[-γ(ω_qt)^{1/μ}], where β_d=(d-1)/2μ, d is the dimensionality of space and γa dimensionless constant.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

Directed polymers at finite temperatures in 1+1 and 2+1 dimensions

We present systematic numerical simulations for directed polymers at finite temperatures in 1+1 and 2+1 dimensions. The transverse fluctuations and free energy fluctuations tend to the strong coupling limit at any temperature in both 1+1 and 2+1 dimensions for long time t. Two different definitions for energy fluctuations at finite temperatures, which are the ensemble energy fluctuations and the internal energy fluctuations, are investigated. Apart from zero temperature, the behavior of the energy fluctuations and the free energy fluctuations for directed polymers is shown to be different. At finite temperatures, the ensemble energy fluctuations in both 1+1 and 2+1 dimensions and internal energy fluctuations in 1+1 dimensions scale as t^{1/2} where the free energy fluctuations in 1+1 dimensions and 2+1 dimensions scale as t^{1/3} and t^{0.2} respectively. As a consequence of that the specific heat in both 1+1 and 2+1 dimensions scales as t and the entropy fluctuations in 1+1 dimensions scale as t^{1/2} at any finite temperature.

0 citations0 reviewsNo code linkedOpen access