@inproceedings{10367, abstract = {How information is created, shared and consumed has changed rapidly in recent decades, in part thanks to new social platforms and technologies on the web. With ever-larger amounts of unstructured and limited labels, organizing and reconciling information from different sources and modalities is a central challenge in machine learning. This cutting-edge tutorial aims to introduce the multimodal entailment task, which can be useful for detecting semantic alignments when a single modality alone does not suffice for a whole content understanding. Starting with a brief overview of natural language processing, computer vision, structured data and neural graph learning, we lay the foundations for the multimodal sections to follow. We then discuss recent multimodal learning literature covering visual, audio and language streams, and explore case studies focusing on tasks which require fine-grained understanding of visual and linguistic semantics question answering, veracity and hatred classification. Finally, we introduce a new dataset for recognizing multimodal entailment, exploring it in a hands-on collaborative section. Overall, this tutorial gives an overview of multimodal learning, introduces a multimodal entailment dataset, and encourages future research in the topic.}, author = {Ilharco, Cesar and Shirazi, Afsaneh and Gopalan, Arjun and Nagrani, Arsha and Bratanič, Blaž and Bregler, Chris and Liu, Christina and Ferreira, Felipe and Barcik, Gabriek and Ilharco, Gabriel and Osang, Georg F and Bulian, Jannis and Frank, Jared and Smaira, Lucas and Cao, Qin and Marino, Ricardo and Patel, Roma and Leung, Thomas and Imbrasaite, Vaiva}, booktitle = {59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, Tutorial Abstracts}, isbn = {9-781-9540-8557-2}, location = {Bangkok, Thailand}, pages = {29--30}, publisher = {Association for Computational Linguistics}, title = {{Recognizing multimodal entailment}}, doi = {10.18653/v1/2021.acl-tutorials.6}, year = {2021}, } @article{10401, abstract = {Theoretical and experimental studies of the interaction between spins and temperature are vital for the development of spin caloritronics, as they dictate the design of future devices. In this work, we propose a two-terminal cold-atom simulator to study that interaction. The proposed quantum simulator consists of strongly interacting atoms that occupy two temperature reservoirs connected by a one-dimensional link. First, we argue that the dynamics in the link can be described using an inhomogeneous Heisenberg spin chain whose couplings are defined by the local temperature. Second, we show the existence of a spin current in a system with a temperature difference by studying the dynamics that follows the spin-flip of an atom in the link. A temperature gradient accelerates the impurity in one direction more than in the other, leading to an overall spin current similar to the spin Seebeck effect.}, author = {Barfknecht, Rafael E. and Foerster, Angela and Zinner, Nikolaj T. and Volosniev, Artem}, issn = {2399-3650}, journal = {Communications Physics}, number = {1}, publisher = {Springer Nature}, title = {{Generation of spin currents by a temperature gradient in a two-terminal device}}, doi = {10.1038/s42005-021-00753-7}, volume = {4}, year = {2021}, } @article{10402, abstract = {Branching morphogenesis governs the formation of many organs such as lung, kidney, and the neurovascular system. Many studies have explored system-specific molecular and cellular regulatory mechanisms, as well as self-organizing rules underlying branching morphogenesis. However, in addition to local cues, branched tissue growth can also be influenced by global guidance. Here, we develop a theoretical framework for a stochastic self-organized branching process in the presence of external cues. Combining analytical theory with numerical simulations, we predict differential signatures of global vs. local regulatory mechanisms on the branching pattern, such as angle distributions, domain size, and space-filling efficiency. We find that branch alignment follows a generic scaling law determined by the strength of global guidance, while local interactions influence the tissue density but not its overall territory. Finally, using zebrafish innervation as a model system, we test these key features of the model experimentally. Our work thus provides quantitative predictions to disentangle the role of different types of cues in shaping branched structures across scales.}, author = {Ucar, Mehmet C and Kamenev, Dmitrii and Sunadome, Kazunori and Fachet, Dominik C and Lallemend, Francois and Adameyko, Igor and Hadjab, Saida and Hannezo, Edouard B}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Theory of branching morphogenesis by local interactions and global guidance}}, doi = {10.1038/s41467-021-27135-5}, volume = {12}, year = {2021}, } @article{10403, abstract = {Synaptic transmission, connectivity, and dendritic morphology mature in parallel during brain development and are often disrupted in neurodevelopmental disorders. Yet how these changes influence the neuronal computations necessary for normal brain function are not well understood. To identify cellular mechanisms underlying the maturation of synaptic integration in interneurons, we combined patch-clamp recordings of excitatory inputs in mouse cerebellar stellate cells (SCs), three-dimensional reconstruction of SC morphology with excitatory synapse location, and biophysical modeling. We found that postnatal maturation of postsynaptic strength was homogeneously reduced along the somatodendritic axis, but dendritic integration was always sublinear. However, dendritic branching increased without changes in synapse density, leading to a substantial gain in distal inputs. Thus, changes in synapse distribution, rather than dendrite cable properties, are the dominant mechanism underlying the maturation of neuronal computation. These mechanisms favor the emergence of a spatially compartmentalized two-stage integration model promoting location-dependent integration within dendritic subunits.}, author = {Biane, Celia and Rückerl, Florian and Abrahamsson, Therese and Saint-Cloment, Cécile and Mariani, Jean and Shigemoto, Ryuichi and Digregorio, David A. and Sherrard, Rachel M. and Cathala, Laurence}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{Developmental emergence of two-stage nonlinear synaptic integration in cerebellar interneurons}}, doi = {10.7554/eLife.65954}, volume = {10}, year = {2021}, } @article{10404, abstract = {While convolutional neural networks (CNNs) have found wide adoption as state-of-the-art models for image-related tasks, their predictions are often highly sensitive to small input perturbations, which the human vision is robust against. This paper presents Perturber, a web-based application that allows users to instantaneously explore how CNN activations and predictions evolve when a 3D input scene is interactively perturbed. Perturber offers a large variety of scene modifications, such as camera controls, lighting and shading effects, background modifications, object morphing, as well as adversarial attacks, to facilitate the discovery of potential vulnerabilities. Fine-tuned model versions can be directly compared for qualitative evaluation of their robustness. Case studies with machine learning experts have shown that Perturber helps users to quickly generate hypotheses about model vulnerabilities and to qualitatively compare model behavior. Using quantitative analyses, we could replicate users’ insights with other CNN architectures and input images, yielding new insights about the vulnerability of adversarially trained models.}, author = {Sietzen, Stefan and Lechner, Mathias and Borowski, Judy and Hasani, Ramin and Waldner, Manuela}, issn = {1467-8659}, journal = {Computer Graphics Forum}, number = {7}, pages = {253--264}, publisher = {Wiley}, title = {{Interactive analysis of CNN robustness}}, doi = {10.1111/cgf.14418}, volume = {40}, year = {2021}, } @article{10406, abstract = {Multicellular organisms develop complex shapes from much simpler, single-celled zygotes through a process commonly called morphogenesis. Morphogenesis involves an interplay between several factors, ranging from the gene regulatory networks determining cell fate and differentiation to the mechanical processes underlying cell and tissue shape changes. Thus, the study of morphogenesis has historically been based on multidisciplinary approaches at the interface of biology with physics and mathematics. Recent technological advances have further improved our ability to study morphogenesis by bridging the gap between the genetic and biophysical factors through the development of new tools for visualizing, analyzing, and perturbing these factors and their biochemical intermediaries. Here, we review how a combination of genetic, microscopic, biophysical, and biochemical approaches has aided our attempts to understand morphogenesis and discuss potential approaches that may be beneficial to such an inquiry in the future.}, author = {Mishra, Nikhil and Heisenberg, Carl-Philipp J}, issn = {1545-2948}, journal = {Annual Review of Genetics}, keywords = {morphogenesis, forward genetics, high-resolution microscopy, biophysics, biochemistry, patterning}, pages = {209--233}, publisher = {Annual Reviews}, title = {{Dissecting organismal morphogenesis by bridging genetics and biophysics}}, doi = {10.1146/annurev-genet-071819-103748}, volume = {55}, year = {2021}, } @inproceedings{10407, abstract = {Digital hardware Trojans are integrated circuits whose implementation differ from the specification in an arbitrary and malicious way. For example, the circuit can differ from its specified input/output behavior after some fixed number of queries (known as “time bombs”) or on some particular input (known as “cheat codes”). To detect such Trojans, countermeasures using multiparty computation (MPC) or verifiable computation (VC) have been proposed. On a high level, to realize a circuit with specification F one has more sophisticated circuits F⋄ manufactured (where F⋄ specifies a MPC or VC of F ), and then embeds these F⋄ ’s into a master circuit which must be trusted but is relatively simple compared to F . Those solutions impose a significant overhead as F⋄ is much more complex than F , also the master circuits are not exactly trivial. In this work, we show that in restricted settings, where F has no evolving state and is queried on independent inputs, we can achieve a relaxed security notion using very simple constructions. In particular, we do not change the specification of the circuit at all (i.e., F=F⋄ ). Moreover the master circuit basically just queries a subset of its manufactured circuits and checks if they’re all the same. The security we achieve guarantees that, if the manufactured circuits are initially tested on up to T inputs, the master circuit will catch Trojans that try to deviate on significantly more than a 1/T fraction of the inputs. This bound is optimal for the type of construction considered, and we provably achieve it using a construction where 12 instantiations of F need to be embedded into the master. We also discuss an extremely simple construction with just 2 instantiations for which we conjecture that it already achieves the optimal bound.}, author = {Chakraborty, Suvradip and Dziembowski, Stefan and Gałązka, Małgorzata and Lizurej, Tomasz and Pietrzak, Krzysztof Z and Yeo, Michelle X}, isbn = {9-783-0309-0452-4}, issn = {1611-3349}, location = {Raleigh, NC, United States}, pages = {397--428}, publisher = {Springer Nature}, title = {{Trojan-resilience without cryptography}}, doi = {10.1007/978-3-030-90453-1_14}, volume = {13043}, year = {2021}, } @inproceedings{10414, abstract = {We consider the almost-sure (a.s.) termination problem for probabilistic programs, which are a stochastic extension of classical imperative programs. Lexicographic ranking functions provide a sound and practical approach for termination of non-probabilistic programs, and their extension to probabilistic programs is achieved via lexicographic ranking supermartingales (LexRSMs). However, LexRSMs introduced in the previous work have a limitation that impedes their automation: all of their components have to be non-negative in all reachable states. This might result in LexRSM not existing even for simple terminating programs. Our contributions are twofold: First, we introduce a generalization of LexRSMs which allows for some components to be negative. This standard feature of non-probabilistic termination proofs was hitherto not known to be sound in the probabilistic setting, as the soundness proof requires a careful analysis of the underlying stochastic process. Second, we present polynomial-time algorithms using our generalized LexRSMs for proving a.s. termination in broad classes of linear-arithmetic programs.}, author = {Chatterjee, Krishnendu and Kafshdar Goharshadi, Ehsan and Novotný, Petr and Zárevúcky, Jiří and Zikelic, Dorde}, booktitle = {24th International Symposium on Formal Methods}, isbn = {9-783-0309-0869-0}, issn = {1611-3349}, location = {Virtual}, pages = {619--639}, publisher = {Springer Nature}, title = {{On lexicographic proof rules for probabilistic termination}}, doi = {10.1007/978-3-030-90870-6_33}, volume = {13047}, year = {2021}, } @book{10415, abstract = {The Hardy–Littlewood circle method was invented over a century ago to study integer solutions to special Diophantine equations, but it has since proven to be one of the most successful all-purpose tools available to number theorists. Not only is it capable of handling remarkably general systems of polynomial equations defined over arbitrary global fields, but it can also shed light on the space of rational curves that lie on algebraic varieties. This book, in which the arithmetic of cubic polynomials takes centre stage, is aimed at bringing beginning graduate students into contact with some of the many facets of the circle method, both classical and modern. This monograph is the winner of the 2021 Ferran Sunyer i Balaguer Prize, a prestigious award for books of expository nature presenting the latest developments in an active area of research in mathematics.}, author = {Browning, Timothy D}, isbn = {978-3-030-86871-0}, issn = {2296-505X}, pages = {XIV, 166}, publisher = {Springer Nature}, title = {{Cubic Forms and the Circle Method}}, doi = {10.1007/978-3-030-86872-7}, volume = {343}, year = {2021}, } @phdthesis{10422, abstract = {Those who aim to devise new materials with desirable properties usually examine present methods first. However, they will find out that some approaches can exist only conceptually without high chances to become practically useful. It seems that a numerical technique called automatic differentiation together with increasing supply of computational accelerators will soon shift many methods of the material design from the category ”unimaginable” to the category ”expensive but possible”. Approach we suggest is not an exception. Our overall goal is to have an efficient and generalizable approach allowing to solve inverse design problems. In this thesis we scratch its surface. We consider jammed systems of identical particles. And ask ourselves how the shape of those particles (or the parameters codifying it) may affect mechanical properties of the system. An indispensable part of reaching the answer is an appropriate particle parametrization. We come up with a simple, yet generalizable and purposeful scheme for it. Using our generalizable shape parameterization, we simulate the formation of a solid composed of pentagonal-like particles and measure anisotropy in the resulting elastic response. Through automatic differentiation techniques, we directly connect the shape parameters with the elastic response. Interestingly, for our system we find that less isotropic particles lead to a more isotropic elastic response. Together with other results known about our method it seems that it can be successfully generalized for different inverse design problems.}, author = {Piankov, Anton}, issn = {2791-4585}, publisher = {Institute of Science and Technology Austria}, title = {{Towards designer materials using customizable particle shape}}, doi = {10.15479/at:ista:10422}, year = {2021}, } @inproceedings{10435, abstract = {Decentralized optimization is emerging as a viable alternative for scalable distributed machine learning, but also introduces new challenges in terms of synchronization costs. To this end, several communication-reduction techniques, such as non-blocking communication, quantization, and local steps, have been explored in the decentralized setting. Due to the complexity of analyzing optimization in such a relaxed setting, this line of work often assumes \emph{global} communication rounds, which require additional synchronization. In this paper, we consider decentralized optimization in the simpler, but harder to analyze, \emph{asynchronous gossip} model, in which communication occurs in discrete, randomly chosen pairings among nodes. Perhaps surprisingly, we show that a variant of SGD called \emph{SwarmSGD} still converges in this setting, even if \emph{non-blocking communication}, \emph{quantization}, and \emph{local steps} are all applied \emph{in conjunction}, and even if the node data distributions and underlying graph topology are both \emph{heterogenous}. Our analysis is based on a new connection with multi-dimensional load-balancing processes. We implement this algorithm and deploy it in a super-computing environment, showing that it can outperform previous decentralized methods in terms of end-to-end training time, and that it can even rival carefully-tuned large-batch SGD for certain tasks.}, author = {Nadiradze, Giorgi and Sabour, Amirmojtaba and Davies, Peter and Li, Shigang and Alistarh, Dan-Adrian}, booktitle = {35th Conference on Neural Information Processing Systems}, location = {Sydney, Australia}, publisher = {Neural Information Processing Systems Foundation}, title = {{Asynchronous decentralized SGD with quantized and local updates}}, year = {2021}, } @article{10527, abstract = {We show that in a two-dimensional electron gas with an annular Fermi surface, long-range Coulomb interactions can lead to unconventional superconductivity by the Kohn-Luttinger mechanism. Superconductivity is strongly enhanced when the inner and outer Fermi surfaces are close to each other. The most prevalent state has chiral p-wave symmetry, but d-wave and extended s-wave pairing are also possible. We discuss these results in the context of rhombohedral trilayer graphene, where superconductivity was recently discovered in regimes where the normal state has an annular Fermi surface. Using realistic parameters, our mechanism can account for the order of magnitude of Tc, as well as its trends as a function of electron density and perpendicular displacement field. Moreover, it naturally explains some of the outstanding puzzles in this material, that include the weak temperature dependence of the resistivity above Tc, and the proximity of spin singlet superconductivity to the ferromagnetic phase.}, author = {Ghazaryan, Areg and Holder, Tobias and Serbyn, Maksym and Berg, Erez}, issn = {1079-7114}, journal = {Physical Review Letters}, keywords = {general physics and astronomy}, number = {24}, publisher = {American Physical Society}, title = {{Unconventional superconductivity in systems with annular Fermi surfaces: Application to rhombohedral trilayer graphene}}, doi = {10.1103/physrevlett.127.247001}, volume = {127}, year = {2021}, } @article{10533, abstract = {Flowering plants utilize small RNA molecules to guide DNA methyltransferases to genomic sequences. This RNA-directed DNA methylation (RdDM) pathway preferentially targets euchromatic transposable elements. However, RdDM is thought to be recruited by methylation of histone H3 at lysine 9 (H3K9me), a hallmark of heterochromatin. How RdDM is targeted to euchromatin despite an affinity for H3K9me is unclear. Here we show that loss of histone H1 enhances heterochromatic RdDM, preferentially at nucleosome linker DNA. Surprisingly, this does not require SHH1, the RdDM component that binds H3K9me. Furthermore, H3K9me is dispensable for RdDM, as is CG DNA methylation. Instead, we find that non-CG methylation is specifically associated with small RNA biogenesis, and without H1 small RNA production quantitatively expands to non-CG methylated loci. Our results demonstrate that H1 enforces the separation of euchromatic and heterochromatic DNA methylation pathways by excluding the small RNA-generating branch of RdDM from non-CG methylated heterochromatin.}, author = {Choi, Jaemyung and Lyons, David B and Zilberman, Daniel}, issn = {2050-084X}, journal = {eLife}, keywords = {genetics and molecular biology}, publisher = {eLife Sciences Publications}, title = {{Histone H1 prevents non-CG methylation-mediated small RNA biogenesis in Arabidopsis heterochromatin}}, doi = {10.7554/elife.72676}, volume = {10}, year = {2021}, } @article{10534, abstract = {For many years, fullerene derivatives have been the main n-type material of organic electronics and optoelectronics. Recently, fullerene derivatives functionalized with ethylene glycol (EG) side chains have been showing important properties such as enhanced dielectric constants, facile doping and enhanced self-assembly capabilities. Here, we have prepared field-effect transistors using a series of these fullerene derivatives equipped with EG side chains of different lengths. Transport data show the beneficial effect of increasing the EG side chain. In order to understand the material properties, full structural determination of these fullerene derivatives has been achieved by coupling the X-ray data with molecular dynamics (MD) simulations. The increase in transport properties is paired with the formation of extended layered structures, efficient molecular packing and an increase in the crystallite alignment. The layer-like structure is composed of conducting layers, containing of closely packed C60 balls approaching the inter-distance of 1 nm, that are separated by well-defined EG layers, where the EG chains are rather splayed with the chain direction almost perpendicular to the layer normal. Such a layered structure appears highly ordered and highly aligned with the C60 planes oriented parallel to the substrate in the thin film configuration. The order inside the thin film increases with the EG chain length, allowing the systems to achieve mobilities as high as 0.053 cm2 V−1 s−1. Our work elucidates the structure of these interesting semiconducting organic molecules and shows that the synergistic use of X-ray structural analysis and MD simulations is a powerful tool to identify the structure of thin organic films for optoelectronic applications.}, author = {Dong, Jingjin and Sami, Selim and Balazs, Daniel and Alessandri, Riccardo and Jahani, Fatimeh and Qiu, Li and Marrink, Siewert J. and Havenith, Remco W.A. and Hummelen, Jan C. and Loi, Maria A. and Portale, Giuseppe}, issn = {2050-7526}, journal = {Journal of Materials Chemistry C}, number = {45}, pages = {16217--16225}, publisher = {Royal Society of Chemistry}, title = {{Fullerene derivatives with oligoethylene-glycol side chains: An investigation on the origin of their outstanding transport properties}}, doi = {10.1039/d1tc02753k}, volume = {9}, year = {2021}, } @article{10535, abstract = {Realistic models of biological processes typically involve interacting components on multiple scales, driven by changing environment and inherent stochasticity. Such models are often analytically and numerically intractable. We revisit a dynamic maximum entropy method that combines a static maximum entropy with a quasi-stationary approximation. This allows us to reduce stochastic non-equilibrium dynamics expressed by the Fokker-Planck equation to a simpler low-dimensional deterministic dynamics, without the need to track microscopic details. Although the method has been previously applied to a few (rather complicated) applications in population genetics, our main goal here is to explain and to better understand how the method works. We demonstrate the usefulness of the method for two widely studied stochastic problems, highlighting its accuracy in capturing important macroscopic quantities even in rapidly changing non-stationary conditions. For the Ornstein-Uhlenbeck process, the method recovers the exact dynamics whilst for a stochastic island model with migration from other habitats, the approximation retains high macroscopic accuracy under a wide range of scenarios in a dynamic environment.}, author = {Bod'ová, Katarína and Szep, Eniko and Barton, Nicholas H}, issn = {1553-7358}, journal = {PLoS Computational Biology}, number = {12}, publisher = {Public Library of Science}, title = {{Dynamic maximum entropy provides accurate approximation of structured population dynamics}}, doi = {10.1371/journal.pcbi.1009661}, volume = {17}, year = {2021}, } @article{10536, abstract = {TGFβ overexpression is commonly detected in cancer patients and correlates with poor prognosis and metastasis. Cancer progression is often associated with an enhanced recruitment of myeloid-derived cells to the tumor microenvironment. Here we show that functional TGFβ-signaling in myeloid cells is required for metastasis to the lungs and the liver. Myeloid-specific deletion of Tgfbr2 resulted in reduced spontaneous lung metastasis, which was associated with a reduction of proinflammatory cytokines in the metastatic microenvironment. Notably, CD8+ T cell depletion in myeloid-specific Tgfbr2-deficient mice rescued lung metastasis. Myeloid-specific Tgfbr2-deficiency resulted in reduced liver metastasis with an almost complete absence of myeloid cells within metastatic foci. On contrary, an accumulation of Tgfβ-responsive myeloid cells was associated with an increased recruitment of monocytes and granulocytes and higher proinflammatory cytokine levels in control mice. Monocytic cells isolated from metastatic livers of Tgfbr2-deficient mice showed increased polarization towards the M1 phenotype, Tnfα and Il-1β expression, reduced levels of M2 markers and reduced production of chemokines responsible for myeloid-cell recruitment. No significant differences in Tgfβ levels were observed at metastatic sites of any model. These data demonstrate that Tgfβ signaling in monocytic myeloid cells suppresses CD8+ T cell activity during lung metastasis, while these cells actively contribute to tumor growth during liver metastasis. Thus, myeloid cells modulate metastasis through different mechanisms in a tissue-specific manner.}, author = {Stefanescu, Cristina and Van Gogh, Merel and Roblek, Marko and Heikenwalder, Mathias and Borsig, Lubor}, issn = {2234-943X}, journal = {Frontiers in Oncology}, publisher = {Frontiers}, title = {{TGFβ signaling in myeloid cells promotes lung and liver metastasis through different mechanisms}}, doi = {10.3389/fonc.2021.765151}, volume = {11}, year = {2021}, } @article{10549, abstract = {We derive optimal-order homogenization rates for random nonlinear elliptic PDEs with monotone nonlinearity in the uniformly elliptic case. More precisely, for a random monotone operator on \mathbb {R}^d with stationary law (that is spatially homogeneous statistics) and fast decay of correlations on scales larger than the microscale \varepsilon >0, we establish homogenization error estimates of the order \varepsilon in case d\geqq 3, and of the order \varepsilon |\log \varepsilon |^{1/2} in case d=2. Previous results in nonlinear stochastic homogenization have been limited to a small algebraic rate of convergence \varepsilon ^\delta . We also establish error estimates for the approximation of the homogenized operator by the method of representative volumes of the order (L/\varepsilon )^{-d/2} for a representative volume of size L. Our results also hold in the case of systems for which a (small-scale) C^{1,\alpha } regularity theory is available.}, author = {Fischer, Julian L and Neukamm, Stefan}, issn = {1432-0673}, journal = {Archive for Rational Mechanics and Analysis}, keywords = {Mechanical Engineering, Mathematics (miscellaneous), Analysis}, number = {1}, pages = {343--452}, publisher = {Springer Nature}, title = {{Optimal homogenization rates in stochastic homogenization of nonlinear uniformly elliptic equations and systems}}, doi = {10.1007/s00205-021-01686-9}, volume = {242}, year = {2021}, } @inproceedings{10552, abstract = {We study a class of convex-concave saddle-point problems of the form minxmaxy⟨Kx,y⟩+fP(x)−h∗(y) where K is a linear operator, fP is the sum of a convex function f with a Lipschitz-continuous gradient and the indicator function of a bounded convex polytope P, and h∗ is a convex (possibly nonsmooth) function. Such problem arises, for example, as a Lagrangian relaxation of various discrete optimization problems. Our main assumptions are the existence of an efficient linear minimization oracle (lmo) for fP and an efficient proximal map for h∗ which motivate the solution via a blend of proximal primal-dual algorithms and Frank-Wolfe algorithms. In case h∗ is the indicator function of a linear constraint and function f is quadratic, we show a O(1/n2) convergence rate on the dual objective, requiring O(nlogn) calls of lmo. If the problem comes from the constrained optimization problem minx∈Rd{fP(x)|Ax−b=0} then we additionally get bound O(1/n2) both on the primal gap and on the infeasibility gap. In the most general case, we show a O(1/n) convergence rate of the primal-dual gap again requiring O(nlogn) calls of lmo. To the best of our knowledge, this improves on the known convergence rates for the considered class of saddle-point problems. We show applications to labeling problems frequently appearing in machine learning and computer vision.}, author = {Kolmogorov, Vladimir and Pock, Thomas}, booktitle = {38th International Conference on Machine Learning}, location = {Virtual}, title = {{One-sided Frank-Wolfe algorithms for saddle problems}}, year = {2021}, } @inproceedings{10553, abstract = {The popularity of permissioned blockchain systems demands BFT SMR protocols that are efficient under good network conditions (synchrony) and robust under bad network conditions (asynchrony). The state-of-the-art partially synchronous BFT SMR protocols provide optimal linear communication cost per decision under synchrony and good leaders, but lose liveness under asynchrony. On the other hand, the state-of-the-art asynchronous BFT SMR protocols are live even under asynchrony, but always pay quadratic cost even under synchrony. In this paper, we propose a BFT SMR protocol that achieves the best of both worlds -- optimal linear cost per decision under good networks and leaders, optimal quadratic cost per decision under bad networks, and remains always live.}, author = {Gelashvili, Rati and Kokoris Kogias, Eleftherios and Spiegelman, Alexander and Xiang, Zhuolun}, booktitle = {Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing}, isbn = {9-781-4503-8548-0}, keywords = {optimal, state machine replication, fallback, asynchrony, byzantine faults}, location = {Virtual, Italy}, pages = {187--190}, publisher = {Association for Computing Machinery}, title = {{Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol}}, doi = {10.1145/3465084.3467941}, year = {2021}, } @inproceedings{10554, abstract = {We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all values proposed by correct processes eventually get delivered. We construct DAG-Rider in two layers: In the first layer, processes reliably broadcast their proposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication.}, author = {Keidar, Idit and Kokoris Kogias, Eleftherios and Naor, Oded and Spiegelman, Alexander}, booktitle = {Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing}, isbn = {978-1-4503-8548-0}, location = {Virtual, Italy}, pages = {165--175}, publisher = {Association for Computing Machinery}, title = {{All You Need is DAG}}, doi = {10.1145/3465084.3467905}, year = {2021}, }