One of the exciting capabilities of recent language models for dialog is their ability to independently search for relevant information to ground a given dialog response.However, obtaining training data to teach models how to issue search queries is time and resource consuming.In this work, we propose q2d: an automatic data generation pipeline that generates information-seeking dialogs from questions.We prompt a large language model (PaLM) to create conversational versions of question answering datasets, and use it to improve query generation models that communicate with external search APIs to ground dialog responses.Unlike previous approaches which relied on human written dialogs with search queries, our method allows to automatically generate querybased grounded dialogs with better control and scale.Our experiments demonstrate that: (1) For query generation on the QReCC dataset, models trained on our synthetically-generated data achieve 90%-97% of the performance of models trained on the human-generated data;(2) We can successfully generate data for training dialog models in new domains without any existing dialog data as demonstrated on the multi-hop MuSiQue and Bamboogle QA datasets.(3) We perform a thorough analysis of the generated dialogs showing that humans find them of high quality and struggle to distinguish them from human-written dialogs. 1 * Work done during an internship at Google Research. 1 We publicly release all prompts and will release all generated datasets.

In this paper, we analyze the following communication complexity problem. It is a variant of the set-disjointness problem, denoted PDISJlog N, where each of Alice and Bob gets as an input a subset of [N] of size at most log N, with the promise that the intersection of the two subsets is of size at most 1. We provide an almost tight lower bound of ¿¿(log2N) on the deterministic communication complexity of the problem. The main motivation for studying this problem comes from the so-called "clique vs. independent-set" problem, introduced by Yannakakis (1988). Proving an ¿(log2N) lower bound on the communication complexity of the clique vs. independent-set problem for all graphs is a long standing open problem with various implications. Proving such a lower bound for random graphs is also open. In such a graph, both the cliques and the independent sets are of size O(log N) (and obviously their intersection is of size at most 1). Hence, our ¿¿(log2N) lower bound for PDISJlog Ncan be viewed as a first step in this direction. Interestingly, we note that standard lower bound techniques cannot yield the desired lower bound. Hence, we develop a novel adversary argument that may find other applications.

We consider the following question: given a two-argument boolean function f, represented as an N x N binary matrix, how hard is it to determine the (deterministic) communication complexity of f?

We consider the following problem. Suppose that a big amount of data is distributed among several parties, so that each party misses only few pieces of data. The parties wish to perform some global computation on the data while minimizing the communication between them. This situation is common in many real-life scenarios. A naive solution to this problem is to first perform a synchronization step, letting one party learn all pieces of data, and then let this party perform the required computation locally. We study the question of obtaining better solutions to the problem, focusing mainly on the case of computing low-degree polynomials via non-interactive protocols. We present interesting connections between this problem and the well studied cryptographic problem of secret sharing. We use this connection to obtain nontrivial upper bounds and lower bounds using results and techniques from the domain of secret sharing. The relation with open problems from the area of secret sharing also provides evidence for the difficulty of resolving some of the questions we leave open.

Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms which do not leak unnecessary information. Specifically, we are interested in private approximation algorithms -- efficient algorithms whose output does not leak information not implied by the optimal solutions to the search problems. Privacy requirements add constraints on the approximation algorithms; in particular, known approximation algorithms usually leak a lot of information.For functions, [Feigenbaum et al., ICALP 2001] presented a natural requirement that a private algorithm should not leak information not implied by the original function. Generalizing this requirement to search problems is not straightforward as an input may have many different outputs. We present a new definition that captures a minimal privacy requirement from such algorithms -- applied to an input instance, it should not leak any information that is not implied by its collection of exact solutions. Although our privacy requirement seems minimal, we show that for well studied problems, as vertex cover and 3SAT, private approximation algorithms are unlikely to exist even for poor approximation ratios. Similar to [Halevi et al., STOC 2001], we define a relaxed notion of approximation algorithms that leak (little) information, and demonstrate the applicability of this notion by showing near optimal approximation algorithms for 3SAT that leak little information.

