|
Disjunct Matrix
In mathematics, a logical matrix may be described as ''d''-disjunct and/or ''d''-separable. These concepts play a pivotal role in the mathematical area of non-adaptive group testing. In the mathematical literature, ''d''-disjunct matrices may also be called superimposed codes or ''d''-cover-free families. According to Chen and Hwang (2006), * A matrix is said to be ''d''-separable if no two sets of ''d'' columns have the same boolean sum. * A matrix is said to be \overline-separable (that's ''d'' with an overline) if no two sets of ''d''-or-fewer columns have the same boolean sum. * A matrix is said to be ''d''-disjunct if no set of ''d'' columns has a boolean sum which is a superset of any other single column. The following relationships are "well-known": * Every \overline-separable matrix is also d-disjunct. * Every d-disjunct matrix is also \overline-separable. * Every \overline-separable matrix is also d-separable (by definition). Concrete examples The following 6\times 8 m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Logical Matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in combinatorial mathematics and theoretical computer science. Matrix representation of a relation If ''R'' is a binary relation between the finite indexed sets ''X'' and ''Y'' (so ), then ''R'' can be represented by the logical matrix ''M'' whose row and column indices index the elements of ''X'' and ''Y'', respectively, such that the entries of ''M'' are defined by :m_ = \begin 1 & (x_i, y_j) \in R, \\ 0 & (x_i, y_j) \not\in R. \end In order to designate the row and column numbers of the matrix, the sets ''X'' and ''Y'' are indexed with positive integers: ''i'' ranges from 1 to the cardinality (size) of ''X'', and ''j'' ranges from 1 to the cardinality of ''Y''. See the article on indexed sets for more detail. The transpose ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Compressed Sensing
Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a Signal (electronics), signal by finding solutions to Underdetermined system, underdetermined linear systems. This is based on the principle that, through optimization, the sparsity of a signal can be exploited to recover it from far fewer samples than required by the Nyquist–Shannon sampling theorem. There are two conditions under which recovery is possible. The first one is sparsity, which requires the signal to be sparse in some domain. The second one is incoherence, which is applied through the isometric property, which is sufficient for sparse signals. Compressed sensing has applications in, for example, magnetic resonance imaging (MRI) where the incoherence condition is typically satisfied. Overview A common goal of the engineering field of signal processing is to reconstruct a signal from a series ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Piotr Indyk
Piotr Indyk is Thomas D. and Virginia W. Cabot Professor in the Theory of Computation Group at the Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology. Academic biography Indyk received the Magister (MA) degree from the University of Warsaw in 1995 and a PhD in computer science from Stanford University in 2000 under the supervision of Rajeev Motwani. In 2000, Indyk joined MIT where he currently holds the title of Thomas D. and Virginia W. Cabot Professor in the Department of Electrical Engineering and Computer Science. Research Indyk's research focuses primarily on computational geometry in high-dimensions, streaming algorithms, and computational learning theory. He has made a range of contributions to these fields, particularly in the study of low-distortion embeddings, algorithmic coding theory, and geometric and combinatorial pattern matching. He has also made contributions to the theory of compressed sensing. His work on algo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Israel Journal Of Mathematics
'' Israel Journal of Mathematics'' is a peer-reviewed mathematics journal published by the Hebrew University of Jerusalem ( Magnes Press). History Founded in 1963, as a continuation of the ''Bulletin of the Research Council of Israel'' (Section F), the journal publishes articles on all areas of mathematics. The journal is indexed by ''Mathematical Reviews'' and Zentralblatt MATH. Its 2009 MCQ was 0.70, and its 2009 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a type of journal ranking. Journals with higher impact factor values are considered more prestigious or important within their field. The Impact Factor of a journa ... was 0.754. External links * Mathematics journals Academic journals established in 1963 Academic journals of Israel English-language journals Bimonthly journals Hebrew University of Jerusalem {{math-journal-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Zoltán Füredi
Zoltán Füredi (Budapest, Hungary, 21 May 1954) is a Hungarian mathematician, working in combinatorics, mainly in discrete geometry and extremal combinatorics. He was a student of Gyula O. H. Katona. He is a corresponding member of the Hungarian Academy of Sciences (2004). He is a research professor of the Rényi Mathematical Institute of the Hungarian Academy of Sciences, and a professor at the University of Illinois Urbana-Champaign (UIUC). Füredi received his Candidate of Sciences degree in mathematics in 1981 from the Hungarian Academy of Sciences. Some results * In infinitely many cases he determined the maximum number of edges in a graph with no ''C''4. * With Paul Erdős he proved that for some ''c''>1, there are ''c''''d'' points in ''d''-dimensional space such that all triangles formed from those points are acute. * With Imre Bárány he proved that no polynomial time algorithm determines the volume of convex bodies in dimension ''d'' within a multiplicative err ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Péter Frankl
Péter Frankl (born 26 March 1953 in Kaposvár, Somogy County, Hungary) is a mathematician, street performer, columnist and educator, active in Japan. Frankl studied mathematics at Eötvös Loránd University in Budapest and submitted his PhD thesis while still an undergraduate. He holds a PhD degree from the University Paris Diderot as well. He has lived in Japan since 1988, where he is a well-known personality and often appears in the media. He keeps travelling around Japan performing (juggling and giving public lectures on various topics). Frankl won a gold medal at the International Mathematical Olympiad in 1971. He has seven joint papers with Paul Erdős, and eleven joint papers with Ronald Graham. His research is in combinatorics, especially in extremal combinatorics. He is the author of the union-closed sets conjecture. Personality Both of his parents were survivors of concentration camps and taught him "The only things you own are in your heart and brain". So he beca ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Paul Erdős
Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, graph theory, number theory, mathematical analysis, approximation theory, set theory, and probability theory. Much of his work centered on discrete mathematics, cracking many previously unsolved problems in the field. He championed and contributed to Ramsey theory, which studies the conditions in which order necessarily appears. Overall, his work leaned towards solving previously open problems, rather than developing or exploring new areas of mathematics. Erdős published around 1,500 mathematical papers during his lifetime, a figure that remains unsurpassed. He was known both for his social practice of mathematics, working with more than 500 collaborators, and for his eccentric lifestyle; ''Time'' magazine called him "The Oddball's Oddba ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete Applied Mathematics
''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split off from another Elsevier journal, ''Discrete Mathematics'', in 1979, with that journal's founder Peter Ladislaw Hammer as its founding editor-in-chief. Abstracting and indexing The journal is abstracted and indexing in: According to the ''Journal Citation Reports'', the journal has a 2020 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a type of journal ranking. Journals with higher impact factor values are considered more prestigious or important within their field. The Impact Factor of a journa ... of 1.139. References External links *{{official website, http://www.journals.elsevier.com/discrete-applied-mathematics/ Discrete mathematics journals Academic journals established in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Concatenated Code
In coding theory, concatenated codes form a class of error-correcting codes that are derived by combining an inner code and an outer code. They were conceived in 1966 by Dave Forney as a solution to the problem of finding a code that has both exponentially decreasing error probability with increasing block length and polynomial-time decoding complexity. Concatenated codes became widely used in space communications in the 1970s. Background The field of channel coding is concerned with sending a stream of data at the highest possible rate over a given communications channel, and then decoding the original data reliably at the receiver, using encoding and decoding algorithms that are feasible to implement in a given technology. Shannon's channel coding theorem shows that over many common channels there exist channel coding schemes that are able to transmit data reliably at all rates R less than a certain threshold C, called the channel capacity of the given channel. In fact, the p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group Testing
In statistics and combinatorics, combinatorial mathematics, group testing is any procedure that breaks up the task of identifying certain objects into tests on groups of items, rather than on individual ones. First studied by Robert Dorfman in 1943, group testing is a relatively new field of applied mathematics that can be applied to a wide range of practical applications and is an active area of research today. A familiar example of group testing involves a string of light bulbs connected in series, where exactly one of the bulbs is known to be broken. The objective is to find the broken bulb using the smallest number of tests (where a test is when some of the bulbs are connected to a power supply). A simple approach is to test each bulb individually. However, when there are a large number of bulbs it would be much more efficient to pool the bulbs into groups. For example, by connecting the first half of the bulbs at once, it can be determined which half the broken bulb is in, r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial-time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is gener ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
