tag:blogger.com,1999:blog-3722233.post4583902398250806221..comments2024-06-24T15:24:01.378-05:00Comments on Computational Complexity: Finding an element with nonadaptive questionsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-14965649228564620412021-11-23T08:05:49.915-06:002021-11-23T08:05:49.915-06:00For this specific question I think there is anothe...For this specific question I think there is another way to isolate: You consider {1,...,N} to be the set of vectors over {0,1}^k (where k=log N), take uniformly random linear equations and ask "Does S contain a solution of l1,...,li". With constant probability, if i is the smallest iteration for which you get "No", you will have a single member of S that solves l1,...,li-1.Eldarnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64130492901945409282021-11-22T16:56:35.414-06:002021-11-22T16:56:35.414-06:00The interplay resulting from what the questioner i...The interplay resulting from what the questioner is allowed to ask can also be interesting. For example, if the goal is to guess a password or the hash of the password to enter a system, then powerful questions targeting single or a small group of bits are not available. Interestingly, in that cryptographic setting, the *expected* number of questions required even for the optimal sequence of atomic queries of X to discover an unknown random quantity X is related to the Renyi entropy, specifically the Renyi entropy of order 1/2, instead of the Shannon entropy where arbitrary queries can be made. See<br /><br />https://crypto.stackexchange.com/questions/40286/entropy-requirements-for-encryption/40292#40292Kodluhttps://www.blogger.com/profile/12418167413500125327noreply@blogger.com