User apurva - MathOverflow

Answer by Apurva for How to find which subset of bitfields xor to another bitfield?

2010-10-04T18:57:00Z

The ways to solve it may vary based on which varies more frequently: the dictionary $A$ used to generate the wanted bitstring $B$, or the bitstring $B$.

First, fix the length of the words we are talking about to $n$ bits.

The dictionary $A$ is a set of $n$-bit long words $A=${$a_1,a_2,...a_m$}, $a_i \in ${$0,1$}${}^n$.

Given an insufficient dictionary, it may not be possible to generate all possible bit patterns of length $n$. For example, if $C$={ 1000, 0011, 0001}, then it is impossible for the dictionary $C$ to generate the bit-pattern $x_4 1 x_2 x_1$, a 4-bit string with the $2^2$ value set to $1$.

It may make sense given a dictionary $A$ of $n$-bit length words to test the dictionary as a viable signal generator by seeing if it is possible to create the "single-bit-on" patterns in the dictionary $C$ defined as

$ C=${$c_1, c_2, ..., c_{n}$}
such that {$c_m = d_n d_{n-1}...d_2 d_1 $} where
$d_j=1$ if $j=m$, and
$d_j=0$ if $j\ne m$

If it is not possible for the dictionary $A$ to generate the dictionary $C$, then there will be certain bit patterns which are not reachable by using words in the dictionary $A$ and the binary-operation XOR.

Once a mapping is generated from $A$ to the single-bit-on dictionary $C$, it is a simple task to create the mapping from $A$ to an arbitrary bit pattern, $B$. Take the bits which are on in $B$, and take the mappings which generate those single bits on in $C$, and concatenate them together.

An even number of XOR's for any particular bit pattern in $C$ cancel each other out, leaving a single count of whichever elements in $A$ would generate bit-pattern $B$.

One quick observation: the dictionary $A$ of $n$-bit long words must contain at least $n$ words for it to be able to generate all possible $n$-bit long strings, and none of them should be linear combinations of the other.

For example, the alphabet X={0001, 1000} is too small to be able to generate all possible 4-bit long words, simply from the observation that it only contains two words of 4-bit length.

The alphabet Y={0001, 0011, 0010, 1000, 1001} has enough words to possibly span all possible 4-bit length words, however $Y_2 = Y_1$ XOR $Y_3$, and $Y_5 = Y_1 $ XOR $Y_4$. It is not possible to generate the bit patterns $a1cd$, where $a,c,d \in ${0,1} using alphabet $Y$. Even though $Y$ is defined as $5$ elements, it really only contains 3 degrees of freedom, as two of the elements can be defined as linear combinations of the others.

In other words, using gaussian elimination on your dictionary using XOR as the operation on the right may be the best way to test or assess your dictionary, with the caveat that if your dictionary does not contain at least as many words as there are bits in each word then your dictionary will not suffice to generate all possible bit patterns.

It's also possible to think of this as operations of a message being passed along the nodes of an $n$-dimensional hypercube. But that's just a different way of thinking of it.

Answer by Apurva for Math paper authors' order

2010-09-02T23:24:39Z

In Medicine and in Surgery, the convention is similar to that of the Physical Sciences with the most significant contributor being first or last, or with the owner of the lab equipment or funding getting senior author position as the last author.

However, there is a curve ball in Medical and Surgical Journals in that the first three authors are the ones who gain the most credit. The reason for this is that back in the pre-WWW-historic era, when I wrote papers that went into Surgical journals and when I went through medical school and surgical residency, the medical journal articles were all indexed in the Index Medicus.

The Index Medicus was a hard-copy index prepared at the end of each year and found in every medical library with three sets of listings sorted by Medical E-something Subject Headings (MeSH), title of the journal article, and the last name of the first three authors. This paper index was how people found journal articles of interest and how the authors gained "publication cred." I ended up as third author on many papers giving me a lot of cred even above some grad students and post-docs who helped with experiments but had not supervised or designed (or originally proposed some of, i.e. conception and design, as I had) the experiments in these papers as I had.

Because of the problem with "author inflation" (people being added to author lists as a courtesy or to accomodate seniority), journals in medical fields such as JAMA (Journal of the American Medical Association) now require authors to submit signed Authorship Responsibility Forms which outline specifically what constitutes valid criteria for being listed as an author on a paper:

Obtaining funding is listed as one of the possible criteria, as are administrative, technical, or material support. Some of these criteria surprised me as being rather flimsy in some contexts.

