@article{10574, abstract = {The understanding of material appearance perception is a complex problem due to interactions between material reflectance, surface geometry, and illumination. Recently, Serrano et al. collected the largest dataset to date with subjective ratings of material appearance attributes, including glossiness, metallicness, sharpness and contrast of reflections. In this work, we make use of their dataset to investigate for the first time the impact of the interactions between illumination, geometry, and eight different material categories in perceived appearance attributes. After an initial analysis, we select for further analysis the four material categories that cover the largest range for all perceptual attributes: fabric, plastic, ceramic, and metal. Using a cumulative link mixed model (CLMM) for robust regression, we discover interactions between these material categories and four representative illuminations and object geometries. We believe that our findings contribute to expanding the knowledge on material appearance perception and can be useful for many applications, such as scene design, where any particular material in a given shape can be aligned with dominant classes of illumination, so that a desired strength of appearance attributes can be achieved.}, author = {Chen, Bin and Wang, Chao and Piovarci, Michael and Seidel, Hans Peter and Didyk, Piotr and Myszkowski, Karol and Serrano, Ana}, issn = {1432-2315}, journal = {Visual Computer}, number = {12}, pages = {2975--2987}, publisher = {Springer Nature}, title = {{The effect of geometry and illumination on appearance perception of different material categories}}, doi = {10.1007/s00371-021-02227-x}, volume = {37}, year = {2021}, } @article{10575, abstract = {The choice of the boundary conditions in mechanical problems has to reflect the interaction of the considered material with the surface. Still the assumption of the no-slip condition is preferred in order to avoid boundary terms in the analysis and slipping effects are usually overlooked. Besides the “static slip models”, there are phenomena that are not accurately described by them, e.g. at the moment when the slip changes rapidly, the wall shear stress and the slip can exhibit a sudden overshoot and subsequent relaxation. When these effects become significant, the so-called dynamic slip phenomenon occurs. We develop a mathematical analysis of Navier–Stokes-like problems with a dynamic slip boundary condition, which requires a proper generalization of the Gelfand triplet and the corresponding function space setting.}, author = {Abbatiello, Anna and Bulíček, Miroslav and Maringová, Erika}, issn = {1793-6314}, journal = {Mathematical Models and Methods in Applied Sciences}, number = {11}, pages = {2165--2212}, publisher = {World Scientific Publishing}, title = {{On the dynamic slip boundary condition for Navier-Stokes-like problems}}, doi = {10.1142/S0218202521500470}, volume = {31}, year = {2021}, } @unpublished{10579, abstract = {We consider a totally asymmetric simple exclusion process (TASEP) consisting of particles on a lattice that require binding by a "token" to move. Using a combination of theory and simulations, we address the following questions: (i) How token binding kinetics affects the current-density relation; (ii) How the current-density relation depends on the scarcity of tokens; (iii) How tokens propagate the effects of the locally-imposed disorder (such a slow site) over the entire lattice; (iv) How a shared pool of tokens couples concurrent TASEPs running on multiple lattices; (v) How our results translate to TASEPs with open boundaries that exchange particles with the reservoir. Since real particle motion (including in systems that inspired the standard TASEP model, e.g., protein synthesis or movement of molecular motors) is often catalyzed, regulated, actuated, or otherwise mediated, the token-driven TASEP dynamics analyzed in this paper should allow for a better understanding of real systems and enable a closer match between TASEP theory and experimental observations.}, author = {Kavcic, Bor and Tkačik, Gašper}, booktitle = {arXiv}, title = {{Token-driven totally asymmetric simple exclusion process}}, doi = {10.48550/arXiv.2112.13558}, year = {2021}, } @article{10585, abstract = {Recently it was shown that anyons on the two-sphere naturally arise from a system of molecular impurities exchanging angular momentum with a many-particle bath (Phys. Rev. Lett. 126, 015301 (2021)). Here we further advance this approach and rigorously demonstrate that in the experimentally realized regime the lowest spectrum of two linear molecules immersed in superfluid helium corresponds to the spectrum of two anyons on the sphere. We develop the formalism within the framework of the recently experimentally observed angulon quasiparticle}, author = {Brooks, Morris and Lemeshko, Mikhail and Lundholm, Douglas and Yakaboylu, Enderalp}, issn = {2218-2004}, journal = {Atoms}, keywords = {anyons, quasiparticles, Quantum Hall Effect, topological states of matter}, number = {4}, publisher = {MDPI}, title = {{Emergence of anyons on the two-sphere in molecular impurities}}, doi = {10.3390/atoms9040106}, volume = {9}, year = {2021}, } @article{10586, abstract = {A facile approach for developing an interfacial solar evaporator by heat localization of solar-thermal energy conversion at water-air liquid composed by in-situ polymerization of Fe2O3 nanoparticles (Fe2O3@PPy) deposited over a facial sponge is proposed. The demonstrated system consists of a floating solar receiver having a vertically cross-linked microchannel for wicking up saline water. The in situ polymerized Fe2O3@PPy interfacial layer promotes diffuse reflection and its rough black surface allows Omni-directional solar absorption (94%) and facilitates efficient thermal localization at the water/air interface and offers a defect-rich surface to promote heat localization (41.9 °C) and excellent thermal management due to cellulosic content. The self-floating composite foam reveals continuous vapors generation at a rate of 1.52 kg m−2 h−1 under one 1 kW m−2 and profound evaporating efficiency (95%) without heat losses that dissipates in its surroundings. Indeed, long-term evaporation experiments reveal the negligible disparity in continuous evaporation rate (33.84 kg m−2/8.3 h) receiving two sun solar intensity, and ensures the stability of the device under intense seawater conditions synchronized with excellent salt rejection potential. More importantly, Raman spectroscopy investigation validates the orange dye rejection via Fe2O3@PPy solar evaporator. The combined advantages of high efficiency, self-floating capability, multimedia rejection, low cost, and this configuration are promising for producing large-scale solar steam generating systems appropriate for commercial clean water yield due to their scalable fabrication.}, author = {Lu, Yuzheng and Arshad, Naila and Irshad, Muhammad Sultan and Ahmed, Iftikhar and Ahmad, Shafiq and Alshahrani, Lina Abdullah and Yousaf, Muhammad and Sayed, Abdelaty Edrees and Nauman, Muhammad}, issn = {2073-4352}, journal = {Crystals}, number = {12}, publisher = {MDPI}, title = {{Fe2O3 nanoparticles deposited over self-floating facial sponge for facile interfacial seawater solar desalination}}, doi = {10.3390/cryst11121509}, volume = {11}, year = {2021}, } @inproceedings{10593, abstract = {We study the problem of estimating a rank-$1$ signal in the presence of rotationally invariant noise-a class of perturbations more general than Gaussian noise. Principal Component Analysis (PCA) provides a natural estimator, and sharp results on its performance have been obtained in the high-dimensional regime. Recently, an Approximate Message Passing (AMP) algorithm has been proposed as an alternative estimator with the potential to improve the accuracy of PCA. However, the existing analysis of AMP requires an initialization that is both correlated with the signal and independent of the noise, which is often unrealistic in practice. In this work, we combine the two methods, and propose to initialize AMP with PCA. Our main result is a rigorous asymptotic characterization of the performance of this estimator. Both the AMP algorithm and its analysis differ from those previously derived in the Gaussian setting: at every iteration, our AMP algorithm requires a specific term to account for PCA initialization, while in the Gaussian case, PCA initialization affects only the first iteration of AMP. The proof is based on a two-phase artificial AMP that first approximates the PCA estimator and then mimics the true AMP. Our numerical simulations show an excellent agreement between AMP results and theoretical predictions, and suggest an interesting open direction on achieving Bayes-optimal performance.}, author = {Mondelli, Marco and Venkataramanan, Ramji}, booktitle = {35th Conference on Neural Information Processing Systems}, isbn = {9781713845393}, issn = {1049-5258}, location = {Virtual}, pages = {29616--29629}, publisher = {Neural Information Processing Systems Foundation}, title = {{PCA initialization for approximate message passing in rotationally invariant models}}, volume = {35}, year = {2021}, } @inproceedings{10594, abstract = {The question of how and why the phenomenon of mode connectivity occurs in training deep neural networks has gained remarkable attention in the research community. From a theoretical perspective, two possible explanations have been proposed: (i) the loss function has connected sublevel sets, and (ii) the solutions found by stochastic gradient descent are dropout stable. While these explanations provide insights into the phenomenon, their assumptions are not always satisfied in practice. In particular, the first approach requires the network to have one layer with order of N neurons (N being the number of training samples), while the second one requires the loss to be almost invariant after removing half of the neurons at each layer (up to some rescaling of the remaining ones). In this work, we improve both conditions by exploiting the quality of the features at every intermediate layer together with a milder over-parameterization condition. More specifically, we show that: (i) under generic assumptions on the features of intermediate layers, it suffices that the last two hidden layers have order of N−−√ neurons, and (ii) if subsets of features at each layer are linearly separable, then no over-parameterization is needed to show the connectivity. Our experiments confirm that the proposed condition ensures the connectivity of solutions found by stochastic gradient descent, even in settings where the previous requirements do not hold.}, author = {Nguyen, Quynh and Bréchet, Pierre and Mondelli, Marco}, booktitle = {35th Conference on Neural Information Processing Systems}, isbn = {9781713845393}, issn = {1049-5258}, location = {Virtual}, publisher = {Neural Information Processing Systems Foundation}, title = {{When are solutions connected in deep networks?}}, volume = {35}, year = {2021}, } @inproceedings{10595, abstract = {A recent line of work has analyzed the theoretical properties of deep neural networks via the Neural Tangent Kernel (NTK). In particular, the smallest eigenvalue of the NTK has been related to the memorization capacity, the global convergence of gradient descent algorithms and the generalization of deep nets. However, existing results either provide bounds in the two-layer setting or assume that the spectrum of the NTK matrices is bounded away from 0 for multi-layer networks. In this paper, we provide tight bounds on the smallest eigenvalue of NTK matrices for deep ReLU nets, both in the limiting case of infinite widths and for finite widths. In the finite-width setting, the network architectures we consider are fairly general: we require the existence of a wide layer with roughly order of $N$ neurons, $N$ being the number of data samples; and the scaling of the remaining layer widths is arbitrary (up to logarithmic factors). To obtain our results, we analyze various quantities of independent interest: we give lower bounds on the smallest singular value of hidden feature matrices, and upper bounds on the Lipschitz constant of input-output feature maps.}, author = {Nguyen, Quynh and Mondelli, Marco and Montufar, Guido F}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, editor = {Meila, Marina and Zhang, Tong}, location = {Virtual}, pages = {8119--8129}, publisher = {ML Research Press}, title = {{Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks}}, volume = {139}, year = {2021}, } @inproceedings{10597, abstract = {We thank Emmanuel Abbe and Min Ye for providing us the implementation of RPA decoding. D. Fathollahi and M. Mondelli are partially supported by the 2019 Lopez-Loreta Prize. N. Farsad is supported by Discovery Grant from the Natural Sciences and Engineering Research Council of Canada (NSERC) and Canada Foundation for Innovation (CFI), John R. Evans Leader Fund. S. A. Hashemi is supported by a Postdoctoral Fellowship from NSERC.}, author = {Fathollahi, Dorsa and Farsad, Nariman and Hashemi, Seyyed Ali and Mondelli, Marco}, booktitle = {2021 IEEE International Symposium on Information Theory}, isbn = {978-1-5386-8210-4}, location = {Virtual, Melbourne, Australia}, pages = {1082--1087}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Sparse multi-decoder recursive projection aggregation for Reed-Muller codes}}, doi = {10.1109/isit45174.2021.9517887}, year = {2021}, } @inproceedings{10598, abstract = { We consider the problem of estimating a signal from measurements obtained via a generalized linear model. We focus on estimators based on approximate message passing (AMP), a family of iterative algorithms with many appealing features: the performance of AMP in the high-dimensional limit can be succinctly characterized under suitable model assumptions; AMP can also be tailored to the empirical distribution of the signal entries, and for a wide class of estimation problems, AMP is conjectured to be optimal among all polynomial-time algorithms. However, a major issue of AMP is that in many models (such as phase retrieval), it requires an initialization correlated with the ground-truth signal and independent from the measurement matrix. Assuming that such an initialization is available is typically not realistic. In this paper, we solve this problem by proposing an AMP algorithm initialized with a spectral estimator. With such an initialization, the standard AMP analysis fails since the spectral estimator depends in a complicated way on the design matrix. Our main contribution is a rigorous characterization of the performance of AMP with spectral initialization in the high-dimensional limit. The key technical idea is to define and analyze a two-phase artificial AMP algorithm that first produces the spectral estimator, and then closely approximates the iterates of the true AMP. We also provide numerical results that demonstrate the validity of the proposed approach. }, author = {Mondelli, Marco and Venkataramanan, Ramji}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, issn = {2640-3498}, location = {Virtual, San Diego, CA, United States}, pages = {397--405}, publisher = {ML Research Press}, title = {{Approximate message passing with spectral initialization for generalized linear models}}, volume = {130}, year = {2021}, } @inproceedings{10599, abstract = {A two-part successive syndrome-check decoding of polar codes is proposed with the first part successively refining the received codeword and the second part checking its syndrome. A new formulation of the successive-cancellation (SC) decoding algorithm is presented that allows for successively refining the received codeword by comparing the log-likelihood ratio value of a frozen bit with its predefined value. The syndrome of the refined received codeword is then checked for possible errors. In case there are no errors, the decoding process is terminated. Otherwise, the decoder continues to refine the received codeword. The proposed method is extended to the case of SC list (SCL) decoding by terminating the decoding process when the syndrome of the best candidate in the list indicates no errors. Simulation results show that the proposed method reduces the time-complexity of SC and SCL decoders and their fast variants, especially at high signal-to-noise ratios.}, author = {Hashemi, Seyyed Ali and Mondelli, Marco and Cioffi, John and Goldsmith, Andrea}, booktitle = {Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers}, isbn = {9781665458283}, issn = {1058-6393}, location = {Virtual, Pacific Grove, CA, United States}, pages = {943--947}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Successive syndrome-check decoding of polar codes}}, doi = {10.1109/IEEECONF53345.2021.9723394}, volume = {2021-October}, year = {2021}, } @article{10606, abstract = {Cell division orientation is thought to result from a competition between cell geometry and polarity domains controlling the position of the mitotic spindle during mitosis. Depending on the level of cell shape anisotropy or the strength of the polarity domain, one dominates the other and determines the orientation of the spindle. Whether and how such competition is also at work to determine unequal cell division (UCD), producing daughter cells of different size, remains unclear. Here, we show that cell geometry and polarity domains cooperate, rather than compete, in positioning the cleavage plane during UCDs in early ascidian embryos. We found that the UCDs and their orientation at the ascidian third cleavage rely on the spindle tilting in an anisotropic cell shape, and cortical polarity domains exerting different effects on spindle astral microtubules. By systematically varying mitotic cell shape, we could modulate the effect of attractive and repulsive polarity domains and consequently generate predicted daughter cell size asymmetries and position. We therefore propose that the spindle position during UCD is set by the combined activities of cell geometry and polarity domains, where cell geometry modulates the effect of cortical polarity domain(s).}, author = {Godard, Benoit G and Dumollard, Remi and Heisenberg, Carl-Philipp J and Mcdougall, Alex}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{Combined effect of cell geometry and polarity domains determines the orientation of unequal division}}, doi = {10.7554/eLife.75639}, volume = {10}, year = {2021}, } @article{10608, abstract = {We consider infinite-dimensional properties in coarse geometry for hyperspaces consisting of finite subsets of metric spaces with the Hausdorff metric. We see that several infinite-dimensional properties are preserved by taking the hyperspace of subsets with at most n points. On the other hand, we prove that, if a metric space contains a sequence of long intervals coarsely, then its hyperspace of finite subsets is not coarsely embeddable into any uniformly convex Banach space. As a corollary, the hyperspace of finite subsets of the real line is not coarsely embeddable into any uniformly convex Banach space. It is also shown that every (not necessarily bounded geometry) metric space with straight finite decomposition complexity has metric sparsification property.}, author = {Weighill, Thomas and Yamauchi, Takamitsu and Zava, Nicolò}, issn = {2199-6768}, journal = {European Journal of Mathematics}, publisher = {Springer Nature}, title = {{Coarse infinite-dimensionality of hyperspaces of finite subsets}}, doi = {10.1007/s40879-021-00515-3}, year = {2021}, } @inproceedings{10609, abstract = {We study Multi-party computation (MPC) in the setting of subversion, where the adversary tampers with the machines of honest parties. Our goal is to construct actively secure MPC protocols where parties are corrupted adaptively by an adversary (as in the standard adaptive security setting), and in addition, honest parties’ machines are compromised. The idea of reverse firewalls (RF) was introduced at EUROCRYPT’15 by Mironov and Stephens-Davidowitz as an approach to protecting protocols against corruption of honest parties’ devices. Intuitively, an RF for a party P is an external entity that sits between P and the outside world and whose scope is to sanitize P ’s incoming and outgoing messages in the face of subversion of their computer. Mironov and Stephens-Davidowitz constructed a protocol for passively-secure two-party computation. At CRYPTO’20, Chakraborty, Dziembowski and Nielsen constructed a protocol for secure computation with firewalls that improved on this result, both by extending it to multi-party computation protocol, and considering active security in the presence of static corruptions. In this paper, we initiate the study of RF for MPC in the adaptive setting. We put forward a definition for adaptively secure MPC in the reverse firewall setting, explore relationships among the security notions, and then construct reverse firewalls for MPC in this stronger setting of adaptive security. We also resolve the open question of Chakraborty, Dziembowski and Nielsen by removing the need for a trusted setup in constructing RF for MPC. Towards this end, we construct reverse firewalls for adaptively secure augmented coin tossing and adaptively secure zero-knowledge protocols and obtain a constant round adaptively secure MPC protocol in the reverse firewall setting without setup. Along the way, we propose a new multi-party adaptively secure coin tossing protocol in the plain model, that is of independent interest.}, author = {Chakraborty, Suvradip and Ganesh, Chaya and Pancholi, Mahak and Sarkar, Pratik}, booktitle = {27th International Conference on the Theory and Application of Cryptology and Information Security}, isbn = {978-3-030-92074-6}, issn = {1611-3349}, location = {Virtual, Singapore}, pages = {335--364}, publisher = {Springer Nature}, title = {{Reverse firewalls for adaptively secure MPC without setup}}, doi = {10.1007/978-3-030-92075-3_12}, volume = {13091}, year = {2021}, } @article{10613, abstract = {Motivated by the recent preprint [\emph{arXiv:2004.08412}] by Ayala, Carinci, and Redig, we first provide a general framework for the study of scaling limits of higher-order fields. Then, by considering the same class of infinite interacting particle systems as in [\emph{arXiv:2004.08412}], namely symmetric simple exclusion and inclusion processes in the d-dimensional Euclidean lattice, we prove the hydrodynamic limit, and convergence for the equilibrium fluctuations, of higher-order fields. In particular, the limit fields exhibit a tensor structure. Our fluctuation result differs from that in [\emph{arXiv:2004.08412}], since we considered-dimensional Euclidean lattice, we prove the hydrodynamic limit, and convergence for the equilibrium fluctuations, of higher-order fields. In particular, the limit fields exhibit a tensor structure. Our fluctuation result differs from that in [\emph{arXiv:2004.08412}], since we consider a different notion of higher-order fluctuation fields.}, author = {Chen, Joe P. and Sau, Federico}, issn = {1024-2953}, journal = {Markov Processes And Related Fields}, keywords = {interacting particle systems, higher-order fields, hydrodynamic limit, equilibrium fluctuations, duality}, number = {3}, pages = {339--380}, publisher = {Polymat Publishing}, title = {{Higher-order hydrodynamics and equilibrium fluctuations of interacting particle systems}}, volume = {27}, year = {2021}, } @article{10628, abstract = {The surface states of 3D topological insulators in general have negligible quantum oscillations (QOs) when the chemical potential is tuned to the Dirac points. In contrast, we find that topological Kondo insulators (TKIs) can support surface states with an arbitrarily large Fermi surface (FS) when the chemical potential is pinned to the Dirac point. We illustrate that these FSs give rise to finite-frequency QOs, which can become comparable to the extremal area of the unhybridized bulk bands. We show that this occurs when the crystal symmetry is lowered from cubic to tetragonal in a minimal two-orbital model. We label such surface modes as 'shadow surface states'. Moreover, we show that the sufficient next-nearest neighbor out-of-plane hybridization leading to shadow surface states can be self-consistently stabilized for tetragonal TKIs. Consequently, shadow surface states provide an important example of high-frequency QOs beyond the context of cubic TKIs.}, author = {Ghazaryan, Areg and Nica, Emilian M. and Erten, Onur and Ghaemi, Pouyan}, issn = {1367-2630}, journal = {New Journal of Physics}, number = {12}, publisher = {IOP Publishing}, title = {{Shadow surface states in topological Kondo insulators}}, doi = {10.1088/1367-2630/ac4124}, volume = {23}, year = {2021}, } @inproceedings{10629, abstract = {Product graphs arise naturally in formal verification and program analysis. For example, the analysis of two concurrent threads requires the product of two component control-flow graphs, and for language inclusion of deterministic automata the product of two automata is constructed. In many cases, the component graphs have constant treewidth, e.g., when the input contains control-flow graphs of programs. We consider the algorithmic analysis of products of two constant-treewidth graphs with respect to three classic specification languages, namely, (a) algebraic properties, (b) mean-payoff properties, and (c) initial credit for energy properties. Our main contributions are as follows. Consider a graph G that is the product of two constant-treewidth graphs of size n each. First, given an idempotent semiring, we present an algorithm that computes the semiring transitive closure of G in time Õ(n⁴). Since the output has size Θ(n⁴), our algorithm is optimal (up to polylog factors). Second, given a mean-payoff objective, we present an O(n³)-time algorithm for deciding whether the value of a starting state is non-negative, improving the previously known O(n⁴) bound. Third, given an initial credit for energy objective, we present an O(n⁵)-time algorithm for computing the minimum initial credit for all nodes of G, improving the previously known O(n⁸) bound. At the heart of our approach lies an algorithm for the efficient construction of strongly-balanced tree decompositions of constant-treewidth graphs. Given a constant-treewidth graph G' of n nodes and a positive integer λ, our algorithm constructs a binary tree decomposition of G' of width O(λ) with the property that the size of each subtree decreases geometrically with rate (1/2 + 2^{-λ}).}, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, isbn = {978-3-9597-7215-0}, issn = {1868-8969}, location = {Virtual}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Quantitative verification on product graphs of small treewidth}}, doi = {10.4230/LIPIcs.FSTTCS.2021.42}, volume = {213}, year = {2021}, } @inproceedings{10630, abstract = {In the Intersection Non-emptiness problem, we are given a list of finite automata A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine whether some string w ∈ Σ^* lies in the intersection of the languages accepted by the automata in the list. We analyze the complexity of the Intersection Non-emptiness problem under the promise that all input automata accept a language in some level of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy. Automata accepting languages from the lowest levels of these hierarchies arise naturally in the context of model checking. We identify a dichotomy in the dot-depth hierarchy by showing that the problem is already NP-complete when all input automata accept languages of the levels B_0 or B_{1/2} and already PSPACE-hard when all automata accept a language from the level B_1. Conversely, we identify a tetrachotomy in the Straubing-Thérien hierarchy. More precisely, we show that the problem is in AC^0 when restricted to level L_0; complete for L or NL, depending on the input representation, when restricted to languages in the level L_{1/2}; NP-complete when the input is given as DFAs accepting a language in L_1 or L_{3/2}; and finally, PSPACE-complete when the input automata accept languages in level L_2 or higher. Moreover, we show that the proof technique used to show containment in NP for DFAs accepting languages in L_1 or L_{3/2} does not generalize to the context of NFAs. To prove this, we identify a family of languages that provide an exponential separation between the state complexity of general NFAs and that of partially ordered NFAs. To the best of our knowledge, this is the first superpolynomial separation between these two models of computation.}, author = {Arrighi, Emmanuel and Fernau, Henning and Hoffmann, Stefan and Holzer, Markus and Jecker, Ismael R and De Oliveira Oliveira, Mateus and Wolf, Petra}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, isbn = {978-3-9597-7215-0}, issn = {1868-8969}, location = {Virtual}, publisher = {Schloss Dagstuhl - Leibniz Zentrum für Informatik}, title = {{On the complexity of intersection non-emptiness for star-free language classes}}, doi = {10.4230/LIPIcs.FSTTCS.2021.34}, volume = {213}, year = {2021}, } @article{10631, abstract = {We combine experimental and theoretical approaches to explore excited rotational states of molecules embedded in helium nanodroplets using CS2 and I2 as examples. Laser-induced nonadiabatic molecular alignment is employed to measure spectral lines for rotational states extending beyond those initially populated at the 0.37 K droplet temperature. We construct a simple quantum-mechanical model, based on a linear rotor coupled to a single-mode bosonic bath, to determine the rotational energy structure in its entirety. The calculated and measured spectral lines are in good agreement. We show that the effect of the surrounding superfluid on molecular rotation can be rationalized by a single quantity, the angular momentum, transferred from the molecule to the droplet.}, author = {Cherepanov, Igor and Bighin, Giacomo and Schouder, Constant A. and Chatterley, Adam S. and Albrechtsen, Simon H. and Muñoz, Alberto Viñas and Christiansen, Lars and Stapelfeldt, Henrik and Lemeshko, Mikhail}, issn = {2469-9934}, journal = {Physical Review A}, number = {6}, publisher = {American Physical Society}, title = {{Excited rotational states of molecules in a superfluid}}, doi = {10.1103/PhysRevA.104.L061303}, volume = {104}, year = {2021}, } @article{10635, abstract = {The brain efficiently performs nonlinear computations through its intricate networks of spiking neurons, but how this is done remains elusive. While nonlinear computations can be implemented successfully in spiking neural networks, this requires supervised training and the resulting connectivity can be hard to interpret. In contrast, the required connectivity for any computation in the form of a linear dynamical system can be directly derived and understood with the spike coding network (SCN) framework. These networks also have biologically realistic activity patterns and are highly robust to cell death. Here we extend the SCN framework to directly implement any polynomial dynamical system, without the need for training. This results in networks requiring a mix of synapse types (fast, slow, and multiplicative), which we term multiplicative spike coding networks (mSCNs). Using mSCNs, we demonstrate how to directly derive the required connectivity for several nonlinear dynamical systems. We also show how to carry out higher-order polynomials with coupled networks that use only pair-wise multiplicative synapses, and provide expected numbers of connections for each synapse type. Overall, our work demonstrates a novel method for implementing nonlinear computations in spiking neural networks, while keeping the attractive features of standard SCNs (robustness, realistic activity patterns, and interpretable connectivity). Finally, we discuss the biological plausibility of our approach, and how the high accuracy and robustness of the approach may be of interest for neuromorphic computing.}, author = {Nardin, Michele and Phillips, James W. and Podlaski, William F. and Keemink, Sander W.}, issn = {2804-3871}, journal = {Peer Community Journal}, publisher = {Centre Mersenne ; Peer Community In}, title = {{Nonlinear computations in spiking neural networks through multiplicative synapses}}, doi = {10.24072/pcjournal.69}, volume = {1}, year = {2021}, }