{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T05:27:50Z","timestamp":1740461270334,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_21","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"221-232","source":"Crossref","is-referenced-by-count":3,"title":["Toward a Deterministic Polynomial Time Algorithm with Optimal Additive Query Complexity"],"prefix":"10.1007","author":[{"given":"Nader H.","family":"Bshouty","sequence":"first","affiliation":[]},{"given":"Hanna","family":"Mazzawi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","volume-title":"Combinatorial Search","author":"M. Aigner","year":"1988","unstructured":"Aigner, M.: Combinatorial Search. John Wiley and Sons, Chichester (1988)"},{"issue":"4","key":"21_CR2","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S0895480103431071","volume":"18","author":"N. Alon","year":"2005","unstructured":"Alon, N., Asodi, V.: Learning a Hidden Subgraph. SIAM J. Discrete Math\u00a018(4), 697\u2013712 (2005)","journal-title":"SIAM J. Discrete Math"},{"issue":"2","key":"21_CR3","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1137\/S0097539702420139","volume":"33","author":"N. Alon","year":"2004","unstructured":"Alon, N., Beigel, R., Kasif, S., Rudich, S., Sudakov, B.: Learning a Hidden Matching. SIAM J. Comput.\u00a033(2), 487\u2013501 (2004)","journal-title":"SIAM J. Comput."},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D., Chen, J.: Learning a Hidden Graph Using O(logn) Queries per Edge. In: Conference on Learning Theory, pp. 210\u2013223 (2004)","DOI":"10.1007\/978-3-540-27819-1_15"},{"key":"21_CR5","first-page":"2215","volume":"7","author":"D. Angluin","year":"2006","unstructured":"Angluin, D., Chen, J.: Learning a Hidden Hypergraph. Journal of Machine Learning Research\u00a07, 2215\u20132236 (2006)","journal-title":"Journal of Machine Learning Research"},{"key":"21_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/11604686_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Bouvel","year":"2005","unstructured":"Bouvel, M., Grebinski, V., Kucherov, G.: Combinatorial Search on Graphs Motivated by Bioinformatics Applications: A Brief Survey. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 16\u201327. Springer, Heidelberg (2005)"},{"key":"21_CR7","unstructured":"Bshouty, N.H.: Optimal Algorithms for the Coin Weighing Problem with a Spring Scale. In: Conference on Learning Theory (2009)"},{"key":"21_CR8","series-title":"LNAI","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-642-04414-4_12","volume-title":"Algorithmic Learning Theory","author":"N.H. Bshouty","year":"2009","unstructured":"Bshouty, N.H., Mazzawi, H.: Reconstructing Weighted Graphs with Minimal Query Complexity. In: Gavald\u00e0, R., Lugosi, G., Zeugmann, T., Zilles, S. (eds.) ALT 2009. LNCS (LNAI), vol.\u00a05809, pp. 97\u2013109. Springer, Heidelberg (2009)"},{"key":"21_CR9","unstructured":"Bshouty, N.H., Mazzawi, H.: On Parity Check (0,1)-Matrix over \u2124 p . TR09-067. In: ECCC (2009)"},{"key":"21_CR10","doi-asserted-by":"crossref","first-page":"94","DOI":"10.4153\/CJM-1964-009-4","volume":"16","author":"D. Cantor","year":"1962","unstructured":"Cantor, D.: Determining a set from the cardinalities of its intersections with other sets. Canadian Journal of Mathematics\u00a016, 94\u201397 (1962)","journal-title":"Canadian Journal of Mathematics"},{"key":"21_CR11","doi-asserted-by":"crossref","first-page":"42","DOI":"10.4153\/CJM-1966-007-2","volume":"18","author":"D. Cantor","year":"1966","unstructured":"Cantor, D., Mills, W.: Determining a Subset from Certain Combinatorial Properties. Canad. J. Math.\u00a018, 42\u201348 (1966)","journal-title":"Canad. J. Math."},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Choi, S., Han Kim, J.: Optimal Query Complexity Bounds for Finding Graphs. In: STOC, pp. 749\u2013758 (2008)","DOI":"10.1145\/1374376.1374484"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Du, D., Hwang, F.K.: Combinatorial group testing and its application. Series on applied mathematics, vol.\u00a03. World Science (1993)","DOI":"10.1142\/1936"},{"key":"21_CR14","first-page":"241","volume":"8","author":"Erd\u00f6s","year":"1963","unstructured":"Erd\u00f6s, R\u00e9nyi, A.: On two problems of information theory. Publ. Math. Inst. Hung. Acad. Sci.\u00a08, 241\u2013254 (1963)","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"issue":"1","key":"21_CR15","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/s004530010033","volume":"28","author":"V. Grebinski","year":"2000","unstructured":"Grebinski, V., Kucherov, G.: Optimal Reconstruction of Graphs Under the Additive Model. Algorithmica\u00a028(1), 104\u2013124 (2000)","journal-title":"Algorithmica"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0166-218X(98)00070-5","volume":"88","author":"V. Grebiniski","year":"1998","unstructured":"Grebiniski, V., Kucherov, G.: Reconstructing a hamiltonian cycle by querying the graph: Application to DNA physical mapping. Discrete Applied Mathematics\u00a088, 147\u2013165 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"21_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-68535-9_23","volume-title":"Computing and Combinatorics","author":"V. Grebinski","year":"1998","unstructured":"Grebinski, V.: On the Power of Additive Combinatorial Search Model. In: Hsu, W.-L., Kao, M.-Y. (eds.) COCOON 1998. LNCS, vol.\u00a01449, pp. 194\u2013203. Springer, Heidelberg (1998)"},{"key":"21_CR18","doi-asserted-by":"crossref","first-page":"477","DOI":"10.4153\/CMB-1965-034-2","volume":"8","author":"B. Lindstr\u00f6m","year":"1965","unstructured":"Lindstr\u00f6m, B.: On a combinatorial problem in number theory. Canad. Math. Bull.\u00a08, 477\u2013490 (1965)","journal-title":"Canad. Math. Bull."},{"key":"21_CR19","first-page":"353","volume":"1","author":"B. Lindstr\u00f6m","year":"1966","unstructured":"Lindstr\u00f6m, B.: On a combinatorial detection problem II. Studia Scientiarum Mathematicarum Hungarica\u00a01, 353\u2013361 (1966)","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"issue":"4","key":"21_CR20","doi-asserted-by":"crossref","first-page":"513","DOI":"10.4153\/CMB-1971-092-9","volume":"14","author":"B. Lindstr\u00f6m","year":"1971","unstructured":"Lindstr\u00f6m, B.: On M\u00f6bius functions and a problem in combinatorial number theory. Canad. Math. Bull.\u00a014(4), 513\u2013516 (1971)","journal-title":"Canad. Math. Bull."},{"key":"21_CR21","first-page":"407","volume-title":"A Survey of Statistical Designs and Linear Models","author":"B. Lindstr\u00f6m","year":"1975","unstructured":"Lindstr\u00f6m, B.: Determining subsets by unramified experiments. In: Srivastava, J.N. (ed.) A Survey of Statistical Designs and Linear Models, pp. 407\u2013418. North Holland, Amsterdam (1975)"},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: Combinatorics and Kolmogorov Complexity. In: Structure in Complexity Theory Conference, pp. 154\u2013163 (1991)","DOI":"10.1109\/SCT.1991.160256"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Mazzawi, H.: Optimally Reconstructing Weighted Graphs Using Queries. In: Symposium on Discrete Algorithms, pp. 608\u2013615 (2010)","DOI":"10.1137\/1.9781611973075.51"},{"key":"21_CR24","first-page":"283","volume-title":"Combinatorial Structure and their applications","author":"L. Moser","year":"1970","unstructured":"Moser, L.: The second moment method in combinatorial analysis. In: Combinatorial Structure and their applications, pp. 283\u2013384. Gordon and Breach, New York (1970)"},{"issue":"1","key":"21_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0097-3165(77)90083-8","volume":"23","author":"N. Pippenger","year":"1977","unstructured":"Pippenger, N.: An Informtation Theoretic Method in Combinatorial Theory. J. Comb. Theory, Ser. A\u00a023(1), 99\u2013104 (1977)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"2","key":"21_CR26","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1109\/TIT.1981.1056332","volume":"27","author":"N. Pippenger","year":"1981","unstructured":"Pippenger, N.: Bounds on the performance of protocols for a multiple-access broadcast channel. IEEE Transactions on Information Theory\u00a027(2), 145\u2013151 (1981)","journal-title":"IEEE Transactions on Information Theory"},{"key":"21_CR27","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/978-3-540-75225-7_24","volume-title":"Algorithmic Learning Theory","author":"L. Reyzin","year":"2007","unstructured":"Reyzin, L., Srivastava, N.: Learning and Verifying Graphs using Queries with a Focus on Edge Counting. In: Hutter, M., Servedio, R.A., Takimoto, E. (eds.) ALT 2007. LNCS (LNAI), vol.\u00a04754, pp. 277\u2013289. Springer, Heidelberg (2007)"},{"issue":"1","key":"21_CR28","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1109\/18.567769","volume":"43","author":"M. Ruszink\u00f3","year":"1997","unstructured":"Ruszink\u00f3, M., Vanroose, P.: How an Erd\u0151s-R\u00e9nyi-type search approach gives an explicit code construction of rate 1 for random access with multiplicity feedback. IEEE Transactions on Information Theory\u00a043(1), 368\u2013372 (1997)","journal-title":"IEEE Transactions on Information Theory"},{"key":"21_CR29","doi-asserted-by":"publisher","first-page":"1066","DOI":"10.2307\/2312835","volume":"70","author":"S. Soderberg","year":"1963","unstructured":"Soderberg, S., Shapiro, H.S.: A combinatory detection problem. American Mathematical Monthly\u00a070, 1066\u20131070 (1963)","journal-title":"American Mathematical Monthly"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T12:31:22Z","timestamp":1740400282000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}