Search

We study property testing in the subcube conditional model introduced by Bhattacharyya and Chakraborty (2017). We obtain the first equivalence test for $n$-dimensional distributions that is quasi-linear in $n$, improving the previously known $\tilde{O}(n^2/\varepsilon^2)$ query complexity bound to $\tilde{O}(n/\varepsilon^2)$. We extend this result to general finite alphabets with logarithmic cost in the alphabet size. By exploiting the specific structure of the queries that we use (which are more restrictive than general subcube queries), we obtain a cubic improvement over the best known test for distributions over $\{1,\ldots,N\}$ under the interval querying model of Canonne, Ron and Servedio (2015), attaining a query complexity of $\tilde{O}((\log N)/\varepsilon^2)$, which for fixed $\varepsilon$ almost matches the known lower bound of $\Omega((\log N)/\log\log N)$. We also derive a product test for $n$-dimensional distributions with $\tilde{O}(n / \varepsilon^2)$ queries, and provide an $\Omega(\sqrt{n} / \varepsilon^2)$ lower bound for this property.

The Huge Object model is a distribution testing model in which we are given access to independent samples from an unknown distribution over the set of strings $\{0,1\}^n$, but are only allowed to query a few bits from the samples. We investigate the problem of testing whether a distribution is supported on $m$ elements in this model. It turns out that the behavior of this property is surprisingly intricate, especially when also considering the question of adaptivity. We prove lower and upper bounds for both adaptive and non-adaptive algorithms in the one-sided and two-sided error regime. Our bounds are tight when $m$ is fixed to a constant (and the distance parameter $\varepsilon$ is the only variable). For the general case, our bounds are at most $O(\log m)$ apart. In particular, our results show a surprising $O(\log \varepsilon^{-1})$ gap between the number of queries required for non-adaptive testing as compared to adaptive testing. For one sided error testing, we also show that a $O(\log m)$ gap between the number of samples and the number of queries is necessary. Our results utilize a wide variety of combinatorial and probabilistic methods.

Although carbon monoxide (CO) is an abundant molecule and may have great importance for planetary interiors, measurements of its properties are difficult due to its extreme volatility. We calculate the equation of state for CO over a range of temperature and density that is applicable to the conditions in planetary interiors. Previous experimental and theoretical studies cover only a limited temperature-density range. Our calculations match these early results well, but now cover the full range of relevance. The method of calculation is based on the general-purpose quotidian equation of state described by More et al. (1988), which is here used in order to generate a freely downloadable look-up table to be used by the community., Comment: 12 pages, 5 figures. Accepted for publication in Icarus

We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an $n$-point set $X \subset \mathbb{R}^d$. In the streaming model, the points in $X$ can be added and removed arbitrarily, and the goal is to maintain an approximation in small space. In low dimensions, $(1+\epsilon)$ approximations are possible in sublinear space [Frahling, Indyk, Sohler, SoCG '05]. However, for high dimensional spaces the best known approximation for this problem was $\tilde{O}(\log n)$, due to [Chen, Jayaram, Levi, Waingarten, STOC '22], improving on the prior $O(\log^2 n)$ bound due to [Indyk, STOC '04] and [Andoni, Indyk, Krauthgamer, SODA '08]. In this paper, we break the logarithmic barrier, and give the first constant factor sublinear space approximation to Euclidean MST. For any $\epsilon\geq 1$, our algorithm achieves an $\tilde{O}(\epsilon^{-2})$ approximation in $n^{O(\epsilon)}$ space. We complement this by proving that any single pass algorithm which obtains a better than $1.10$-approximation must use $\Omega(\sqrt{n})$ space, demonstrating that $(1+\epsilon)$ approximations are not possible in high-dimensions, and that our algorithm is tight up to a constant. Nevertheless, we demonstrate that $(1+\epsilon)$ approximations are possible in sublinear space with $O(1/\epsilon)$ passes over the stream. More generally, for any $\alpha \geq 2$, we give a $\alpha$-pass streaming algorithm which achieves a $(1+O(\frac{\log \alpha + 1}{ \alpha \epsilon}))$ approximation in $n^{O(\epsilon)} d^{O(1)}$ space. Our streaming algorithms are linear sketches, and therefore extend to the massively-parallel computation model (MPC). Thus, our results imply the first $(1+\epsilon)$-approximation to Euclidean MST in a constant number of rounds in the MPC model.

