Zoltan Firedi 1,2, Nathan Linial3
1Mathematical Institute of the Hungarian Academy of Sciences, P,0, B. 127, Budapest 1364 Hungary
2Department of Mathematics University of Illinois Urbana, IL 61801, USA
3Hebrew University of Jerusalem
Abstract:

Given \(n\) real numbers whose sum is zero, find one of the numbers that is non-negative. In the model under consideration, an algorithm is allowed to compute \(p\) linear forms in each time step until it knows an answer. We prove that exactly \(\lceil{\log n}/{\log(p+1)} \rceil\) time steps are required. Some connections with parallel group-testing problems are pointed out.

E-mail Alert

Add your e-mail address to receive upcoming issues of Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC).

Special Issues

The Combinatorial Press Editorial Office routinely extends invitations to scholars for the guest editing of Special Issues, focusing on topics of interest to the scientific community. We actively encourage proposals from our readers and authors, directly submitted to us, encompassing subjects within their respective fields of expertise. The Editorial Team, in conjunction with the Editor-in-Chief, will supervise the appointment of Guest Editors and scrutinize Special Issue proposals to ensure content relevance and appropriateness for the journal. To propose a Special Issue, kindly complete all required information for submission;