Presented on October 2, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116E.
The critical slowdown picture of Glauber dynamics for the 2D Ising model is by now fairly well understood. For @math , the dynamics on an @math torus has @math via the work of Martinelli and Olivieri @cite_42 @cite_45 and Martinelli, Olivieri and Schonmann @cite_40 , showing that, in this regime, there is a uniform bound on the inverse gap (in fact under arbitrary boundary conditions; see [ .7] Martinelli97 ). That this dynamics has @math at any @math for some @math was shown by Chayes, Chayes and Schonmann @cite_18 , and thereafter with the sharp @math by Cesi @cite_27 . Finally, a polynomial upper bound on @math at @math was given in the aforementioned paper @cite_25 ; establishing the correct (believed to be universal and approximately @math ; cf. @cite_25 and its references) remains a challenging open problem.
@cite_18 @cite_42 @cite_27 @cite_40 @cite_45 @cite_25
2011373957 2030344865 2092260192 2004959470 2079416076
We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . Abstract Irregular sampling and “stable sampling” of band-limited functions have been studied by H.J. Landau [H.J. Landau, Necessary density conditions for sampling and interpolation of certain entire functions, Acta Math. 117 (1967) 37–52]. We prove that quasicrystals are sets of stable sampling. To cite this article: B. Matei, Y. Meyer, C. R. Acad. Sci. Paris, Ser. I 346 (2008). The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csiszar and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, @math , defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by @math , is an upper bound on @math . For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type @math condition, which is verifiable in polynomial time, guarantees that our lower bound on @math meets the @math upper bound. Thus, the PIN models satisfying our condition are @math -maximal, indicating that the upper bound @math holds with equality. This allows us to explicitly evaluate @math for such PIN models. We also give several examples of PIN models that satisfy our Type @math condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type @math condition implies that communication from all terminals (omnivocality) is needed for establishing an SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type @math condition is satisfied. However, for the source models with four or more terminals, counterexamples exist showing that the converse does not hold in general. Given a set of @math points in @math , how many dimensions are needed to represent all pair wise distances within a specific distortion? This dimension-distortion tradeoff question is well understood for the @math norm, where @math dimensions suffice to achieve @math distortion. In sharp contrast, there is a significant gap between upper and lower bounds for dimension reduction in @math . A recent result shows that distortion @math can be achieved with @math dimensions. On the other hand, the only lower bounds known are that distortion @math requires @math dimensions and that distortion @math requires @math dimensions. In this work, we show the first near linear lower bounds for dimension reduction in @math . In particular, we show that @math distortion requires at least @math dimensions. Our proofs are combinatorial, but inspired by linear programming. In fact, our techniques lead to a simple combinatorial argument that is equivalent to the LP based proof of Brinkman-Charikar for lower bounds on dimension reduction in @math . Scholars are increasingly citing electronic “web references” which are not preserved in libraries or full text archives. WebCite is a new standard for citing web references. To “webcite” a document involves archiving the cited Web page through www.webcitation.org and citing the WebCite permalink instead of (or in addition to) the unstable live Web page. This journal has amended its “instructions for authors” accordingly, asking authors to archive cited Web pages before submitting a manuscript. Almost 200 other journals are already using the system. We discuss the rationale for WebCite, its technology, and how scholars, editors, and publishers can benefit from the service. Citing scholars initiate an archiving process of all cited Web references, ideally before they submit a manuscript. Authors of online documents and websites which are expected to be cited by others can ensure that their work is permanently available by creating an archived copy using WebCite and providing the citation information including the WebCite link on their Web document(s). Editors should ask their authors to cache all cited Web addresses (Uniform Resource Locators, or URLs) “prospectively” before submitting their manuscripts to their journal. Editors and publishers should also instruct their copyeditors to cache cited Web material if the author has not done so already. Finally, WebCite can process publisher submitted “citing articles” (submitted for example as eXtensible Markup Language [XML] documents) to automatically archive all cited Web pages shortly before or on publication. Finally, WebCite can act as a focussed crawler, caching retrospectively references of already published articles. Copyright issues are addressed by honouring respective Internet standards (robot exclusion files, no-cache and no-archive tags). Long-term preservation is ensured by agreements with libraries and digital preservation organizations. The resulting WebCite Index may also have applications for research assessment exercises, being able to measure the impact of Web services and published Web documents through access and Web citation metrics. @PARASPLIT [J Med Internet Res 2005;7(5):e60] In a document network such as a citation network of scientific documents, web-logs, etc., the content produced by authors exhibits their interest in certain topics. In addition some authors influence other authors' interests. In this work, we propose to model the influence of cited authors along with the interests of citing authors. Moreover, we hypothesize that apart from the citations present in documents, the context surrounding the citation mention provides extra topical information about the cited authors. However, associating terms in the context to the cited authors remains an open problem. We propose novel document generation schemes that incorporate the context while simultaneously modeling the interests of citing authors and influence of the cited authors. Our experiments show significant improvements over baseline models for various evaluation criteria such as link prediction between document and cited author, and quantitatively explaining unseen text. A (tandem) duplication of length @math is an insertion of an exact copy of a substring of length @math next to its original position. This and related types of impairments are of relevance in modeling communication in the presence of synchronization errors, as well as in several information storage applications. We demonstrate that Levenshtein’s construction of binary codes correcting insertions of zeros is, with minor modifications, applicable also to channels with arbitrary alphabets and with duplication errors of arbitrary (but fixed) length @math . Furthermore, we derive bounds on the cardinality of optimal @math -ary codes correcting up to @math duplications of length @math and establish the following corollaries in the asymptotic regime of growing block length: 1) the presented family of codes is optimal for every @math , in the sense of the asymptotic scaling of code redundancy; 2) the upper bound, when specialized to @math , @math , improves upon Levenshtein’s bound for every @math ; and 3) the bounds coincide for @math , thus yielding the exact asymptotic behavior of the size of optimal single-duplication-correcting codes. We consider a switched network, a fairly general constrained queueing network model that has been used successfully to model the detailed packet-level dynamics in communication networks, such as input-queued switches and wireless networks. The main operational issue in this model is that of deciding which queues to serve, subject to certain constraints. In this paper, we study qualitative performance properties of the well known @math -weighted scheduling policies. The stability, in the sense of positive recurrence, of these policies has been well understood. We establish exponential upper bounds on the tail of the steady-state distribution of the backlog. Along the way, we prove finiteness of the expected steady-state backlog when @math , a property that was known only for @math . Finally, we analyze the excursions of the maximum backlog over a finite time horizon for @math . As a consequence, for @math , we establish the full state space collapse property. A citing sentence is one that appears in a scientific article and cites previous work. Citing sentences have been studied and used in many applications. For example, they have been used in scientific paper summarization, automatic survey generation, paraphrase identification, and citation function classification. Citing sentences that cite multiple papers are common in scientific writing. This observation should be taken into consideration when using citing sentences in applications. For instance, when a citing sentence is used in a summary of a scientific paper, only the fragments of the sentence that are relevant to the summarized paper should be included in the summary. In this paper, we present and compare three different approaches for identifying the fragments of a citing sentence that are related to a given target reference. Our methods are: word classification, sequence labeling, and segment classification. Our experiments show that segment classification achieves the best results. Abstract Documents in computer-readable form can be used to provide information about other documents, i.e. those they cite. To do this efficiently requires procedures for computer recognition of citing statements. This is not easy, especially for multi-sentence citing statements. Computer recognition procedures have been developed which are accurate to the following extent: 73 of the words in statements selected by computer procedures as being citing statements are words which are correctly attributable to the corresponding documents. The retrieval effectiveness of computer-recognized citing statements was tested in the following way. First, for eight retrieval requests in inorganiic chemistry, average recall by search of Chemical Abstracts Service indexing and Chemical Abstracts abstract text words was found to be 50 . Words from citing statements referring to the papers to be retrieved were then added to the index terms and abstract words as additional access points, and searching was repeated. Average recall increased to 70 . Only words from citing statements published within a year of the cited papers were used. The retrieval effect of citing statement words alone (published within a year) without index or abstract terms was the following: average recall was 40 . When just the words of the titles of the cited papers were added to those citing statement words, average recall increased to 50 . In this work we show that for every @math , such that for all @math where the parameters of the model do not depend on @math . They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than @math . Our proof exploits in novel ways the local treelike structure of Erd o s-R 'enyi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex @math of the graph has a neighborhood @math of radius @math in which the induced sub-graph is a tree union at most @math edges and where for each simple path in @math the sum of the vertex degrees along the path is @math . Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for @math it applies for all external fields and @math , where @math is the critical point for decay of correlation for the Ising model on @math . Given an @math matrix @math , its Schatten- @math norm, @math , is defined as @math , where @math is the @math -th largest singular value of @math . These norms have been studied in functional analysis in the context of non-commutative @math -spaces, and recently in data stream and linear sketching models of computation. Basic questions on the relations between these norms, such as their embeddability, are still open. Specifically, given a set of matrices @math , suppose we want to construct a linear map @math such that @math for each @math , where @math and @math , and further, @math for a given approximation factor @math and real number @math . Then how large do @math and @math need to be as a function of @math ? We nearly resolve this question for every @math , for the case where @math can be expressed as @math , where @math and @math are arbitrary matrices that are allowed to depend on @math , that is, @math can be implemented by left and right matrix multiplication. Namely, for every @math , we provide nearly matching upper and lower bounds on the size of @math and @math as a function of @math . Importantly, our upper bounds are oblivious , meaning that @math and @math do not depend on the @math , while our lower bounds hold even if @math and @math depend on the @math . As an application of our upper bounds, we answer a recent open question of about space-approximation trade-offs for the Schatten @math -norm, showing in a data stream it is possible to estimate the Schatten- @math norm up to a factor of @math using @math space. Index Coding has received considerable attention recently motivated in part by real-world applications and in part by its connection to Network Coding. The basic setting of Index Coding encodes the problem input as an undirected graph and the fundamental parameter is the broadcast rate @math , the average communication cost per bit for sufficiently long messages (i.e. the non-linear vector capacity). Recent nontrivial bounds on @math were derived from the study of other Index Coding capacities (e.g. the scalar capacity @math ) by Bar- (2006), Lubetzky and Stav (2007) and (2008). However, these indirect bounds shed little light on the behavior of @math : there was no known polynomial-time algorithm for approximating @math in a general network to within a nontrivial (i.e. @math ) factor, and the exact value of @math remained unknown for any graph where Index Coding is nontrivial. Our main contribution is a direct information-theoretic analysis of the broadcast rate @math using linear programs, in contrast to previous approaches that compared @math with graph-theoretic parameters. This allows us to resolve the aforementioned two open questions. We provide a polynomial-time algorithm with a nontrivial approximation ratio for computing @math in a general network along with a polynomial-time decision procedure for recognizing instances with @math . In addition, we pinpoint @math precisely for various classes of graphs (e.g. for various Cayley graphs of cyclic groups) thereby simultaneously improving the previously known upper and lower bounds for these graphs. Via this approach we construct graphs where the difference between @math and its trivial lower bound is linear in the number of vertices and ones where @math is uniformly bounded while its upper bound derived from the naive encoding scheme is polynomially worse. [See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the @math -Approximate Near Neighbor Search problem. For the @math -dimensional Euclidean space and @math -point datasets, we develop a data structure with space @math and query time @math for every @math such that: This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor @math , improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for @math , improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes. Given samples from an unknown multivariate distribution @math , is it possible to distinguish whether @math is the product of its marginals versus @math being far from every product distribution? Similarly, is it possible to distinguish whether @math equals a given distribution @math versus @math and @math being far from each other? These problems of testing independence and goodness-of-fit have received enormous attention in statistics, information theory, and theoretical computer science, with sample-optimal algorithms known in several interesting regimes of parameters. Unfortunately, it has also been understood that these problems become intractable in large dimensions, necessitating exponential sample complexity. Motivated by the exponential lower bounds for general distributions as well as the ubiquity of Markov Random Fields (MRFs) in the modeling of high-dimensional distributions, we initiate the study of distribution testing on structured multivariate distributions, and in particular the prototypical example of MRFs: the Ising Model. We demonstrate that, in this structured setting, we can avoid the curse of dimensionality, obtaining sample and time efficient testers for independence and goodness-of-fit. One of the key technical challenges we face along the way is bounding the variance of functions of the Ising model. This paper considers the problem of designing maximum distance separable (MDS) codes over small fields with constraints on the support of their generator matrices. For any given @math binary matrix @math , the GM-MDS conjecture, proposed by , states that if @math satisfies the so-called MDS condition, then for any field @math of size @math , there exists an @math MDS code whose generator matrix @math , with entries in @math , fits the matrix @math (i.e., @math is the support matrix of @math ). Despite all the attempts by the coding theory community, this conjecture remains still open in general. It was shown, independently by and , that the GM-MDS conjecture holds if the following conjecture, referred to as the TM-MDS conjecture, holds: if @math satisfies the MDS condition, then the determinant of a transform matrix @math , such that @math fits @math , is not identically zero, where @math is a Vandermonde matrix with distinct parameters. In this work, we first reformulate the TM-MDS conjecture in terms of the Wronskian determinant, and then present an algebraic-combinatorial approach based on polynomial-degree reduction for proving this conjecture. Our proof technique's strength is based primarily on reducing inherent combinatorics in the proof. We demonstrate the strength of our technique by proving the TM-MDS conjecture for the cases where the number of rows ( @math ) of @math is upper bounded by @math . For this class of special cases of @math where the only additional constraint is on @math , only cases with @math were previously proven theoretically, and the previously used proof techniques are not applicable to cases with @math . We consider the problem of broadcasting in an unknown radio network modeled as a directed graph @math , where @math . In unknown networks, every node knows only its own label, while it is unaware of any other parameter of the network, including its neighborhood and even any upper bound on the number of nodes. We show an @math upper bound on the time complexity of deterministic broadcasting. This is an improvement over the currently best upper bound @math for arbitrary networks, thus shrinking exponentially the existing gap between the lower bound @math and the upper bound from @math to @math . A range counting problem is specified by a set @math of size @math of points in @math , an integer weight @math associated to each point @math , and a range space @math . Given a query range @math , the target output is @math . Range counting for different range spaces is a central problem in Computational Geometry. We study @math -differentially private algorithms for range counting. Our main results are for the range space given by hyperplanes, that is, the halfspace counting problem. We present an @math -differentially private algorithm for halfspace counting in @math dimensions which achieves @math average squared error. This contrasts with the @math lower bound established by the classical result of Dinur and Nissim [PODS 2003] for arbitrary subset counting queries. We also show a matching lower bound on average squared error for any @math -differentially private algorithm for halfspace counting. Both bounds are obtained using discrepancy theory. For the lower bound, we use a modified discrepancy measure and bound approximation of @math -differentially private algorithms for range counting queries in terms of this discrepancy. We also relate the modified discrepancy measure to classical combinatorial discrepancy, which allows us to exploit known discrepancy lower bounds. This approach also yields a lower bound of @math for @math -differentially private orthogonal range counting in @math dimensions, the first known superconstant lower bound for this problem. For the upper bound, we use an approach inspired by partial coloring methods for proving discrepancy upper bounds, and obtain @math -differentially private algorithms for range counting with polynomially bounded shatter function range spaces. We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is @math -complete to decide whether the classical value of a non-local game is 1 or @math . Furthermore, as long as @math is small enough, this result does not depend on the gap @math . In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap @math decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of @math (proofs with two provers, one round, completeness probability @math , soundness probability @math , and commuting-operator strategies) can increase without bound as the gap @math gets arbitrarily small. Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class @math - @math of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap @math gets arbitrarily small. While we do not know any computable time upper bound on the class @math , a result of the first author and Vidick shows that for @math and @math , the class @math , with constant communication from the provers, is contained in @math . We give a lower bound of @math (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis. We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed @math , we construct a family of codes over alphabet of size @math with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching @math . In particular, for binary codes, we are able to recover a fraction of deletions approaching @math . Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was @math , and around @math for the binary case. Our result pins down the largest fraction of correctable deletions for @math -ary codes as @math , since @math is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between @math and @math for the limit of worst-case deletions correctable by binary codes remains a tantalizing open question.