Existing Graph Neural Networks (GNNs) compute the message exchange between nodes by either aggregating uniformly (convolving) the features of all the neighboring nodes, or by applying a non-uniform score (attending) to the features. Recent works have shown the strengths and weaknesses of the resulting GNN architectures, respectively, GCNs and GATs. In this work, we aim at exploiting the strengths of both approaches to their full extent. To this end, we first introduce the graph convolutional attention layer (CAT), which relies on convolutions to compute the attention scores. Unfortunately, as in the case of GCNs and GATs, we show that there exists no clear winner between the three (neither theoretically nor in practice) as their performance directly depends on the nature of the data (i.e., of the graph and features). This result brings us to the main contribution of our work, the learnable graph convolutional attention network (L-CAT): a GNN architecture that automatically interpolates between GCN, GAT and CAT in each layer, by adding only two scalar parameters. Our results demonstrate that L-CAT is able to efficiently combine different GNN layers along the network, outperforming competing methods in a wide range of datasets, and resulting in a more robust model that reduces the need of cross-validating., Comment: Published as a conference paper at ICLR 2023. 35 pages, 5 figures

Graph-based learning is a rapidly growing sub-field of machine learning with applications in social networks, citation networks, and bioinformatics. One of the most popular models is graph attention networks. They were introduced to allow a node to aggregate information from features of neighbor nodes in a non-uniform way, in contrast to simple graph convolution which does not distinguish the neighbors of a node. In this paper, we theoretically study the behaviour of graph attention networks. We prove multiple results on the performance of the graph attention mechanism for the problem of node classification for a contextual stochastic block model. Here, the node features are obtained from a mixture of Gaussians and the edges from a stochastic block model. We show that in an "easy" regime, where the distance between the means of the Gaussians is large enough, graph attention is able to distinguish inter-class from intra-class edges. Thus it maintains the weights of important edges and significantly reduces the weights of unimportant edges. Consequently, we show that this implies perfect node classification. In the "hard" regime, we show that every attention mechanism fails to distinguish intra-class from inter-class edges. In addition, we show that graph attention convolution cannot (almost) perfectly classify the nodes even if intra-class edges could be separated from inter-class edges. Beyond perfect node classification, we provide a positive result on graph attention's robustness against structural noise in the graph. In particular, our robustness result implies that graph attention can be strictly better than both the simple graph convolution and the best linear classifier of node features. We evaluate our theoretical results on synthetic and real-world data., Comment: 45 pages, 5 figures

Recent astronomical observations obtained with the Kepler and TESS missions and their related ground-based follow-ups revealed an abundance of exoplanets with a size intermediate between Earth and Neptune. A low occurrence rate of planets has been identified at around twice the size of Earth, known as the exoplanet radius gap or radius valley. We explore the geometry of this gap in the mass-radius diagram, with the help of a Mathematica plotting tool developed with the capability of manipulating exoplanet data in multidimensional parameter space, and with the help of visualized water equations of state in the temperature-density graph and the entropy-pressure graph. We show that the radius valley can be explained by a compositional difference between smaller, predominantly rocky planets and larger planets that exhibit greater compositional diversity including cosmic ices (water, ammonia, methane) and gaseous envelopes. In particular, among the larger planets, when viewed from the perspective of planet equilibrium temperature, the hot ones are consistent with ice-dominated composition without significant gaseous envelopes, while the cold ones have more diverse compositions, including various amounts of gaseous envelopes., Comment: 30 pages, 15 figures

