@article{22519, abstract = {Glacier health across High Mountain Asia (HMA) is highly heterogeneous and strongly governed by regional climate, which is variably influenced by monsoon dynamics and the westerlies. We explore four decades of glacier energy and mass balance at three climatically distinct sites across HMA by utilising a detailed land surface model driven by bias-corrected Weather Research and Forecasting meteorological forcing. All three glaciers have experienced long-term mass losses (ranging from −0.04 ± 0.09 to −0.59 ± 0.20 m w.e. a−1) consistent with widespread warming across the region. However, complex and contrasting responses of glacier energy and mass balance to the patterns of the Indian Summer Monsoon were evident, largely driven by the role snowfall timing, amount and phase. A later monsoon onset generates less total snowfall to the glacier in the southeastern Tibetan Plateau during May–June, augmenting net shortwave radiation and affecting annual mass balance (−0.5 m w.e. on average compared to early onset years). Conversely, timing of the monsoon’s arrival has limited impact for the Nepalese Himalaya which is more strongly governed by the temperature and snowfall amount during the core monsoon season. In the arid central Tibetan Plateau, a later monsoon arrival results in a 40 mm (58%) increase of May–June snowfall on average compared to early onset years, likely driven by the greater interaction of westerly storm events. Meanwhile, a late monsoon cessation at this site sees an average 200 mm (192%) increase in late summer precipitation due to monsoonal storms. A trend towards weaker intensity monsoon conditions in recent decades, combined with long-term warming patterns, has produced predominantly negative glacier mass balances for all sites (up to 1 m w.e. more mass loss in the Nepalese Himalaya compared to strong monsoon intensity years) but sub-regional variability in monsoon timing can additionally complicate this response.}, author = {Shaw, T E and Miles, E S and Chen, D and Jouberton, A and Kneib, M and Fugger, S and Ou, T and Lai, H-W and Fujita, K and Yang, W and Fatichi, Simone and Pellicciotti, F}, issn = {1748-9326}, journal = {Environmental Research Letters}, keywords = {Glacier, Long-term mass balance, Monsoon, Snowfall}, number = {10}, publisher = {IOP Publishing}, title = {{Multi-decadal monsoon characteristics and glacier response in High Mountain Asia}}, doi = {10.1088/1748-9326/ac9008}, volume = {17}, year = {2022}, } @article{22502, abstract = {The Indian and East Asian summer monsoons shape the melt and accumulation patterns of glaciers in High Mountain Asia in complex ways due to the interaction of persistent cloud cover, large temperature ranges, high atmospheric water content and high precipitation rates. Glacier energy- and mass-balance modelling using in situ measurements offers insights into the ways in which surface processes are shaped by climatic regimes. In this study, we use a full energy- and mass-balance model and seven on-glacier automatic weather station datasets from different parts of the Central and Eastern Himalaya to investigate how monsoon conditions influence the glacier surface energy and mass balance. In particular, we look at how debris-covered and debris-free glaciers respond differently to monsoonal conditions. The radiation budget primarily controls the melt of clean-ice glaciers, but turbulent fluxes play an important role in modulating the melt energy on debris-covered glaciers. The sensible heat flux decreases during core monsoon, but the latent heat flux cools the surface due to evaporation of liquid water. This interplay of radiative and turbulent fluxes causes debris-covered glacier melt rates to stay almost constant through the different phases of the monsoon. Ice melt under thin debris, on the other hand, is amplified by both the dark surface and the turbulent fluxes, which intensify melt during monsoon through surface heating and condensation. Pre-monsoon snow cover can considerably delay melt onset and have a strong impact on the seasonal mass balance. Intermittent monsoon snow cover lowers the melt rates at high elevation. This work is fundamental to the understanding of the present and future Himalayan cryosphere and water budget, while informing and motivating further glacier- and catchment-scale research using process-based models.The radiation budget primarily controls the melt of clean-ice glaciers, but turbulent fluxes play an important role in modulating the melt energy on debris-covered glaciers. The sensible heat flux decreases during core monsoon, but the latent heat flux cools the surface due to evaporation of liquid water. This interplay of radiative and turbulent fluxes causes debris-covered glacier melt rates to stay almost constant through the different phases of the monsoon. Ice melt under thin debris, on the other hand, is amplified by both the dark surface and the turbulent fluxes, which intensify melt during monsoon through surface heating and condensation. Pre-monsoon snow cover can considerably delay melt onset and have a strong impact on the seasonal mass balance. Intermittent monsoon snow cover lowers the melt rates at high elevation. This work is fundamental to the understanding of the present and future Himalayan cryosphere and water budget, while informing and motivating further glacier- and catchment-scale research using process-based models.}, author = {Fugger, Stefan and Fyffe, Catriona L. and Fatichi, Simone and Miles, Evan and McCarthy, Michael and Shaw, Thomas E. and Ding, Baohong and Yang, Wei and Wagnon, Patrick and Immerzeel, Walter and Liu, Qiao and Pellicciotti, Francesca}, issn = {1994-0424}, journal = {The Cryosphere}, number = {5}, pages = {1631--1652}, publisher = {Copernicus Publications}, title = {{Understanding monsoon controls on the energy and mass balance of glaciers in the Central and Eastern Himalaya}}, doi = {10.5194/tc-16-1631-2022}, volume = {16}, year = {2022}, } @article{22515, abstract = {Hydrological, ecohydrological, and terrestrial biosphere models depend on pedotransferfunctions for computing soil hydraulic parameters based on easily measurable variables, such as soil texturaland physical properties. Several pedotransfer functions have been derived in the last few decades, providingdivergent estimates of soil hydraulic parameters. In this study, we quantify how uncertainties embedded inusing different pedotransfer functions propagate to ecosystem dynamics, including simulated hydrologicalfluxes and vegetation response to water availability. Using a state-of-the-art ecohydrological model applied at79 sites worldwide, we show that uncertainties related to pedotransfer functions can affect both hydrologicaland vegetation dynamics. Uncertainties in evapotranspiration, plant productivity, and vegetation structure,quantified as leaf area, are in the order of ∼10% at annual time scales. Runoff and groundwater rechargeuncertainties are one order of magnitude larger. All uncertainties are largely amplified when small-scaletopography is taken into account in a distributed domain, especially for water-limited ecosystems with lowpermeability soils. Overall, pedotransfer function related uncertainties for a given soil type are higher thanuncertainties across soil types in both hydrological and ecosystem dynamics. The magnitude of uncertainties isclimate-dependent but not soil type-dependent. Evapotranspiration, vegetation structure, and plant productivityuncertainties are higher in water-limited semiarid climates, whereas groundwater recharge uncertainties arehigher in climates where potential evapotranspiration is comparable to precipitation.}, author = {Paschalis, Athanasios and Bonetti, Sara and Guo, Yanran and Fatichi, Simone}, issn = {1944-7973}, journal = {Water Resources Research}, number = {9}, publisher = {American Geophysical Union}, title = {{On the uncertainty induced by pedotransfer functions in terrestrial biosphere modeling}}, doi = {10.1029/2021wr031871}, volume = {58}, year = {2022}, } @article{22537, abstract = {Urban heat islands (UHIs) are a widely studied phenomenon, while research on urban-rural differences in humidity, the so called urban dry or moisture islands (UDIs, UMIs), is less common and a large-scale quantification of the seasonal and diurnal patterns of the UDI is still lacking. However, quantification of the UDI/UMI effect is essential to understand the impacts of humidity on outdoor thermal comfort, building energy consumption, and urban ecology in cities worldwide. Here, we use a set of globally distributed air temperature and humidity measurements (1089 stations) to quantify diurnal and seasonal patterns of UHI and UDI resulting from rapid urbanization over many regions of the world. The terms ‘absolute UDI’ and ‘relative UDI’ are defined, which quantify urban–rural differences in actual and relative humidity metrics, respectively. Results show that absolute UDI is largest during daytime with the peak humidity decrease in urban areas occurring during late afternoon hours. In contrast, relative UDI is largest during night and the peak urban relative humidity (RH) decrease and vapor pressure deficit (VPD) increase occurs in the late evening hours with values of around −10% to −11% for RH and 2.9–3.6 hPa for VPD between 20–00 local time during summer. Relative and absolute UDIs are largest during the warm season, except for daytime RH UDI, which does not show any seasonal pattern. In agreement with literature, canopy air UHI is shown to be a nighttime phenomenon, which is larger during summer than winter. Relative UDI is predominantly caused by changes in actual humidity during day and UHI during nighttime.}, author = {Meili, Naika and Paschalis, Athanasios and Manoli, Gabriele and Fatichi, Simone}, issn = {1748-9326}, journal = {Environmental Research Letters}, keywords = {Urban dry island, Urban moisture island, Urban heat island, Urban climate, Urbanization effects, Humidity}, number = {5}, publisher = {IOP Publishing}, title = {{Diurnal and seasonal patterns of global urban dry islands}}, doi = {10.1088/1748-9326/ac68f8}, volume = {17}, year = {2022}, } @article{22555, abstract = {The current Chilean megadrought has led to acute water shortages in central Chile since 2010.Glaciers have provided vital fresh water to the region's rivers, but the quantity, timing and sustainability ofthat provision remain unclear. Here we combine in-situ, remote sensing and climate reanalysis data to showthat from 2010 to 2018 during the megadrought, unsustainable imbalance ablation of glaciers (ablation notbalanced by new snowfall) strongly buffered the late-summer discharge of the Maipo River, a primary sourceof water to Santiago. If there had been no glaciers, water availability would have been reduced from Decemberthrough May, with a 31 ± 19% decrease during March. Our results indicate that while the annual contributionsof imbalance ablation to river discharge during the megadrought have been small compared to those fromprecipitation and sustainable balance ablation, they have nevertheless been a substantial input to a hydrologicalsystem that was already experiencing high water stress. The water-equivalent volume of imbalance ablationgenerated in the Maipo Basin between 2010 and 2018 was 740 × 10 6 m 3 (19 ± 12 mm yr −1), approximately 3.4times the capacity of the basin's El Yeso Reservoir. This is equivalent to 14% of Santiago's potable water use inthat time, while total glacier ablation was equivalent to 59%. We show that glacier retreat will exacerbate riverdischarge deficits and further jeopardize water availability in central Chile if precipitation deficits endure, andconjecture that these effects will be amplified by climatic warming.}, author = {McCarthy, Michael and Meier, Fabienne and Fatichi, Simone and Stocker, Benjamin D. and Shaw, Thomas E. and Miles, Evan and Dussaillant, Inés and Pellicciotti, Francesca}, issn = {2328-4277}, journal = {Earth's Future}, number = {10}, publisher = {American Geophysical Union}, title = {{Glacier contributions to river discharge during the current chilean megadrought}}, doi = {10.1029/2022ef002852}, volume = {10}, year = {2022}, } @article{22564, abstract = {It is well known that cities increase air and surface temperatures compared to their rural surroundings, the so-called urban heat island (UHI) effect. However, the associated changes in atmospheric humidity (also known as urban dry island, UDI) and convection triggering remain largely unexplored and it is still unclear how urban modifications of the surface energy budget Influence the diurnal evolution of temperature and humidity in the Atmospheric Boundary Layer (ABL) and ultimately control the initiation of convective clouds. Here we quantify the impact of different urban settings and free atmospheric conditions on UHI, UDI, and convection triggers by means of a zero-order model of the ABL. Specifically, we derive an approximate solution for urban-rural changes in surface energy fluxes and ABL potential temperature and humidity and we investigate the crossing between the ABL height and the lifting condensation level (LCL) which is a proxy for the triggering of convective clouds. We show that urban areas are generally warmer and drier, thus causing an increase in both ABL and LCL heights. However, the response of the ABL-LCL crossing to surface conditions is non-linear and there exists a range of free atmosphere conditions for which changes in imperviousness can impact convective clouds.}, author = {Chiu, Clinton T.F. and Wang, Kai and Paschalis, Athanasios and Erfani, Tohid and Peleg, Nadav and Fatichi, Simone and Theeuwes, Natalie and Manoli, Gabriele}, issn = {2212-0955}, journal = {Urban Climate}, keywords = {Urban heat island, Urban dry island, Boundary layer, Convective clouds, Analytical model}, publisher = {Elsevier}, title = {{An analytical approximation of urban heat and dry islands and their impact on convection triggering}}, doi = {10.1016/j.uclim.2022.101346}, volume = {46}, year = {2022}, } @article{10827, abstract = {Titanium dioxide has been extensively studied in the rutile or anatase phase, while its high-pressure phases are less well-understood, despite that many are thought to have interesting optical, mechanical, and electrochemical properties. First-principles methods, such as density functional theory (DFT), are often used to compute the enthalpies of TiO2 phases at 0 K, but they are expensive and, thus, impractical for long time scale and large system-size simulations at finite temperatures. On the other hand, cheap empirical potentials fail to capture the relative stabilities of various polymorphs. To model the thermodynamic behaviors of ambient and high-pressure phases of TiO2, we design an empirical model as a baseline and then train a machine learning potential based on the difference between the DFT data and the empirical model. This so-called Δ-learning potential contains long-range electrostatic interactions and predicts the 0 K enthalpies of stable TiO2 phases that are in good agreement with DFT. We construct a pressure–temperature phase diagram of TiO2 in the range 0 < P < 70 GPa and 100 < T < 1500 K. We then simulate dynamic phase transition processes by compressing anatase at different temperatures. At 300 K, we predominantly observe an anatase-to-baddeleyite transformation at about 20 GPa via a martensitic two-step mechanism with a highly ordered and collective atomic motion. At 2000 K, anatase can transform into cotunnite around 45–55 GPa in a thermally activated and probabilistic manner, accompanied by diffusive movement of oxygen atoms. The pressures computed for these transitions show good agreement with experiments. Our results shed light on how to synthesize and stabilize high-pressure TiO2 phases, and our method is generally applicable to other functional materials with multiple polymorphs.}, author = {Lee, Jacob G. and Pickard, Chris J. and Cheng, Bingqing}, issn = {1089-7690}, journal = {The Journal of chemical physics}, number = {7}, publisher = {AIP Publishing}, title = {{High-pressure phase behaviors of titanium dioxide revealed by a Δ-learning potential}}, doi = {10.1063/5.0079844}, volume = {156}, year = {2022}, } @article{12128, abstract = {We introduce a machine-learning (ML) framework for high-throughput benchmarking of diverse representations of chemical systems against datasets of materials and molecules. The guiding principle underlying the benchmarking approach is to evaluate raw descriptor performance by limiting model complexity to simple regression schemes while enforcing best ML practices, allowing for unbiased hyperparameter optimization, and assessing learning progress through learning curves along series of synchronized train-test splits. The resulting models are intended as baselines that can inform future method development, in addition to indicating how easily a given dataset can be learnt. Through a comparative analysis of the training outcome across a diverse set of physicochemical, topological and geometric representations, we glean insight into the relative merits of these representations as well as their interrelatedness.}, author = {Poelking, Carl and Faber, Felix A and Cheng, Bingqing}, issn = {2632-2153}, journal = {Machine Learning: Science and Technology}, keywords = {Artificial Intelligence, Human-Computer Interaction, Software}, number = {4}, publisher = {IOP Publishing}, title = {{BenchML: An extensible pipelining framework for benchmarking representations of materials and molecules at scale}}, doi = {10.1088/2632-2153/ac4d11}, volume = {3}, year = {2022}, } @article{12249, abstract = {The chemical potential of a component in a solution is defined as the free energy change as the amount of that component changes. Computing this fundamental thermodynamic property from atomistic simulations is notoriously difficult because of the convergence issues involved in free energy methods and finite size effects. This Communication presents the so-called S0 method, which can be used to obtain chemical potentials from static structure factors computed from equilibrium molecular dynamics simulations under the isothermal–isobaric ensemble. This new method is demonstrated on the systems of binary Lennard-Jones particles, urea–water mixtures, a NaCl aqueous solution, and a high-pressure carbon–hydrogen mixture. }, author = {Cheng, Bingqing}, issn = {1089-7690}, journal = {The Journal of Chemical Physics}, keywords = {Physical and Theoretical Chemistry, General Physics and Astronomy}, number = {12}, publisher = {AIP Publishing}, title = {{Computing chemical potentials of solutions from structure factors}}, doi = {10.1063/5.0107059}, volume = {157}, year = {2022}, } @article{11937, abstract = {Most experimentally known high-pressure ice phases have a body-centred cubic (bcc) oxygen lattice. Our large-scale molecular-dynamics simulations with a machine-learning potential indicate that, amongst these bcc ice phases, ices VII, VII′ and X are the same thermodynamic phase under different conditions, whereas superionic ice VII″ has a first-order phase boundary with ice VII′. Moreover, at about 300 GPa, the transformation between ice X and the Pbcm phase has a sharp structural change but no apparent activation barrier, whilst at higher pressures the barrier gradually increases. Our study thus clarifies the phase behaviour of the high-pressure ices and reveals peculiar solid–solid transition mechanisms not known in other systems.}, author = {Reinhardt, Aleks and Bethkenhagen, Mandy and Coppari, Federica and Millot, Marius and Hamel, Sebastien and Cheng, Bingqing}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Thermodynamics of high-pressure ice phases explored with atomistic simulations}}, doi = {10.1038/s41467-022-32374-1}, volume = {13}, year = {2022}, } @article{9695, abstract = {Real-world data typically contain a large number of features that are often heterogeneous in nature, relevance, and also units of measure. When assessing the similarity between data points, one can build various distance measures using subsets of these features. Using the fewest features but still retaining sufficient information about the system is crucial in many statistical learning approaches, particularly when data are sparse. We introduce a statistical test that can assess the relative information retained when using two different distance measures, and determine if they are equivalent, independent, or if one is more informative than the other. This in turn allows finding the most informative distance measure out of a pool of candidates. The approach is applied to find the most relevant policy variables for controlling the Covid-19 epidemic and to find compact yet informative representations of atomic structures, but its potential applications are wide ranging in many branches of science.}, author = {Glielmo, Aldo and Zeni, Claudio and Cheng, Bingqing and Csanyi, Gabor and Laio, Alessandro}, issn = {2752-6542}, journal = {PNAS Nexus}, number = {2}, publisher = {Oxford University Press}, title = {{Ranking the information content of distance measures}}, doi = {10.1093/pnasnexus/pgac039}, volume = {1}, year = {2022}, } @article{12237, abstract = {Thermoelectric technology requires synthesizing complex materials where not only the crystal structure but also other structural features such as defects, grain size and orientation, and interfaces must be controlled. To date, conventional solid-state techniques are unable to provide this level of control. Herein, we present a synthetic approach in which dense inorganic thermoelectric materials are produced by the consolidation of well-defined nanoparticle powders. The idea is that controlling the characteristics of the powder allows the chemical transformations that take place during consolidation to be guided, ultimately yielding inorganic solids with targeted features. Different from conventional methods, syntheses in solution can produce particles with unprecedented control over their size, shape, crystal structure, composition, and surface chemistry. However, to date, most works have focused only on the low-cost benefits of this strategy. In this perspective, we first cover the opportunities that solution processing of the powder offers, emphasizing the potential structural features that can be controlled by precisely engineering the inorganic core of the particle, the surface, and the organization of the particles before consolidation. We then discuss the challenges of this synthetic approach and more practical matters related to solution processing. Finally, we suggest some good practices for adequate knowledge transfer and improving reproducibility among different laboratories.}, author = {Fiedler, Christine and Kleinhanns, Tobias and Garcia, Maria and Lee, Seungho and Calcabrini, Mariano and Ibáñez, Maria}, issn = {1520-5002}, journal = {Chemistry of Materials}, keywords = {Materials Chemistry, General Chemical Engineering, General Chemistry}, number = {19}, pages = {8471--8489}, publisher = {American Chemical Society}, title = {{Solution-processed inorganic thermoelectric materials: Opportunities and challenges ∇}}, doi = {10.1021/acs.chemmater.2c01967}, volume = {34}, year = {2022}, } @article{11700, abstract = {This paper contains two contributions in the study of optimal transport on metric graphs. Firstly, we prove a Benamou–Brenier formula for the Wasserstein distance, which establishes the equivalence of static and dynamical optimal transport. Secondly, in the spirit of Jordan–Kinderlehrer–Otto, we show that McKean–Vlasov equations can be formulated as gradient flow of the free energy in the Wasserstein space of probability measures. The proofs of these results are based on careful regularisation arguments to circumvent some of the difficulties arising in metric graphs, namely, branching of geodesics and the failure of semi-convexity of entropy functionals in the Wasserstein space.}, author = {Erbar, Matthias and Forkert, Dominik L and Maas, Jan and Mugnolo, Delio}, issn = {1556-181X}, journal = {Networks and Heterogeneous Media}, number = {5}, pages = {687--717}, publisher = {AIMS}, title = {{Gradient flow formulation of diffusion equations in the Wasserstein space over a metric graph}}, doi = {10.3934/nhm.2022023}, volume = {17}, year = {2022}, } @inproceedings{12299, abstract = {Transfer learning is a classic paradigm by which models pretrained on large “upstream” datasets are adapted to yield good results on “downstream” specialized datasets. Generally, more accurate models on the “upstream” dataset tend to provide better transfer accuracy “downstream”. In this work, we perform an in-depth investigation of this phenomenon in the context of convolutional neural networks (CNNs) trained on the ImageNet dataset, which have been pruned-that is, compressed by sparsifiying their connections. We consider transfer using unstructured pruned models obtained by applying several state-of-the-art pruning methods, including magnitude-based, second-order, regrowth, lottery-ticket, and regularization approaches, in the context of twelve standard transfer tasks. In a nutshell, our study shows that sparse models can match or even outperform the transfer performance of dense models, even at high sparsities, and, while doing so, can lead to significant inference and even training speedups. At the same time, we observe and analyze significant differences in the behaviour of different pruning methods. The code is available at: https://github.com/IST-DASLab/sparse-imagenet-transfer.}, author = {Iofinova, Eugenia B and Peste, Elena-Alexandra and Kurtz, Mark and Alistarh, Dan-Adrian}, booktitle = {2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition}, issn = {2575-7075}, location = {New Orleans, LA, United States}, pages = {12256--12266}, publisher = {IEEE}, title = {{How well do sparse ImageNet models transfer?}}, doi = {10.1109/cvpr52688.2022.01195}, year = {2022}, } @inproceedings{12161, abstract = {We introduce LIMES, a new method for learning with non-stationary streaming data, inspired by the recent success of meta-learning. The main idea is not to attempt to learn a single classifier that would have to work well across all occurring data distributions, nor many separate classifiers, but to exploit a hybrid strategy: we learn a single set of model parameters from which a specific classifier for any specific data distribution is derived via classifier adaptation. Assuming a multiclass classification setting with class-prior shift, the adaptation step can be performed analytically with only the classifier’s bias terms being affected. Another contribution of our work is an extrapolation step that predicts suitable adaptation parameters for future time steps based on the previous data. In combination, we obtain a lightweight procedure for learning from streaming data with varying class distribution that adds no trainable parameters and almost no memory or computational overhead compared to training a single model. Experiments on a set of exemplary tasks using Twitter data show that LIMES achieves higher accuracy than alternative approaches, especially with respect to the relevant real-world metric of lowest within-day accuracy.}, author = {Tomaszewska, Paulina and Lampert, Christoph}, booktitle = {26th International Conference on Pattern Recognition}, issn = {2831-7475}, location = {Montreal, Canada}, pages = {2128--2134}, publisher = {IEEE}, title = {{Lightweight conditional model extrapolation for streaming data under class-prior shift}}, doi = {10.1109/icpr56361.2022.9956195}, volume = {2022}, year = {2022}, } @inproceedings{12160, abstract = {We present the Filecoin Hierarchical Consensus framework, which aims to overcome the throughput challenges of blockchain consensus by horizontally scaling the network. Unlike traditional sharding designs, based on partitioning the state of the network, our solution centers on the concept of subnets -which are organized hierarchically- and can be spawned on-demand to manage new state. Child sub nets are firewalled from parent subnets, have their own specific policies, and run a different consensus algorithm, increasing the network capacity and enabling new applications. Moreover, they benefit from the security of parent subnets by periodically checkpointing state. In this paper, we introduce the overall system architecture, our detailed designs for cross-net transaction handling, and the open questions that we are still exploring.}, author = {De la Rocha, Alfonso and Kokoris Kogias, Eleftherios and Soares, Jorge M. and Vukolic, Marko}, booktitle = {42nd International Conference on Distributed Computing Systems Workshops}, issn = {2332-5666}, location = {Bologna, Italy}, pages = {45--52}, publisher = {IEEE}, title = {{Hierarchical consensus: A horizontal scaling framework for blockchains}}, doi = {10.1109/icdcsw56584.2022.00018}, volume = {2022}, year = {2022}, } @inproceedings{12432, abstract = {We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If G ∼ G(n, p) and p ≥ 100 log n/n then the expected running time of CertifyHAM is O(n/p) which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and Krivelevich, who proved analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n −1/2 respectively.}, author = {Anastos, Michael}, booktitle = {63rd Annual IEEE Symposium on Foundations of Computer Science}, isbn = {9781665455190}, issn = {0272-5428}, location = {Denver, CO, United States}, pages = {919--930}, publisher = {IEEE}, title = {{Solving the Hamilton cycle problem fast on average}}, doi = {10.1109/FOCS54457.2022.00091}, volume = {2022-October}, year = {2022}, } @inproceedings{12017, abstract = {In the classic adversarial communication problem, two parties communicate over a noisy channel in the presence of a malicious jamming adversary. The arbitrarily varying channels (AVCs) offer an elegant framework to study a wide range of interesting adversary models. The optimal throughput or capacity over such AVCs is intimately tied to the underlying adversary model; in some cases, capacity is unknown and the problem is known to be notoriously hard. The omniscient adversary, one which knows the sender’s entire channel transmission a priori, is one of such classic models of interest; the capacity under such an adversary remains an exciting open problem. The myopic adversary is a generalization of that model where the adversary’s observation may be corrupted over a noisy discrete memoryless channel. Through the adversary’s myopicity, one can unify the slew of different adversary models, ranging from the omniscient adversary to one that is completely blind to the transmission (the latter is the well known oblivious model where the capacity is fully characterized).In this work, we present new results on the capacity under both the omniscient and myopic adversary models. We completely characterize the positive capacity threshold over general AVCs with omniscient adversaries. The characterization is in terms of two key combinatorial objects: the set of completely positive distributions and the CP-confusability set. For omniscient AVCs with positive capacity, we present non-trivial lower and upper bounds on the capacity; unlike some of the previous bounds, our bounds hold under fairly general input and jamming constraints. Our lower bound improves upon the generalized Gilbert-Varshamov bound for general AVCs while the upper bound generalizes the well known Elias-Bassalygo bound (known for binary and q-ary alphabets). For the myopic AVCs, we build on prior results known for the so-called sufficiently myopic model, and present new results on the positive rate communication threshold over the so-called insufficiently myopic regime (a completely insufficient myopic adversary specializes to an omniscient adversary). We present interesting examples for the widely studied models of adversarial bit-flip and bit-erasure channels. In fact, for the bit-flip AVC with additive adversarial noise as well as random noise, we completely characterize the omniscient model capacity when the random noise is sufficiently large vis-a-vis the adversary’s budget.}, author = {Yadav, Anuj Kumar and Alimohammadi, Mohammadreza and Zhang, Yihan and Budkuley, Amitalok J. and Jaggi, Sidharth}, booktitle = {2022 IEEE International Symposium on Information Theory}, isbn = {9781665421591}, issn = {2157-8095}, location = {Espoo, Finland}, pages = {2535--2540}, publisher = {IEEE}, title = {{New results on AVCs with omniscient and myopic adversaries}}, doi = {10.1109/ISIT50566.2022.9834632}, volume = {2022}, year = {2022}, } @inproceedings{12018, abstract = {We study the problem of characterizing the maximal rates of list decoding in Euclidean spaces for finite list sizes. For any positive integer L ≥ 2 and real N > 0, we say that a subset C⊂Rn is an (N,L – 1)-multiple packing or an (N,L– 1)-list decodable code if every Euclidean ball of radius nN−−−√ in ℝ n contains no more than L − 1 points of C. We study this problem with and without ℓ 2 norm constraints on C, and derive the best-known lower bounds on the maximal rate for (N,L−1) multiple packing. Our bounds are obtained via error exponents for list decoding over Additive White Gaussian Noise (AWGN) channels. We establish a curious inequality which relates the error exponent, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We derive various bounds on the error exponent for list decoding in both bounded and unbounded settings which could be of independent interest beyond multiple packing.}, author = {Zhang, Yihan and Vatedka, Shashank}, booktitle = {2022 IEEE International Symposium on Information Theory}, isbn = {9781665421591}, issn = {2157-8095}, location = {Espoo, Finland}, pages = {1324--1329}, publisher = {IEEE}, title = {{Lower bounds on list decoding capacity using error exponents}}, doi = {10.1109/ISIT50566.2022.9834815}, volume = {2022}, year = {2022}, } @inproceedings{12019, abstract = {This paper studies combinatorial properties of codes for the Z-channel. A Z-channel with error fraction τ takes as input a length-n binary codeword and injects in an adversarial manner up to nτ asymmetric errors, i.e., errors that only zero out bits but do not flip 0’s to 1’s. It is known that the largest (L − 1)-list-decodable code for the Z-channel with error fraction τ has exponential (in n) size if τ is less than a critical value that we call the Plotkin point and has constant size if τ is larger than the threshold. The (L−1)-list-decoding Plotkin point is known to be L−1L−1−L−LL−1. In this paper, we show that the largest (L−1)-list-decodable code ε-above the Plotkin point has size Θ L (ε −3/2 ) for any L − 1 ≥ 1.}, author = {Polyanskii, Nikita and Zhang, Yihan}, booktitle = {2022 IEEE International Symposium on Information Theory}, isbn = {9781665421591}, issn = {2157-8095}, location = {Espoo, Finland}, pages = {2553--2558}, publisher = {IEEE}, title = {{List-decodable zero-rate codes for the Z-channel}}, doi = {10.1109/ISIT50566.2022.9834829}, volume = {2022}, year = {2022}, }