@article{10537, abstract = {We consider the quantum many-body evolution of a homogeneous Fermi gas in three dimensions in the coupled semiclassical and mean-field scaling regime. We study a class of initial data describing collective particle–hole pair excitations on the Fermi ball. Using a rigorous version of approximate bosonization, we prove that the many-body evolution can be approximated in Fock space norm by a quasi-free bosonic evolution of the collective particle–hole excitations.}, author = {Benedikter, Niels P and Nam, Phan Thành and Porta, Marcello and Schlein, Benjamin and Seiringer, Robert}, issn = {1424-0637}, journal = {Annales Henri Poincaré}, publisher = {Springer Nature}, title = {{Bosonization of fermionic many-body dynamics}}, doi = {10.1007/s00023-021-01136-y}, 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{10409, abstract = {We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a SO(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(δwlog(S)) , δ being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity. with only a SO(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(δwlog(S)) , δ being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.}, author = {Kamath Hosdurg, Chethan and Klein, Karen and Pietrzak, Krzysztof Z}, booktitle = {19th International Conference}, isbn = {9-783-0309-0452-4}, issn = {1611-3349}, location = {Raleigh, NC, United States}, pages = {486--517}, publisher = {Springer Nature}, title = {{On treewidth, separators and Yao’s garbling}}, doi = {10.1007/978-3-030-90453-1_17}, volume = {13043 }, year = {2021}, } @article{10545, abstract = {Classical models with complex energy landscapes represent a perspective avenue for the near-term application of quantum simulators. Until now, many theoretical works studied the performance of quantum algorithms for models with a unique ground state. However, when the classical problem is in a so-called clustering phase, the ground state manifold is highly degenerate. As an example, we consider a 3-XORSAT model defined on simple hypergraphs. The degeneracy of classical ground state manifold translates into the emergence of an extensive number of Z2 symmetries, which remain intact even in the presence of a quantum transverse magnetic field. We establish a general duality approach that restricts the quantum problem to a given sector of conserved Z2 charges and use it to study how the outcome of the quantum adiabatic algorithm depends on the hypergraph geometry. We show that the tree hypergraph which corresponds to a classically solvable instance of the 3-XORSAT problem features a constant gap, whereas the closed hypergraph encounters a second-order phase transition with a gap vanishing as a power-law in the problem size. The duality developed in this work provides a practical tool for studies of quantum models with classically degenerate energy manifold and reveals potential connections between glasses and gauge theories.}, author = {Medina Ramos, Raimel A and Serbyn, Maksym}, issn = {2469-9934}, journal = {Physical Review A}, number = {6}, publisher = {American Physical Society}, title = {{Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT)}}, doi = {10.1103/physreva.104.062423}, volume = {104}, 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}, }