23,460 research outputs found
Recommended from our members
THE READ-LEHMAN LETTERS ON KINSHIP MATHEMATICS
No full textFollowing the publication of the letter from Dwight Read, (see “New Results: The Logic of Older/Younger Sibling Terms in Classificatory Terminologies” in MACT Letters, November 9 2004) Kris Lehman (F. K. L. Chit Hlaing) responded to that letter. Together Professors Read and Lehman then agreed to compile an exchange, including previous discussions, and have submitted the sequence of letters below to MACT. They offer the exchange both to record some important developments in the mathematical theory of kinship category systems as reflected in their joint work in progress, and to record the way such work develops through technical exchanges
On Read-k Projections of the Determinant
No full textWe consider read-k determinantal representations of polynomials and prove some non-expressibility results. A square matrix M whose entries are variables or field elements will be called read-k, if every variable occurs at most k times in M. It will be called a determinantal representation of a polynomial f if f = det(M). We show that
- the n × n permanent polynomial does not have a read-k determinantal representation for k ∈ o(√n/log n) (over a field of characteristic different from two). We also obtain a quantitative strengthening of this result by giving a similar non-expressibility for k ∈ o(√n/log n) for an explicit n-variate multilinear polynomial (as opposed to the permanent which is n²-variate)
A Note on Read-k Times Branching Programs
No full text. A syntactic read-k times branching program has the restriction that no variable occurs more than k times on any path (whether or not consistent) . We exhibit an explicit Boolean function f; which cannot be computed by nondeterministic syntactic read-k times branching programs of size less than exp i \Omega ip n k 2k jj ; although its complement :f has a nondeterministic syntactic read-once branching program of polynomial size. This, in particular, means that the nonuniform analogue of NLOGSPACE = co \Gamma NLOGSPACE fails for syntactic read-k times networks with k = o(log n): We also show that (even for k = 1) the syntactic model is exponentially weaker then more realistic "nonsyntactic" one. Keywords: Branching programs, read-k times networks, lower bounds y To appear in: RAIRO J. Theoretical Informatics and Application z Universitat Trier, FB Informatik, 54286 Trier, GERMANY. E--mail: [email protected] Online access for ECCC: FTP: ftp.eccc.uni-trier.de:/pub/eccc/ W..
A Note on Read-k Times Branching Programs
No full textA syntactic read-k times branching program has the restriction that no variable occurs more than k times on any path (whether or not consistent). We exhibit an explicit Boolean function f; which cannot be computed by nondeterministic syntactic read-k times branching programs of size less than exp i\Omega ip n k 2k jj ; although its complement :f has a nondeterministic syntactic read-once branching program of polynomial size. This, in particular, means that the nonuniform analogue of NLOGSPACE = co \Gamma NLOGSPACE fails for syntactic read-k times networks with k = o(log n): We also show that (even for k = 1) the syntactic model is exponentially weaker then more realistic "nonsyntactic" on
Notes on Boolean Read-k and Multilinear Circuits
No full textA monotone Boolean (OR,AND) circuit computing a monotone Boolean function f
is a read-k circuit if the polynomial produced (purely syntactically) by the
arithmetic (+,x) version of the circuit has the property that for every prime
implicant of f, the polynomial contains at least one monomial with the same set
of variables, each appearing with degree at most k. Every monotone circuit is a
read-k circuit for some k. We show that already read-1 (OR,AND) circuits are
not weaker than monotone arithmetic constant-free (+,x) circuits computing
multilinear polynomials, are not weaker than non-monotone multilinear
(OR,AND,NOT) circuits computing monotone Boolean functions, and have the same
power as tropical (min,+) circuits solving combinatorial minimization problems.
Finally, we show that read-2 (OR,AND) circuits can be exponentially smaller
than read-1 (OR,AND) circuits.Comment: A throughout revised version. To appear in Discrete Applied
Mathematic
The construction of Karen Karnak: The multi-author-function
No full textThis thesis is situated within the comparatively recent developments of Web 2.0 and the emergence of interactive WikiMedia, and explores the mode of authorship within a Read/Write culture compared to that of a Read/Only tradition. The hypothesis of this study is that the role of the audience has become merged with the author, and as such, represents new functions and attributes, distinct from a more conventional concept of authorship, in which the roles of audience and author are more separate. Read/Write and participatory culture, as defined by this study, is focused on collaboration, and includes the influences of D.I.Y. culture, Open-Source practices and the production of text by multiple authors. Multi-authorship presents a re-thinking of several concepts which support the notion of the individual author, since the focus of multi-authorship is not on attribution and ownership of a finished text, but on the continued malleability of a text. Modes of multi-authorship, demonstrated in the use of the pseudonyms Alan Smithee and Karen Eliot, represent declarative authors whose names signify multiple origins, whilst concurrently indicating a distinct body of work. The function of these names form an important context to this study, since primary research involves the construction of an experimental mode of multi-authorship utilising WikiMedia technology and the interaction of thirty nine participants, who are invited to create a body of work under the collective pseudonym Karen Karnak. The data generated by this experiment is analysed using aspects of Michel Foucault's author-function to identify and determine power structures inherent in the WikiMedia context. The interplay of power structures, including concepts such as identity, ownership and the body of work, affect the resulting mode of authorship and contribute to the construction of Karen Karnak, suggesting further areas of research into the emerging multi-author
Read-through motifs are avoided in highly expressed genes.
No full text“TGACA” and “TGACT” (stop codon underlined) are two previously identified sequence motifs conducive to stop-codon read-through. A total of 6,572 yeast genes and 11,895 fruit fly genes are considered. (A-D) Yeast (A-B) and fruit fly (C-D) genes with and without the read-through motifs show significantly different expression levels. The distribution of gene expression level is shown in a box plot, where the lower and upper edges of a box represent the first (qu1) and third quartiles (qu3), respectively, the horizontal line inside the box indicates the median (md), the whiskers extend to the most extreme values inside inner fences, md±1.5(qu3-qu1), and the circles represent values outside the inner fences (outliers). P-values are based on Mann-Whitney U tests. (E-H) Observed and expected motif frequencies in yeast (E-F) and fruit fly (G-H) genes of low, medium, and high expressions. Genes are ranked by expression levels and then divided into three bins of equal numbers of genes. Each bar shows the observed motif frequency, with the error bar representing the standard deviation based on 1,000 bootstrap samples of genes within the bin. Each dot shows the motif frequency expected from the observed frequencies of the three components (stop codon and each of the following two nucleotides) of the motif in the bin. We shuffled motif components among genes in the same bin 10,000 times, and the P-value above each dot shows the probability that the number of motifs observed upon a shuffle is equal to or smaller than the number in the actual genes. (I-K) Frequencies of the stop codon TGA (I), C following the stop codon (J), and A/T at the next position (K) in yeast (grey bars) and fruit fly (white bars) genes of low, medium, and high expressions. Error bars show standard deviations based on 1,000 bootstrap samples of genes within the bin. Note that the Y-axis does not start from 0 in (I)-(K).</p
Identity Testing and Lower Bounds for Read- <i>k</i> Oblivious Algebraic Branching Programs
No full text
Read-
k
oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ABP). In this work, we give an exponential lower bound of exp (
n/k
O
(
k
)
) on the width of any read-
k
oblivious ABP computing some explicit multilinear polynomial
f
that is computed by a polynomial-size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2
Õ(
n
1−1/2
k
−1
)
and needs white box access only to know the order in which the variables appear in the ABP.
</jats:p
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs
No full textRead-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp(n/k^{O(k)}) on the width of any read-k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2^{~O(n^{1-1/2^{k-1}})} and needs white box access only to know the order in which the variables appear in the ABP
On the Expressive Power of Read-Once Determinants
No full textWe introduce and study the notion of read-k projections of the determinant: a polynomial f∈F[x1,…,xn] is called a read-k projection of determinant if f=det(M), where entries of matrix M are either field elements or variables such that each variable appears at most k times in M. A monomial set S is said to be expressible as read-k projection of determinant if there is a read-k projection of determinant f such that the monomial set of f is equal to S. We obtain basic results relating read-k determinantal projections to the well-studied notion of determinantal complexity. We show that for sufficiently large n, the n×n permanent polynomial Permn and the elementary symmetric polynomials of degree d on n variables Sdn for 2≤d≤n−2 are not expressible as read-once projection of determinant, whereas mon(Permn) and mon(Sdn) are expressible as read-once projections of determinant. We also give examples of monomial sets which are not expressible as read-once projections of determinant
- …
