1. |
- De Rezende, Susanna F., et al.
(författare)
-
Automating algebraic proof systems is NP-hard
- 2021
-
Ingår i: STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. - New York, NY, USA : ACM. - 0737-8017. - 9781450380539 ; , s. 209-222
-
Konferensbidrag (refereegranskat)abstract
- We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is NP-hard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or Sherali-Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a simplified proof of, the recent breakthrough of Atserias and Müller (JACM 2020) that established an analogous result for Resolution.
|
|
2. |
- De Rezende, Susanna F., et al.
(författare)
-
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
- 2021
-
Ingår i: Computational Complexity. - : Springer Science and Business Media LLC. - 1016-3328 .- 1420-8954. ; 30:1
-
Tidskriftsartikel (refereegranskat)abstract
- We establish an exactly tight relation between reversiblepebblings of graphs and Nullstellensatz refutations of pebbling formulas,showing that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz refutation of the pebbling formulaover G in size t + 1 and degree s (independently of the field in whichthe Nullstellensatz refutation is made). We use this correspondenceto prove a number of strong size-degree trade-offs for Nullstellensatz,which to the best of our knowledge are the first such results for thisproof system.
|
|
3. |
- Wagner, Nils, et al.
(författare)
-
Deep learning-enhanced light-field imaging with continuous validation
- 2021
-
Ingår i: Nature Methods. - : Springer Science and Business Media LLC. - 1548-7105 .- 1548-7091. ; 18:5, s. 557-563
-
Tidskriftsartikel (refereegranskat)abstract
- Visualizing dynamic processes over large, three-dimensional fields of view at high speed is essential for many applications in the life sciences. Light-field microscopy (LFM) has emerged as a tool for fast volumetric image acquisition, but its effective throughput and widespread use in biology has been hampered by a computationally demanding and artifact-prone image reconstruction process. Here, we present a framework for artificial intelligence-enhanced microscopy, integrating a hybrid light-field light-sheet microscope and deep learning-based volume reconstruction. In our approach, concomitantly acquired, high-resolution two-dimensional light-sheet images continuously serve as training data and validation for the convolutional neural network reconstructing the raw LFM data during extended volumetric time-lapse imaging experiments. Our network delivers high-quality three-dimensional reconstructions at video-rate throughput, which can be further refined based on the high-resolution light-sheet images. We demonstrate the capabilities of our approach by imaging medaka heart dynamics and zebrafish neural activity with volumetric imaging rates up to 100 Hz.
|
|