Source author record

Amit Levi

Amit Levi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

astro-ph.EP Data Structures and Algorithms Discrete Mathematics Machine Learning math.PR math.ST Statistics Theory astro-ph.IM Computational Complexity Information Theory math.CO math.IT

Catalog footprint

What is connected

9works

12topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

New Perspectives on the Exoplanet Radius Gap from a Mathematica Tool and Visualized Water Equation of State

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.

preprint2021arXiv

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

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.

preprint2020arXiv

Learning and Testing Junta Distributions with Subcube Conditioning

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/ε^2) \log n + O(2^k/ε^2)$ subcube conditioning queries, and 2. An algorithm for testing $k$-junta distributions with $\tilde{O}((k + \sqrt{n})/ε^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].

preprint2016arXiv

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

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 $ε$-close to some $k$-junta and reject any function that is $ε'$-far from every $k'$-junta for some $ε'= O(ε)$ and $k' = O(k)$. Our first result is an algorithm that solves this problem with query complexity polynomial in $k$ and $1/ε$. 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 $ρ\in(0,1/2)$ accepts any function that is $\frac{ερ}{16}$-close to some $k$-junta and rejects any function that is $ε$-far from every $k$-junta. The query complexity of the algorithm is $O\big( \frac{k\log k}{ερ(1-ρ)^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.

preprint2015arXiv

Approximately Counting Triangles in Sublinear Time

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<ε<1$, the algorithm provides an estimate $\widehat{t}$ such that with high constant probability, $(1-ε)\cdot t< \widehat{t}<(1+ε)\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/ε)$, 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/ε)$. We also prove that $Ω\!\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/ε$).

preprint2015arXiv

On the Converse of Talagrand's Influence Inequality

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 $0<a_1,a_2,\ldots,a_n\le 1$ such that $\sum_{j=1}^n a_j/(1-\log a_j)\ge C$ for some constant $C>0$, 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$.

preprint2014arXiv

Structure and Dynamics of Cold Water Super-Earths: The Case of Occluded CH4 and its Outgassing

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.

preprint2013arXiv

Volatile Transport inside Super-Earths by Entrapment in the Water Ice Matrix

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.

preprint2011arXiv

Estimating the Density of Intermediate Size KBOs from Considerations of Volatile Retention

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.