An official website of the United States government
Spectral independence is a recently developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimalO(nlogn)sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on usingLp-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, and Yin, FOCS’13). The non-linearity ofLp-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture theLp-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graphG (n, d/n), where the previously known algorithms run in timenO(logd) or applied only to larged. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constantd, throughout the uniqueness regime.
more »
« less
Local decoding and testing of polynomials over grids
We study the local decodability and (tolerant) local testability of low‐degreen‐variate polynomials over arbitrary fields, evaluated over the domain {0,1}n. We show that for every field there is a tolerant local test whose query complexity depends only on the degree. In contrast we show that decodability is possible over fields of positive characteristic, but not over the reals.
more »
« less
- Award ID(s):
- 1715187
- PAR ID:
- 10165610
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 57
- Issue:
- 3
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 658-694
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A<sc>bstract</sc> We use a combination of analytical and numerical methods to study out-of-time order correlators (OTOCs) in the sparse Sachdev-Ye-Kitaev (SYK) model. We find that at a given order ofN, the standard result for theq-local, all-to-all SYK, obtained through the sum over ladder diagrams, is corrected by a series in the sparsity parameter,k. We present an algorithm to sum the diagrams at any given order of 1/(kq)n. We also study OTOCs numerically as a function of the sparsity parameter and determine the Lyapunov exponent. We find that numerical stability when extracting the Lyapunov exponent requires averaging over a massive number of realizations. This trade-off between the efficiency of the sparse model and consistent behavior at finiteNbecomes more significant for larger values ofN.more » « less
-
We prove the failure of the local-global principle, with respect to discrete valuations, for isotropy of quadratic forms in 2^n variables over function fields of transcendence degree n at least 2 over an algebraically closed field of characteristic not 2. Our construction involves the generalized Kummer varieties considered by Borcea and by Cynk and Hulek as well as new results on the nontriviality of unramified cohomology of products of elliptic curves over discretely valued fields.more » « less
-
Abstract Undirected C(sp3)−H functionalization reactions often follow site‐selectivity patterns that mirror the corresponding C−H bond dissociation energies (BDEs). This often results in the functionalization of weaker tertiary C−H bonds in the presence of stronger secondary and primary bonds. An important, contemporary challenge is the development of catalyst systems capable of selectively functionalizing stronger primary and secondary C−H bonds over tertiary and benzylic C−H sites. Herein, we report a Cu catalyst that exhibits a high degree of primary and secondary over tertiary C−H bond selectivity in the amidation of linear and cyclic hydrocarbons with aroyl azides ArC(O)N3. Mechanistic and DFT studies indicate that C−H amidation involves H‐atom abstraction from R‐H substrates by nitrene intermediates [Cu](κ2‐N,O‐NC(O)Ar) to provide carbon‐based radicals R.and copper(II)amide intermediates [CuII]‐NHC(O)Ar that subsequently capture radicals R.to form products R‐NHC(O)Ar. These studies reveal important catalyst features required to achieve primary and secondary C−H amidation selectivity in the absence of directing groups.more » « less
-
null (Ed.)We study the problems of identity and closeness testing of n-dimensional product distributions. Prior works of Canonne et al. (2017) and Daskalakis and Pan (2017) have established tight sample complexity bounds for non-tolerant testing over a binary alphabet: given two product distributions P and Q over a binary alphabet, distinguish between the cases P = Q and dTV(P;Q) > epsilon . We build on this prior work to give a more comprehensive map of the complexity of testing of product distributions by investigating tolerant testing with respect to several natural distance measures and over an arbitrary alphabet. Our study gives a fine-grained understanding of how the sample complexity of tolerant testing varies with the distance measures for product distributions. In addition, we also extend one of our upper bounds on product distributions to bounded-degree Bayes nets.more » « less
