搜索结果: 1-15 共查到“代数学 Complexity”相关记录18条 . 查询时间(0.057 秒)
Simple Bounds for Recovering Low-complexity Models
`1-norm minimization nuclear-norm minimization block-sparsity duality random matrices
2015/6/17
This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in Rn can be efficien...
We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in p 2 . In the case of linear matroids, which are
represented over polynomially growing fie...
Randomized Communication Complexity for Linear Algebra Problems over Finite Fields
communication complexity streaming, matrix singularity determinant
2012/12/3
Finding the singularity of a matrix is a basic problem in linear algebra. Chu and Schnitger first considered this problem in the communication complexity model, in which Alice holds the first half of ...
Complexity for Modules Over the Classical Lie Superalgebra gl(m|n)
Complexity the Classical Lie Superalgebra gl(m|n) Representation Theory
2011/9/5
Abstract: Let $\mathfrak{g}=\mathfrak{g}_{\bar{0}}\oplus \mathfrak{g}_{\bar{1}}$ be a classical Lie superalgebra and $\mathcal{F}$ be the category of finite dimensional $\mathfrak{g}$-supermodules whi...
The computational complexity of recognising embeddings in finitely presented groups
Finitely presented groups embeddings Kleene’s arithmetical hierarchy decidability universal finitely presented group
2011/8/29
Abstract: We extend a result by Lempp that recognising torsion-freeness for finitely presented groups is $\Pi^{0}_{2}$-complete; we show that the problem of recognising embeddings of finitely presente...
Asymptotic invariants, complexity of groups and related problems
word problem conjugacy problem computational complexity
2011/1/19
We survey results about computational complexity of the word problem in groups, Dehn functions of groups and related problems.
Towards a Low-Complexity Dynamic Decode-and-Forward Relay Protocol
Low-Complexity Dynamic Decode-and-Forward Relay Protocol
2011/1/17
The dynamic decode-and-forward (DDF) relaying protocol is a relatively new cooperative scheme
which has been shown to achieve promising theoretical results in terms of diversity-multiplexing gain tra...
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
Optimal Lower Bound Communication Complexity Gap-Hamming-Distance
2010/12/15
We prove an optimal W(n) lower bound on the randomized communication complexity of the much-studied GAP-HAMMING-DISTANCE problem. As a consequence, we obtain essentially optimal multi-pass space lower...
Reduced Complexity Decoding for Bit-Interleaved Coded Multiple Beamforming with Constellation Precoding
Complexity Decoding Bit-Interleaved Coded Multiple Beamforming Constellation Precoding
2010/12/8
Multiple beamforming is realized by singular value decomposition of the channel matrix which is assumed to be perfectly known to the transmitter as well as the receiver. Bit-Interleaved Coded Multiple...
Linear Transceiver Design for Interference Alignment: Complexity and Computation
Linear Transceiver Interference Alignment: Complexity Computation
2010/12/8
Consider a MIMO interference channel whereby each transmitter and receiver are equipped with
multiple antennas. The basic problem is to design optimal linear transceivers (or beamformers) that can ma...
Kolmogorov complexity, Lovasz local lemma and critical exponents
Kolmogorov complexity Lovasz local lemma critical exponents
2010/12/13
D. Krieger and J. Shallit have proved that every real number greater than 1 is a critical exponent of some sequence [1].We show how this result can be derived from some general statements about sequen...
Cox rings of rational complexity one T-varieties
Cox ring branched coverings torus actions
2010/11/29
Let X be a Mori dream space together with an effective torus action of complexity one. In this note, we construct a polyhedral divisor DCox on a suitable finite covering of P1 which corresponds to the...
Forbidden substrings, Kolmogorov complexity and almost periodic sequences
Forbidden substrings Kolmogorov complexity almost periodic sequences
2010/12/10
Assume that for some < 1 and for all nutural n a set Fn of at most 2 n “forbidden” binary strings of length n is fixed. Then there exists an infinite binary sequence ! that does not have (long) forb...
On the Complexity of Matroid Isomorphism Problems
On the Complexity of Matroid Isomorphism Problems
2012/12/3
We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in Σp 2 . In the case of linear matroids, which are represented over polynomially growing fiel...
In this paper, we prove that there is a natural equivalence between the category ${\scr F}_1(x)$ of Koszul modules of complexity $1$ with filtration of given cyclic modules as the factor modules of an...