{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:37:02Z","timestamp":1787323022088,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We prove that for every prime $p$ there exists a (0,1)-matrix $M$ of size $t_p(n,m)\\times n$, where $t_p(n,m)=O(m+\\frac{m\\log \\frac{n}{m}}{\\log \\min({m,p})})$ such that every $m$ columns of $M$ are linearly independent over $\\mathbb{Z}_p$, the field of integers modulo $p$ (and therefore over any field of characteristic $p$ and over the field of real numbers $\\mathbb{R}$). In coding theory this matrix is a parity-check (0,1)-matrix over $\\mathbb{Z}_p$ of a linear code of minimal distance m+1. Using the Hamming bound (for $p&lt;m$) and the information theoretic argument (for $p\\ge m$) it can be shown that the above bound is tight. This solves the following open problems: (1) Coin weighing problem: Suppose that $n$ coins are given among which there are at most $m$ counterfeit coins of arbitrary weights. There is a nonadaptive algorithm that finds the counterfeit coins and their weights in $t(n,m)=O((m\\log n)\/\\log m)$ weighings. A previous result [S. S. Choi and J. H. Kim, in Proceedings of the 2008 ACM International Symposium on Theory of Computing, ACM, New York, 2008, pp. 749--758] proves the existence of a nonadaptive algorithm that solves the problem (with the same complexity) only for weights between $n^{-a}$ and $n^b$ for constants $a$ and $b$ and finds the counterfeit coins but not their weights. (2) Reconstructing graph from additive queries: Suppose that $G$ is an unknown weighted graph with $n$ vertices and at most $m$ edges. There exists a nonadaptive algorithm that finds the edges of $G$ and their weights in $O(t(n,m))$ additive queries. Previous results [S. S. Choi and J. H. Kim, in Proceedings of the 2008 ACM International Symposium on Theory of Computing, ACM, New York, 2008, pp. 749--758; N. H. Bshouty and H. Mazzawi, in Proceedings of the 20th International Conference on Algorithmic Learning Theory, Springer, Berlin, 2009, pp. 97--109] prove the existence of a nonadaptive algorithm that solves the problem only for weights between $n^{-a}$ and $n^b$ for constants $a$ and $b$ and finds the edges but not their weights. (3) Signature coding problem: Consider $n$ stations and at most $m$ of them want to send messages from $\\mathbb{Z}_p$ through an adder channel, that is, a channel whose output is the sum of the messages. Then all messages can be sent (encoded and decoded) with $O(t(n,m))$ transmissions. Previous algorithms [E. Biglieri and L. Gy\u00f6rfi, Multiple Access Channels: Theory and Practice, NATO Security through Sci. Ser. D: Inform. Commun. Security, IOS Press, Amsterdam, 2007] run with the same number of transmissions only for messages in $\\{0,1\\}$. Simple information theoretic arguments show that all the above bounds are tight.<\/jats:p>","DOI":"10.1137\/120881129","type":"journal-article","created":{"date-parts":[[2015,3,31]],"date-time":"2015-03-31T16:11:20Z","timestamp":1427818280000},"page":"631-657","source":"Crossref","is-referenced-by-count":0,"title":["On Parity Check (0,1)-Matrix over $\\mathbb{Z}_p$"],"prefix":"10.1137","volume":"29","author":[{"given":"Nader H.","family":"Bshouty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hanna","family":"Mazzawi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,3,31]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90026-0"},{"key":"atypb2","unstructured":"M. Aigner,\n                      Combinatorial Search\n                      , John Wiley and Sons, Chichester, UK, 1988."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0378-3758(85)90084-9"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"atypb5","unstructured":"B. Bolloba\u0301s,\n                      Random graphs\n                      , second ed., Cambridge Stud. Adv. Math. 73, Cambridge University Press, Cambridge, 2001."},{"key":"atypb6","unstructured":"E. Biglieri and L. Gyo\u0308rfi,\n                      Multiple Access Channels: Theory and Practice\n                      , NATO Security Through Sci. Ser. D Inform. Commun. Security, IOS Press, Amsterdam, 2007."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-08-09595-6"},{"key":"atypb8","first-page":"16","author":"Bouvel M.","year":"2005","journal-title":"Berlin"},{"key":"atypb9","first-page":"97","author":"Bshouty N. H.","year":"2009","journal-title":"Berlin"},{"key":"atypb10","unstructured":"N. H. Bshouty and H. Mazzawi,\n                      On parity check $(0, 1)$-matrix over $Z_p$\n                      , Technical report TR09-067, Electronic Colloquium on Computational Complexity, 2009."},{"key":"atypb11","unstructured":"C. Christen and A. Fibonaccian,\n                      Algorithm for the Detection of Two Elements\n                      , Technical report 341, Universite\u0301 de Montre\u0301al, De\u0301partement d'informatique et de recherche ope\u0301rationnelle, 1980."},{"key":"atypb12","first-page":"749","author":"Choi S. S.","year":"2008","journal-title":"New York"},{"key":"atypb13","first-page":"163","author":"Djackov A. G.","year":"1975","journal-title":"Amsterdam"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"D. Du and F. K. Hwang,\n                      Combinatorial Group Testing and its Application\n                      , Ser. Appl. Math. 3, World Science, Singapore, 1993.","DOI":"10.1142\/1936"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1945-08454-7"},{"key":"atypb16","first-page":"194","author":"Grebinski V.","year":"1998","journal-title":"Berlin"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00070-5"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010033"},{"key":"atypb19","first-page":"30","author":"Indyk P.","year":"2008","journal-title":"Philadelpha"},{"key":"atypb20","first-page":"199","author":"Indyk P.","year":"2008","journal-title":"NJ"},{"key":"atypb21","first-page":"7","volume":"2","author":"Komlo\u0301s J.","year":"1967","journal-title":"Studia. Sci. Math. Hungar."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1965-034-2"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1971-092-9"},{"key":"atypb24","first-page":"407","author":"Lindstro\u0308m B.","year":"1975","journal-title":"Amsterdam"},{"key":"atypb25","first-page":"277","volume":"12","author":"Littlewood J. E.","year":"1943","journal-title":"III. Mat. Sb."},{"key":"atypb26","unstructured":"P. Long,\n                      private communication\n                      , 2009."},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"atypb28","first-page":"285","author":"Reyzin L.","year":"2007","journal-title":"Berlin"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01171114"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120881129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:37:24Z","timestamp":1787319444000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120881129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/120881129"],"URL":"https:\/\/doi.org\/10.1137\/120881129","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}