Weighted threshold secret sharing was introduced by Shamir in his seminal work on secret sharing. In such settings, there is a set of users where each user is assigned a positive weight. A dealer wishes to distribute a secret among those users so that a subset of users may reconstruct the secret if and only if the sum of weights of its users exceeds a certain threshold. On one hand, there are nontrivial weighted threshold access structures that have an ideal scheme—a scheme in which the size of the domain of shares of each user is the same as the size of the domain of possible secrets (this is the smallest possible size for the domain of shares). On the other hand, other weighted threshold access structures are not ideal. In this work we characterize all weighted threshold access structures that are ideal. We show that a weighted threshold access structure is ideal if and only if it is a hierarchical threshold access structure (as introduced by Simmons), or a tripartite access structure (these structures generalize the concept of bipartite access structures due to Padró and Sáez), or a composition of two ideal weighted threshold access structures that are defined on smaller sets of users. We further show that in all those cases the weighted threshold access structure may be realized by a linear ideal secret sharing scheme. The proof of our characterization relies heavily on the strong connection between ideal secret sharing schemes and matroids, as proved by Brickell and Davenport.

Weighted threshold functions with positive weights are a natural generalization of unweighted threshold functions. These functions are clearly monotone. However, the naive way of computing them is adding the weights of the satisfied variables and checking if the sum is greater than the threshold; this algorithm is inherently non-monotone since addition is a non-monotone function. In this work we bypass this addition step and construct a polynomial size logarithmic depth unbounded fan-in monotone circuit for every weighted threshold function, i.e., we show that weighted threshold functions are in mAC. (To the best of our knowledge, prior to our work no polynomial monotone circuits were known for weighted threshold functions). Our monotone circuits are applicable for the cryptographic tool of secret sharing schemes. Using general results for compiling monotone circuits (Yao, 1989) and monotone formulae (Benaloh and Leichter, 1990) into secret sharing schemes, we get secret sharing schemes for every weighted threshold access structure. Specifically, we get: (1) information-theoretic secret sharing schemes where the size of each share is quasi-polynomial in the number of users, and (2) computational secret sharing schemes where the size of each share is polynomial in the number of users.

Monotone span programs represent a linear-algebraic model of computation. They are equivalent to linear secret sharing schemes and have various applications in cryptography and complexity. A fundamental question regarding them is how the choice of the field in which the algebraic operations are performed affects the power of the span program. In this paper we prove that the power of monotone span programs over finite fields of different characteristics is incomparable; we show a superpolynomial separation between any two fields with different characteristics, solving an open problem of Pudlák and Sgall [Algebraic models of computation and interpolation for algebraic proof systems, in Proof Complexity and Feasible Arithmetic, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 39, P. W. Beame and S. Buss, eds., AMS, Providence, RI, 1998, pp. 279--296]. Using this result we prove a superpolynomial lower bound for monotone span programs for a function in uniform-${\cal N}C^2$ (and therefore in ${\cal P}$), solving an open problem of Babai, Gál, and Wigderson [Combinatorica, 19 (1999), pp. 301--319]. (All previous superpolynomial lower bounds for monotone span programs were for functions not known to be in ${\cal P}$.) Finally, we show that quasi-linear secret sharing schemes, a generalization of linear secret sharing schemes introduced in Beimel and Ishai [On the power of nonlinear secret-sharing, in Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 188--202], are stronger than linear secret sharing schemes. In particular, this proves, without any assumptions, that nonlinear secret sharing schemes are more efficient than linear secret sharing schemes.

Monotone span programs are a linear-algebraic model of computation. They are equivalent to linear secret sharing schemes and have various applications in cryptography and complexity. A fundamental question is how the choice of the field in which the algebraic operations are performed effects the power of the span program. In this paper we prove that the power of monotone span programs over finite fields of different characteristics is incomparable; we show a super-polynomial separation between any two fields with different characteristics, answering an open problem of Pudlak and Sgall (1998). Using this result we prove a super-polynomial lower bound for monotone span programs for a function in uniform - /spl Nscr/;/spl Cscr/;/sup 2/ (and therefore in /spl Pscr/;), answering an open problem of Babai, Wigderson, and Gal (1999). Finally, we show that quasi-linear schemes, a generalization of linear secret sharing schemes introduced in Beimel and Ishai (2001), are stronger than linear secret sharing schemes. In particular, this proves, without any assumptions, that non-linear secret sharing schemes are more efficient than linear secret sharing schemes.