Algorithms for modeling asynchronicity in Asynchronous Cellular Automata

2010-08-19T19:36:31Z

Most cellular automata are defined as being updated synchronously. I am interested in asynchronous automata, where they do not all have to update simultaneously. I am restricting myself to cellular automata on a graph (e.g. lattice) where the cellular automata is a FSM and all of the automata on the graph are identical.

I have seen some representations of asynchronously updated networks as synchronous updating of the automata with probabilistic updating of the cells, i.e. at each time step, each cell has probability $p$ of possibly updating its state.

I have seen asynchronous models where there is a single ordered list of the individual cells with each cell firing one after the other, with the same ordering maintained over multiple cycles, or with a different ordering being generated each time after all of the cells have fired. In this scheme, a cell is guaranteed to fire at most $3$ times in $2*n$ time-steps if there are $n$ total cells or at most $x+1$ times in $x*n$ time-steps ($x$ cycles of $n$ timesteps). (Example, it fires at time $n$ in the first cycle, at any time $n+s, (0 \le s \le n)$ in the second cycle, and at time $2n+1$ in the third cycle, meaning it fires 3 times during the $n+2$ steps from $t=n$ to $t=2n+1$.

I have also seen sequential firing, where at each time step a single cell is chosen to be updated, with no restrictions on firing all of the cells before starting over. This schema also averages a cell firing once every $n$ time-steps, but does not restrict it from firing more frequently.

Are there other better ways to mathematically model asynchronous cellular automata? What are the pitfalls and benefits of these particular schemes? I also agree at the outset that the type of firing scheme to be used for an asynchronous system depends on the particular system being modeled; I am asking for general answers or references for algorithms to model asynchronicity.

Answer by Apurva for Tractably Partitioning the possible vertex k-colorings of a graph by local stability and instability.

2010-08-19T19:14:47Z

If you limit it to specific classes of graphs, say for example star graphs, you can come up with some answers. For a star graph $S_m$, with a vertex at the center and $m$ vertices connected to the center, yielding a graph $G$ with $n=m+1$ vertices and $m$ edges, it can be calculated that for $k=2$

If the center vertex is labeled black, then the only "0-unstable" coloring is where all of the leaves are white. If any of the leaves are also black, say $j$ of the $m$ leaves are black while the center is also black, then the center and those $j$ black leaves are unstable, leaving $m-j$ leaves as stable nodes. There are $m \choose j$ = ($m$ choose $j$) ways to color $j$ of the $m$ leaves as black.

The same is true with the color labels reversed if the center is labeled white. Thus for $k=2$, for two-color labeling of a star-graph $S_m$ with $m$ leaves and $n=m+1$ vertices, the sizes of the partitions of all of the possible two-colorings are as follows:

|{0 unstable}| = 2

|{1 unstable}| = 0

|{r unstable}| = $2 \times$ ${m}\choose{r-1}$ for $ 2 \le r \le n$, with $r \in Z $

The size of the 1-unstable partition is always zero for this family of graphs. The size of the 1-unstable partition is always zero for any graph and for any $k$ because instablity occurs over an edge linking two vertices with the same color label, thus always creating two unstable vertices if there are any unstable vertices at all.

The sum of all of these partitions sizes is $2^n$, thus all of the possible $2^n$ colorings of the $n=m+1$ vertex star graph $S_m$ have been accounted for. A similar calculation can be made for star graphs for $k>2$.

Apurva

Comment by Apurva

2010-09-16T22:19:32Z

@Jon Yard, @Deane Yang, wasn't there a turf battle between mathematics and electrical engineering for "ownership" or "rights" to computer science and information theory. At some places, computer science is a part or division of Electrical Engineering. At few, computer science is a branch of mathematics. And at many places, it is a department in its own right. The same thing happens with Neurosurgery. Some schools have Divisions of Neurosurgery as part of the Department of Surgery, others free-standing Depts of Neurosurgery, and for some odd ducks it's part of Neurology, a medical branch.

Comment by Apurva

2010-09-16T22:08:22Z

@Barbara, (sadly), obtaining funding for a lab is considered valid criteria for claiming authorship according to the American Medical Association. See my comment below regarding their authorship form requirements.

Comment by Apurva

2010-09-13T21:36:02Z

Is the spanning tree $T$ a given at the beginning of this problem, or is it a part of the problem to also find the spanning tree?