We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an $n$-point set $X \subset \{1,2,\dots,\Delta\}^d$, and computing the Earth Mover Distance (EMD) between two multi-sets $A,B \subset \{1,2,\dots,\Delta\}^d$ of size $n$. We consider the turnstile model, where points can be added and removed. We give a one-pass streaming algorithm for MST and a two-pass streaming algorithm for EMD, both achieving an approximation factor of $\tilde{O}(\log n)$ and using polylog$(n,d,\Delta)$-space only. Furthermore, our algorithm for EMD can be compressed to a single pass with a small additive error. Previously, the best known sublinear-space streaming algorithms for either problem achieved an approximation of $O(\min\{ \log n , \log (\Delta d)\} \log n)$ [Andoni-Indyk-Krauthgamer '08, Backurs-Dong-Indyk-Razenshteyn-Wagner '20]. For MST, we also prove that any constant space streaming algorithm can only achieve an approximation of $\Omega(\log n)$, analogous to the $\Omega(\log n)$ lower bound for EMD of [Andoni-Indyk-Krauthgamer '08]. Our algorithms are based on an improved analysis of a recursive space partitioning method known generically as the Quadtree. Specifically, we show that the Quadtree achieves an $\tilde{O}(\log n)$ approximation for both EMD and MST, improving on the $O(\min\{ \log n , \log (\Delta d)\} \log n)$ approximation of [Andoni-Indyk-Krauthgamer '08, Backurs-Dong-Indyk-Razenshteyn-Wagner '20].

We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input graph and work with a specified fraction of adversarial erasures in adjacency entries. We focus on two computational tasks: testing if a graph is connected or $\varepsilon$-far from connected and estimating the average degree. For testing connectedness, we discover a threshold phenomenon: when the fraction of erasures is less than $\varepsilon$, this property can be tested efficiently (in time independent of the size of the graph); when the fraction of erasures is at least $\varepsilon,$ then a number of queries linear in the size of the graph representation is required. Our erasure-resilient algorithm (for the special case with no erasures) is an improvement over the previously known algorithm for connectedness in the standard property testing model and has optimal dependence on the proximity parameter $\varepsilon$. For estimating the average degree, our results provide an "interpolation" between the query complexity for this computational task in the model with no erasures in two different settings: with only degree queries, investigated by Feige (SIAM J. Comput. `06), and with degree queries and neighbor queries, investigated by Goldreich and Ron (Random Struct. Algorithms `08) and Eden et al. (ICALP `17). We conclude with a discussion of our model and open questions raised by our work., Comment: To appear in the 12th Innovations in Theoretical Computer Science (ITCS) conference, 2021

We study the problems of learning and testing junta distributions on $\{-1,1\}^n$ with respect to the uniform distribution, where a distribution $p$ is a $k$-junta if its probability mass function $p(x)$ depends on a subset of at most $k$ variables. The main contribution is an algorithm for finding relevant coordinates in a $k$-junta distribution with subcube conditioning [BC18, CCKLW20]. We give two applications: 1. An algorithm for learning $k$-junta distributions with $\tilde{O}(k/\epsilon^2) \log n + O(2^k/\epsilon^2)$ subcube conditioning queries, and 2. An algorithm for testing $k$-junta distributions with $\tilde{O}((k + \sqrt{n})/\epsilon^2)$ subcube conditioning queries. All our algorithms are optimal up to poly-logarithmic factors. Our results show that subcube conditioning, as a natural model for accessing high-dimensional distributions, enables significant savings in learning and testing junta distributions compared to the standard sampling model. This addresses an open question posed by Aliakbarpour, Blais, and Rubinfeld [ABR17].

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm., Comment: Added Remark 4.4, which discusses the time complexity (the algorithms are polynomial-time, based on an observation from [CJLW20]); removing log log log n factor for the Gaussian testing algorithm. These changes reflect those included in the conference version (SODA'21)

We show that there exist properties that are maximally hard for testing, while still admitting PCPPs with a proof size very close to linear. Specifically, for every fixed $\ell$, we construct a property $\mathcal{P}^{(\ell)}\subseteq\{0,1\}^n$ satisfying the following: Any testing algorithm for $\mathcal{P}^{(\ell)}$ requires $\Omega(n)$ many queries, and yet $\mathcal{P}^{(\ell)}$ has a constant query PCPP whose proof size is $O(n\cdot \log^{(\ell)}n)$, where $\log^{(\ell)}$ denotes the $\ell$ times iterated log function (e.g., $\log^{(2)}n = \log \log n$). The best previously known upper bound on the PCPP proof size for a maximally hard to test property was $O(n \cdot \mathrm{poly}\log{n})$. As an immediate application, we obtain stronger separations between the standard testing model and both the tolerant testing model and the erasure-resilient testing model: for every fixed $\ell$, we construct a property that has a constant-query tester, but requires $\Omega(n/\log^{(\ell)}(n))$ queries for every tolerant or erasure-resilient tester.

We study the problem of estimating the number of edges of an unknown, undirected graph $G=([n],E)$ with access to an independent set oracle. When queried about a subset $S\subseteq [n]$ of vertices the independent set oracle answers whether $S$ is an independent set in $G$ or not. Our first main result is an algorithm that computes a $(1+\epsilon)$-approximation of the number of edges $m$ of the graph using $\min(\sqrt{m},n / \sqrt{m})\cdot\textrm{poly}(\log n,1/\epsilon)$ independent set queries. This improves the upper bound of $\min(\sqrt{m},n^2/m)\cdot\textrm{poly}(\log n,1/\epsilon)$ by Beame et al. \cite{BHRRS18}. Our second main result shows that ${\min(\sqrt{m},n/\sqrt{m}))/\textrm{polylog}(n)}$ independent set queries are necessary, thus establishing that our algorithm is optimal up to a factor of $\textrm{poly}(\log n, 1/\epsilon)$.

The radii and orbital periods of 4000+ confirmed/candidate exoplanets have been precisely measured by the Kepler mission. The radii show a bimodal distribution, with two peaks corresponding to smaller planets (likely rocky) and larger intermediate-size planets, respectively. While only the masses of the planets orbiting the brightest stars can be determined by ground-based spectroscopic observations, these observations allow calculation of their average densities placing constraints on the bulk compositions and internal structures. Yet an important question about the composition of planets ranging from 2 to 4 Earth radii still remains. They may either have a rocky core enveloped in a H2-He gaseous envelope (gas dwarfs) or contain a significant amount of multi-component, H2O-dominated ices/fluids (water worlds). Planets in the mass range of 10-15 Earth masses, if half-ice and half-rock by mass, have radii of 2.5 Earth radii, which exactly match the second peak of the exoplanet radius bimodal distribution. Any planet in the 2-4 Earth radii range requires a gas envelope of at most a few mass percentage points, regardless of the core composition. To resolve the ambiguity of internal compositions, we use a growth model and conduct Monte Carlo simulations to demonstrate that many intermediate-size planets are water worlds., Comment: PNAS link: https://www.pnas.org/content/116/20/9723 Complete data and mass-radius tables are available at: https://www.cfa.harvard.edu/~lzeng/planetmodels.html

The habitable zone (HZ) is the region around a star(s) where standing bodies of water could exist on the surface of a rocky planet. The classical HZ definition makes a number of assumptions common to the Earth, including assuming that the most important greenhouse gases for habitable planets are CO2 and H2O, habitable planets orbit main-sequence stars, and that the carbonate-silicate cycle is a universal process on potentially habitable planets. Here, we discuss these and other predictions for the habitable zone and the observations that are needed to test them. We also, for the first time, argue why A-stars may be interesting HZ prospects. Instead of relying on unverified extrapolations from our Earth, we argue that future habitability studies require first principles approaches where temporal, spatial, physical, chemical, and biological systems are dynamically coupled. We also suggest that next-generation missions are only the beginning of a much more data-filled era in the not-too-distant future, when possibly hundreds to thousands of HZ planets will yield the statistical data we need to go beyond just finding habitable zone planets to actually determining which ones are most likely to exhibit life., Comment: White paper submitted to the NAS Astro 2020 decadal survey(5 pages, 1 figure + cover page, 13 co-authors + 10 co-signers). First author name added to description. In this arxiv version, one more co-signer was added after the NAS version was submitted. Link: http://surveygizmoresponseuploads.s3.amazonaws.com/fileuploads/623127/4458621/64-2dc3fcc201a3075e3da6233f1a91c668_RamirezRamsesM.pdf

The emerging theory of graph limits exhibits an analytic perspective on graphs, showing that many important concepts and tools in graph theory and its applications can be described more naturally (and sometimes proved more easily) in analytic language. We extend the theory of graph limits to the ordered setting, presenting a limit object for dense vertex-ordered graphs, which we call an orderon. As a special case, this yields limit objects for matrices whose rows and columns are ordered, and for dynamic graphs that expand (via vertex insertions) over time. Along the way, we devise an ordered locality-preserving variant of the cut distance between ordered graphs, showing that two graphs are close with respect to this distance if and only if they are similar in terms of their ordered subgraph frequencies. We show that the space of orderons is compact with respect to this distance notion, which is key to a successful analysis of combinatorial objects through their limits. We derive several applications of the ordered limit theory in extremal combinatorics, sampling, and property testing in ordered graphs. In particular, we prove a new ordered analogue of the well-known result by Alon and Stav [RS\&A'08] on the furthest graph from a hereditary property; this is the first known result of this type in the ordered setting. Unlike the unordered regime, here the random graph model $G(n, p)$ with an ordering over the vertices is not always asymptotically the furthest from the property for some $p$. However, using our ordered limit theory, we show that random graphs generated by a stochastic block model, where the blocks are consecutive in the vertex ordering, are (approximately) the furthest. Additionally, we describe an alternative analytic proof of the ordered graph removal lemma [Alon et al., FOCS'17]., Comment: Completed the proof of the ordered removal lemma application; introduced the notion of pixelization

We investigate the thermal equation of state, bulk modulus, thermal expansion coefficient, and heat capacity of MH-III (CH$_4$ filled-ice Ih), needed for the study of CH$_4$ transport and outgassing for the case of Titan and super-Titans. We employ density functional theory and ab initio molecular dynamics simulations in the generalized-gradient approximation with a van der Waals functional. We examine the finite temperature range of $300$K-$500$K and pressures between $2$GPa-$7$GPa. We find that in this P-T range MH-III is less dense than liquid water. There is uncertainty in the normalized moment of inertia (MOI) of Titan; it is estimated to be in the range of $0.33-0.34$. If Titan's MOI is $0.34$, MH-III is not stable at present in Titan's interior, yielding an easier path for the outgassing of CH$_4$. However, for an MOI of $0.33$, MH-III is thermodynamically stable at the bottom of a ice-rock internal layer capable of storing CH$_4$. For rock mass fractions $\lessapprox 0.2$ upwelling melt is likely hot enough to dissociate MH-III along its path. For super-Titans considering a mixture of MH-III and ice VII, melt is always positively buoyant if the H$_2$O:CH$_4$ mole fraction is $>5.5$. Our thermal evolution model shows that MH-III may be present today in Titan's core, confined to a thin ($\approx 10$km) outer shell. We find that the heat capacity of MH-III is higher than measured values for pure water-ice, larger than heat capacity often adopted for ice-rock mixtures with implications for internal heating., Comment: 23 pages, 23 figures, accepted in The Astrophysical Journal

We design a sublinear-time approximation algorithm for quadratic function minimization problems with a better error bound than the previous algorithm by Hayashi and Yoshida (NIPS'16). Our approximation algorithm can be modified to handle the case where the minimization is done over a sphere. The analysis of our algorithms is obtained by combining results from graph limit theory, along with a novel spectral decomposition of matrices. Specifically, we prove that a matrix $A$ can be decomposed into a structured part and a pseudorandom part, where the structured part is a block matrix with a polylogarithmic number of blocks, such that in each block all the entries are the same, and the pseudorandom part has a small spectral norm, achieving better error bound than the existing decomposition theorem of Frieze and Kannan (FOCS'96). As an additional application of the decomposition theorem, we give a sublinear-time approximation algorithm for computing the top singular values of a matrix.

We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of $n$-nodes graphs using rejection sampling queries requires complexity $\widetilde{\Omega}(n^2)$. Via reductions from the rejection sampling model, we give three new lower bounds for tolerant testing of Boolean functions of the form $f\colon\{0,1\}^n\to \{0,1\}$: $\bullet$Tolerant $k$-junta testing with \emph{non-adaptive} queries requires $\widetilde{\Omega}(k^2)$ queries. $\bullet$Tolerant unateness testing requires $\widetilde{\Omega}(n)$ queries. $\bullet$Tolerant unateness testing with \emph{non-adaptive} queries requires $\widetilde{\Omega}(n^{3/2})$ queries. Given the $\widetilde{O}(k^{3/2})$-query non-adaptive junta tester of Blais \cite{B08}, we conclude that non-adaptive tolerant junta testing requires more queries than non-tolerant junta testing. In addition, given the $\widetilde{O}(n^{3/4})$-query unateness tester of Chen, Waingarten, and Xie \cite{CWX17b} and the $\widetilde{O}(n)$-query non-adaptive unateness tester of Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri \cite{BCPRS17}, we conclude that tolerant unateness testing requires more queries than non-tolerant unateness testing, in both adaptive and non-adaptive settings. These lower bounds provide the first separation between tolerant and non-tolerant testing for a natural property of Boolean functions.

We study ocean exoplanets, for which the global surface ocean is separated from the rocky interior by a high-pressure ice mantle. We describe a mechanism that can pump salts out of the ocean, resulting in oceans of very low salinity. Here we focus on the H2O-NaCl system, though we discuss the application of this pump to other salts as well. We find our ocean worlds to be acidic, with a pH in the range of 2-4. We discuss and compare between the conditions found within our studied oceans and the conditions in which polyextremophiles were discovered. This work focuses on exoplanets in the super-Earth mass range (2 M_Earth), with water composing at least a few percent of their mass. Although, the principal of the desalination pump may extend beyond this mass range., Comment: 61 pages, 18 figures, accepted for publication in ApJ

Traditional definitions of the habitable zone assume that habitable planets contain a carbonate-silicate cycle that regulates CO2 between the atmosphere, surface, and the interior. Such theories have been used to cast doubt on the habitability of ocean worlds. However, Levi et al (2017) have recently proposed a mechanism by which CO2 is mobilized between the atmosphere and the interior of an ocean world. At high enough CO2 pressures, sea ice can become enriched in CO2 clathrates and sink after a threshold density is achieved. The presence of subpolar sea ice is of great importance for habitability in ocean worlds. It may moderate the climate and is fundamental in current theories of life formation in diluted environments. Here, we model the Levi et al. mechanism and use latitudinally-dependent non-grey energy balance and single-column radiative-convective climate models and find that this mechanism may be sustained on ocean worlds that rotate at least 3 times faster than the Earth. We calculate the circumstellar region in which this cycle may operate for G-M-stars (Teff = 2,600 to 5,800 K), extending from about 1.23 to 1.65, 0.69 to 0.954, 0.38 to 0.528 AU, 0.219 to 0.308 AU, 0.146 to 0.206 AU, and 0.0428 to 0.0617 AU for G2, K2, M0, M3, M5, and M8 stars, respectively. However, unless planets are very young and not tidally locked, our mechanism would be unlikely to apply to stars cooler than a ~M3. We predict C/O ratios for our atmospheres (about 0.5) that can be verified by the JWST mission., Comment: Published in the Monthly Notices of the Royal Astronomical Society (31 pages, 7 Figures, 1 Table) https://doi.org/10.1093/mnras/sty761

This is a white paper in response to the National Academy of Sciences "Exoplanet Science Strategy" call. We summarize recent advances in theoretical habitability studies and argue that such studies will remain important for guiding and interpreting observations. Interactions between 1-D and 3-D climate modelers will be necessary to resolve recent discrepancies in model results and improve habitability studies. Observational capabilities will also need improvement. Although basic observations can be performed with present capabilities, technological advances will be necessary to improve climate models to the level needed for planetary habitability studies., Comment: This is a white paper submitted to the National Academies 2018 "Exoplanet Science Strategy" call(6 pages total, including cover page). Corrected references section in this version. http://sites.nationalacademies.org/SSB/CurrentProjects/SSB_180659

We examine the possibility that icy super-Earth mass planets, formed over long time scales (0.1--1~Gyr) at large distances ($\sim$ 200--1000~AU) from their host stars, will develop massive H-rich atmospheres. Within the interior of these planets, high pressure converts CH$_4$ into ethane, butane, or diamond and releases H$_2$. Using simplified models which capture the basic physics of the internal structure, we show that the physical properties of the atmosphere depend on the outflux of H$_2$ from the mantle. When this outflux is $\lesssim 10^{10}$ [molec cm$^{-2}$ s$^{-1}$], the outgassed atmosphere has base pressure $\lesssim$ 1 bar. Larger outflows result in a substantial atmosphere where the base pressure may approach $10^3 - 10^4$ bar. For any pressure, the mean density of these planets, 2.4--3 [g cm$^{-3}$], is much larger than the mean density of Uranus and Neptune, 1.3--1.6 [g cm$^{-3}$]. Thus, observations can distinguish between a Planet Nine with a primordial H/He-rich atmosphere accreted from the protosolar nebula and one with an atmosphere outgassed from the core., Comment: 32 pages, 11 figures, accepted to ApJ

We consider super-Earth sized planets which have a water mass fraction that is large enough to form an external mantle composed of high pressure water ice polymorphs and that lack a substantial H/He atmosphere. We consider such planets in their habitable zone so that their outermost condensed mantle is a global deep liquid ocean. For these ocean planets we investigate potential internal reservoirs of CO2; the amount of CO2 dissolved in the ocean for the various saturation conditions encountered, and the ocean-atmosphere exchange flux of CO2. We find that in steady state the abundance of CO2 in the atmosphere has two possible states. When the wind-driven circulation is the dominant CO2 exchange mechanism, an atmosphere of tens of bars of CO2 results, where the exact value depends on the subtropical ocean surface temperature and the deep ocean temperature. When sea-ice formation, acting on these planets as a CO2 deposition mechanism, is the dominant exchange mechanism, an atmosphere of a few bars of CO2 is established. The exact value depends on the subpolar surface temperature. Our results suggest the possibility of a negative feedback mechanism, unique to water planets, where a reduction in the subpolar temperature drives more CO2 into the atmosphere to increase the greenhouse effect., Comment: 114 pages, 55 figures, submitted to the astrophysical journal

A function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $\epsilon$-close to some $k$-junta and reject any function that is $\epsilon'$-far from every $k'$-junta for some $\epsilon'= O(\epsilon)$ and $k' = O(k)$. Our first result is an algorithm that solves this problem with query complexity polynomial in $k$ and $1/\epsilon$. This result is obtained via a new polynomial-time approximation algorithm for submodular function minimization (SFM) under large cardinality constraints, which holds even when only given an approximate oracle access to the function. Our second result considers the case where $k'=k$. We show how to obtain a smooth tradeoff between the amount of tolerance and the query complexity in this setting. Specifically, we design an algorithm that given $\rho\in(0,1/2)$ accepts any function that is $\frac{\epsilon\rho}{16}$-close to some $k$-junta and rejects any function that is $\epsilon$-far from every $k$-junta. The query complexity of the algorithm is $O\big( \frac{k\log k}{\epsilon\rho(1-\rho)^k} \big)$. Finally, we show how to apply the second result to the problem of tolerant isomorphism testing between two unknown Boolean functions $f$ and $g$. We give an algorithm for this problem whose query complexity only depends on the (unknown) smallest $k$ such that either $f$ or $g$ is close to being a $k$-junta., Comment: Polished the writing, corrected typos, and fixed an issue in the proof of Theorem 1.2

In 1994, Talagrand showed a generalization of the celebrated KKL theorem. In this work, we prove that the converse of this generalization also holds. Namely, for any sequence of numbers $00$, it is possible to find a roughly balanced Boolean function $f$ such that $\textrm{Inf}_j[f] < a_j$ for every $1 \le j \le n$.

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a {\em sublinear-time\/} algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries and neighbor queries. We show that for any given approximation parameter $0<\epsilon<1$, the algorithm provides an estimate $\widehat{t}$ such that with high constant probability, $(1-\epsilon)\cdot t< \widehat{t}<(1+\epsilon)\cdot t$, where $t$ is the number of triangles in the graph $G$. The expected query complexity of the algorithm is $\!\left(\frac{n}{t^{1/3}} + \min\left\{m, \frac{m^{3/2}}{t}\right\}\right)\cdot {\rm poly}(\log n, 1/\epsilon)$, where $n$ is the number of vertices in the graph and $m$ is the number of edges, and the expected running time is $\!\left(\frac{n}{t^{1/3}} + \frac{m^{3/2}}{t}\right)\cdot {\rm poly}(\log n, 1/\epsilon)$. We also prove that $\Omega\!\left(\frac{n}{t^{1/3}} + \min\left\{m, \frac{m^{3/2}}{t}\right\}\right)$ queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to polylogarithmic factors in $n$ (and the dependence on $1/\epsilon$)., Comment: To appear in the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)

We study the transport of methane in the external water envelopes surrounding water-rich super-Earths and estimate its outgassing into the atmosphere. We investigate the influence of methane on the thermodynamics and mechanics of the water mantle. We find that including methane in the water matrix introduces a new phase (filled ice) resulting in hotter planetary interiors. This effect renders the super-ionic and reticulating phases accessible to relatively low mass planets lacking a H/He atmosphere. We model the thermal and structural profile of the planetary crust and discuss five possible crustal regimes. The formation of methane clathrate in the subsurface is shown to inhibit the formation of a subterranean ocean. This effect results in increased stresses on the lithosphere making modes of ice plate tectonics possible. The dynamics of the tectonic plates are analysed. We derive overturn and resurfacing time scales as well as the melt fraction underneath spreading centers. Ice mantle dynamics is found to be important for assessing the composition of the atmosphere. We formulate the relation between the outgassing flux of methane and the tectonic mode dynamics. We give numerical estimates for the global outgassing rate of methane into the atmosphere., Comment: 123 pages, 27 figures, 8 tables, to be published in the astrophysical journal

Whether volatiles can be entrapped in a background matrix composing planetary envelopes and be dragged via convection to the surface is a key question in understanding atmospheric fluxes, cycles and composition. In this paper we consider super-Earths with an extensive water mantle (i.e. water planets), and the possibility of entrapment of methane in their extensive water ice envelopes. We adopt the theory developed by van der Waals & Platteeuw (1959) for modelling solid solutions, often used for modelling clathrate hydrates, and modify it in order to estimate the thermodynamic stability field of a new phase, called methane filled ice Ih. We find that in comparison to water ice VII the filled ice Ih structure may be stable not only at the high pressures but also at the high temperatures expected at the core-water mantle transition boundary of water planets., Comment: 20 pages, 6 figures, accepted for publication in the astrophysical journal

By using a hydrodynamic atmospheric escape mechanism \citep{amit09} we show how the unusually high mass density of Quaoar could have been predicted (constrained), without any knowledge of a binary companion. We suggest an explanation of the recent spectroscopic observations of Orcus and Charon \citep{delsanti10,cook07}. We present a simple relation between the detection of certain volatile ices and the body mass density and diameter. As a test case we implement the relations on the KBO 2003 AZ$_{84}$ and give constraints on its mass density. We also present a method of relating the latitude-dependence of hydrodynamic gas escape to the internal structure of a rapidly rotating body and apply it to Haumea., Comment: 37 pages, 5 figures. Much revised version. To appear in Icarus