waashk/dblp huggingface dataset:
universal semantic communication i. is it possible for two intelligent beings to communicate meaningfully, without any common language or background? this question has interest on its own, but is especially relevant in the context of modern computational infrastructures where an increase in the diversity of computers is making the task of inter-computer interaction increasingly burdensome. computers spend a substantial amount of time updating their software to increase their knowledge of other computing devices. in turn, for any pair of communicating devices, one has to design software that enables the two to talk to each other. is it possible instead to let the two computing entities use their intelligence (universality as computers) to learn each others' behavior and attain a common understanding? what is 'common understanding?' we explore this question in this paper. to formalize this problem, we suggest that one should study the 'goal of communication:' why are the two entities interacting with each other, and what do they hope to gain by it? we propose that by considering this question explicitly, one can make progress on the question of universal communication. we start by considering a computational setting for the problem where the goal of one of the interacting players is to gain some computational wisdom from the other player. we show that if the second player is "sufficiently" helpful and powerful, then the first player can gain significant computational power (deciding pspace complete languages). our work highlights some of the definitional issues underlying the task of formalizing universal communication, but also suggests some interesting phenomena and highlights potential tools that may be used for such communication.
on the constant-depth complexity of k-clique. we prove a lower bound of ω(nk/4) on the size of constant-depth circuits solving the k-clique problem on n-vertex graphs (for every constant k). this improves a lower bound of ω(nk/89d2) due to beame where d is the circuit depth. our lower bound has the advantage that it does not depend on the constant d in the exponent of n, thus breaking the mold of the traditional size-depth tradeoff. our k-clique lower bound derives from a stronger result of independent interest. suppose fn :0,1n/2 → {0,1} is a sequence of functions computed by constant-depth circuits of size o(nt). let g be an erdos-renyi random graph with vertex set {1,...,n} and independent edge probabilities n-α where α ≤ 1/2t-1. let a be a uniform random k-element subset of {1,...,n} (where k is any constant independent of n) and let ka denote the clique supported on a. we prove that fn(g) = fn(g ∪ ka) asymptotically almost surely. these results resolve a long-standing open question in finite model theory (going back at least to immerman in 1982). the m-variable fragment of first-order logic, denoted by fom, consists of the first-order sentences which involve at most m variables. our results imply that the bounded variable hierarchy fo1 ⊂ fo2 ⊂ ... ⊂ fom ⊂ ... is strict in terms of expressive power on finite ordered graphs. it was previously unknown that fo3 is less expressive than full first-order logic on finite ordered graphs.
hardness amplification proofs require majority. hardness amplification is the fundamental task of converting a δ-hard function f : (0, 1)n -> (0, 1) into a (1/2-ε)-hard function amp(f), where f is γ-hard if small circuits fail to compute f on at least a γ fraction of the inputs. typically, ε,δ are small (and δ=2-k captures the case where f is worst-case hard). achieving ε = 1/nω(1) is a prerequisite for cryptography and most pseudorandom-generator constructions. in this paper we study the complexity of black-box proofs of hardness amplification. a class of circuits cal d proves a hardness amplification result if for any function h that agrees with amp(f) on a 1/2+e fraction of the inputs there exists an oracle circuit d ∈ d such that dh agrees with f on a 1-δ fraction of the inputs. we focus on the case where every d ∈ d makes non-adaptive queries to h. this setting captures most hardness amplification techniques. we prove two main results: the circuits in d "can be used" to compute the majority function on 1e bits. in particular, these circuits have large depth when ε ≤ 1/ poly log n. the circuits in d must make ω log(1/δ)/e2 oracle queries. both our bounds on the depth and on the number of queries are tight up to constant factors. our results explain why hardness amplification techniques have failed to transform known lower bounds against constant-depth circuit classes into strong average-case lower bounds. when coupled with the celebrated "natural proofs" result by razborov and rudich (j. css '97) and the pseudorandom functions by naor and reingold (j. acm '04), our results show that standard techniques for hardness amplification can only be applied to those circuit classes for which standard techniques cannot prove circuit lower bounds. our results reveal a contrast between yao's xor lemma (amp(f) := f(x1) ⊕ ... ⊕ f(xt) ∈ zo) and the direct-product lemma (amp(f) := f(x1) o ... o f(xt) ∈ zot; here amp(f) is non-boolean). our results (1) and (2) apply to yao's xor lemma, whereas known proofs of the direct-product lemma violate both (1) and (2). one of our contributions is a new technique to handle "non-uniform" reductions, i.e. the case when d contains many circuits.
robust lower bounds for communication and stream computation. we study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. this naturally extends previously studied variable partition models such as the best-case and worst-case partition models [32,29]. we aim to understand whether the hardness of a communication problem holds for almost every allocation of the input, as opposed to holding for perhaps just a few atypical partitions. a key application is to the heavily studied data stream model. there is a strong connection between our communication lower bounds and lower bounds in the data stream model that are "robust" to the ordering of the data. that is, we prove lower bounds for when the order of the items in the stream is chosen not adversarially but rather uniformly (or near-uniformly) from the set of all permuations. this random-order data stream model has attracted recent interest, since lower bounds here give stronger evidence for the inherent hardness of streaming problems. our results include the first random-partition communication lower bounds for problems including multi-party set disjointness and gap-hamming-distance. both are tight. we also extend and improve previous results [19,7] for a form of pointer jumping that is relevant to the problem of selection (in particular, median finding). collectively, these results yield lower bounds for a variety of problems in the random-order data stream model, including estimating the number of distinct elements, approximating frequency moments, and quantile estimation.
unconditional pseudorandom generators for low degree polynomials. we give an explicit construction of pseudorandom generators against low degree polynomials over finite fields. we show that the sum of 2d small-biased generators with error ε2o(d) is a pseudorandom generator against degree d polynomials with error ε. this gives a generator with seed length 2o(d) log(n/ε). our construction follows the recent breakthrough result of bogadnov and viola. their work shows that the sum of d small-biased generators is a pseudo-random generator against degree d polynomials, assuming the inverse gowers conjecture. however, this conjecture is only proven for d=2,3. the main advantage of our work is that it does not rely on any unproven conjectures.
fast polynomial factorization and modular composition in small characteristic. we obtain randomized algorithms for factoring degree n univariate polynomials over f_q that use o(n1.5 + o(1) + n1 + o(1)log q) field operations, when the characteristic is at most no(1). when log q the improvements come from a new algorithm for modular composition of degree n univariate polynomials, which is the asymptotic bottleneck in fast algorithms for factoring polynomials over finite fields. the best previous algorithms for modular composition use o(n(omega + 1)/2) field operations, where omega is the exponent of matrix multiplication (brent & kung (1978)), with a slight improvement in the exponent achieved by employing fast rectangular matrix multiplication (huang & pan (1997)). we show that modular composition and multipoint evaluation of multivariate polynomials are essentially equivalent in the sense that an algorithm for one achieving exponent α implies an algorithm for the other with exponent α + o(1), and vice versa. we then give a new algorithm that requires o(n1 + o(1)) field operations when the characteristic is at most no(1), which is optimal up to lower order terms. our algorithms do not rely on fast matrix multiplication, in contrast to all previous subquadratic algorithms for these problems. the main operations are fast univariate polynomial arithmetic, multipoint evaluation, and interpolation, and consequently the algorithms could be feasible in practice.
pricing combinatorial markets for tournaments. in a prediction market, agents trade assets whose value is tied to a future event, for example the outcome of the next presidential election. asset prices determine a probability distribution over the set of possible outcomes. typically, the outcome space is small, allowing agents to directly trade in each outcome, and allowing a market maker to explicitly update asset prices. combinatorial markets, in contrast, work to estimate a full joint distribution of dependent observations, in which case the outcome space grows exponentially. in this paper, we consider the problem of pricing combinatorial markets for single-elimination tournaments. with $n$ competing teams, the outcome space is of size 2n-1. we show that the general pricing problem for tournaments is p-hard. we derive a polynomial-time algorithm for a restricted betting language based on a bayesian network representation of the probability distribution. the language is fairly natural in the context of tournaments, allowing for example bets of the form "team i wins game k". we believe that our betting language is the first for combinatorial market makers that is both useful and tractable. we briefly discuss a heuristic approximation technique for the general case.
sketching in adversarial environments. we formalize a realistic model for computations over massive data sets. the model, referred to as the {\em adversarial sketch model}, unifies the well-studied sketch and data stream models together with a cryptographic flavor that considers the execution of protocols in "hostile environments", and provides a framework for studying the complexity of many tasks involving massive data sets. the adversarial sketch model consists of several participating parties: honest parties, whose goal is to compute a pre-determined function of their inputs, and an adversarial party. computation in this model proceeds in two phases. in the first phase, the adversarial party chooses the inputs of the honest parties. these inputs are sets of elements taken from a large universe, and provided to the honest parties in an on-line manner in the form of a sequence of insert and delete operations. once an operation from the sequence has been processed it is discarded and cannot be retrieved unless explicitly stored. during this phase the honest parties are not allowed to communicate. moreover, they do not share any secret information and any public information they share is known to the adversary in advance. in the second phase, the honest parties engage in a protocol in order to compute a pre-determined function of their inputs. in this paper we settle the complexity (up to logarithmic factors) of two fundamental problems in this model: testing whether two massive data sets are equal, and approximating the size of their symmetric difference. we construct explicit and efficient protocols with sublinear sketches of essentially optimal size, poly-logarithmic update time during the first phase, and poly-logarithmic communication and computation during the second phase. our main technical contribution is an explicit and deterministic encoding scheme that enjoys two seemingly conflicting properties: incrementality and high distance, which may be of independent interest.
graph and map isomorphism and all polyhedral embeddings in linear time. for every surface s (orientable or non-orientable), we give a linear time algorithm to test the graph isomorphism of two graphs, one of which admits an embedding of face-width at least 3 into s. this improves a previously known algorithm whose time complexity is no(g), where g is the genus of s. this is the first algorithm for which the degree of polynomial in the time complexity does not depend on g. the above result is based on two linear time algorithms, each of which solves a problem that is of independent interest. the first of these problems is the following one. let s be a fixed surface. given a graph g and an integer k ≥ 3, we want to find an embedding of g in s of face-width at least k, or conclude that such an embedding does not exist. it is known that this problem is np-hard when the surface is not fixed. moreover, if there is an embedding, the algorithm can give all embeddings of face-width at least k, up to whitney equivalence. here, the face-width of an embedded graph g is the minimum number of points of g in which some non-contractible closed curve in the surface intersects the graph. in the proof of the above algorithm, we give a simpler proof and a better bound for the theorem by mohar and robertson concerning the number of polyhedral embeddings of 3-connected graphs. the second ingredient is a linear time algorithm for map isomorphism and whitney equivalence. this part generalizes the seminal result of hopcroft and wong that graph isomorphism can be decided in linear time for planar graphs.
interdomain routing and games. we present a game-theoretic model that captures many of the intricacies of interdomain routing in today's internet. in this model, the strategic agents are source nodes located on a network, who aim to send traffic to a unique destination node. the interaction between the agents is dynamic and complex -- asynchronous, sequential, and based on partial information. best-reply dynamics in this model capture crucial aspects of the interdomain routing protocol de facto, namely the border gateway protocol (bgp). we study complexity and incentive-related issues in this model. our main results are showing that in realistic and well-studied settings, bgp is incentive-compatible. i.e., not only does myopic behaviour of all players converge to a "stable" routing outcome, but no player has motivation to unilaterally deviate from the protocol. moreover, we show that even coalitions of players of any size cannot improve their routing outcomes by collaborating. unlike the vast majority of works in mechanism design, our results do not require any monetary transfers (to or by the agents).
optimal approximation for the submodular welfare problem in the value oracle model. in the submodular welfare problem, m items are to be distributed among n players with utility functions wi: 2[m] → r+. the utility functions are assumed to be monotone and submodular. assuming that player i receives a set of items si, we wish to maximize the total utility ∑i=1n wi(si). in this paper, we work in the value oracle model where the only access to the utility functions is through a black box returning wi(s) for a given set s. submodular welfare is in fact a special case of the more general problem of submodular maximization subject to a matroid constraint: max{f(s): s ∈ i}, where f is monotone submodular and i is the collection of independent sets in some matroid. for both problems, a greedy algorithm is known to yield a 1/2-approximation [21, 16]. in special cases where the matroid is uniform (i = s: |s| ≤ k) [20] or the submodular function is of a special type [4, 2], a (1-1/e)-approximation has been achieved and this is optimal for these problems in the value oracle model [22, 6, 15]. a (1-1/e)-approximation for the general submodular welfare problem has been known only in a stronger demand oracle model [4], where in fact 1-1/e can be improved [9]. in this paper, we develop a randomized continuous greedy algorithm which achieves a (1-1/e)-approximation for the submodular welfare problem in the value oracle model. we also show that the special case of n equal players is approximation resistant, in the sense that the optimal (1-1/e)-approximation is achieved by a uniformly random solution. using the pipage rounding technique [1, 2], we obtain a (1-1/e)-approximation for submodular maximization subject to any matroid constraint. the continuous greedy algorithm has a potential of wider applicability, which we demonstrate on the examples of the generalized assignment problem and the adwords assignment problem.
delegating computation: interactive proofs for muggles. in this work we study interactive proofs for tractable languages. the (honest) prover should be efficient and run in polynomial time, or in other words a "muggle". the verifier should be super-efficient and run in nearly-linear time. these proof systems can be used for delegating computation: a server can run a computation for a client and interactively prove the correctness of the result. the client can verify the result's correctness in nearly-linear time (instead of running the entire computation itself). previously, related questions were considered in the holographic proof setting by babai, fortnow, levin and szegedy, in the argument setting under computational assumptions by kilian, and in the random oracle model by micali. our focus, however, is on the original interactive proof model where no assumptions are made on the computational power or adaptiveness of dishonest provers. our main technical theorem gives a public coin interactive proof for any language computable by a log-space uniform boolean circuit with depth d and input length n. the verifier runs in time (n+d) • polylog(n) and space o(log(n)), the communication complexity is d • polylog(n), and the prover runs in time poly(n). in particular, for languages computable by log-space uniform nc (circuits of polylog(n) depth), the prover is efficient, the verifier runs in time n • polylog(n) and space o(log(n)), and the communication complexity is polylog(n). using this theorem we make progress on several questions: we show how to construct short (polylog size) computationally sound non-interactive certificates of correctness for any log-space uniform nc computation, in the public-key model. the certificates can be verified in quasi-linear time and are for a designated verifier: each certificate is tailored to the verifier's public key. this result uses a recent transformation of kalai and raz from public-coin interactive proofs to one-round arguments. the soundness of the certificates is based on the existence of a pir scheme with polylog communication. interactive proofs with public-coin, log-space, poly-time verifiers for all of p. this settles an open question regarding the expressive power of proof systems with such verifiers. zero-knowledge interactive proofs with communication complexity that is quasi-linear in the witness, length for any np language verifiable in nc, based on the existence of one-way functions. probabilistically checkable arguments (a model due to kalai and raz) of size polynomial in the witness length (rather than the instance length) for any np language verifiable in nc, under computational assumptions.
fast integer multiplication using modular arithmetic. we give an o(n • log n • 2o(log*n)) algorithm for multiplying two n-bit integers that improves the o(n • log n • log log n) algorithm by schönhage-strassen. both these algorithms use modular arithmetic. recently, fürer gave an o(n • log n • 2o(log*n)) algorithm which however uses arithmetic over complex numbers as opposed to modular arithmetic. in this paper, we use multivariate polynomial multiplication along with ideas from fürer's algorithm to achieve this improvement in the modular setting. our algorithm can also be viewed as a p-adic version of fürer's algorithm. thus, we show that the two seemingly different approaches to integer multiplication, modular and complex arithmetic, are similar.
algebrization: a new barrier in complexity theory. any proof of p!=np will have to overcome two barriers: relativization and natural proofs. yet over the last decade, we have seen circuit lower bounds (for example, that pp does not have linear-size circuits) that overcome both barriers simultaneously. so the question arises of whether there is a third barrier to progress on the central questions in complexity theory. in this paper we present such a barrier, which we call algebraic relativization or algebrization. the idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle a, but also to a low-degree extension of a over a finite field or ring. we systematically go through basic results and open problems in complexity theory to delineate the power of the new algebrization barrier. first, we show that all known non-relativizing results based on arithmetization -- both inclusions such as ip=pspace and mip=nexp, and separations such as maexp not in p/poly -- do indeed algebrize. second, we show that almost all of the major open problems -- including p versus np, p versus rp, and nexp versus p/poly -- will require non-algebrizing techniques. in some cases algebrization seems to explain exactly why progress stopped where it did: for example, why we have superlinear circuit lower bounds for promisema but not for np. our second set of results follows from lower bounds in a new model of algebraic query complexity, which we introduce in this paper and which is interesting in its own right. some of our lower bounds use direct combinatorial and algebraic arguments, while others stem from a surprising connection between our model and communication complexity. using this connection, we are also able to give an ma-protocol for the inner product function with o(sqrt(n) log n) communication (essentially matching a lower bound of klauck).