![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
default search action
SIAM Journal on Computing, Volume 52
Volume 52, Number 1, February 2023
- Lorenzo Ciardo, Stanislav Zivný
:
CLAP: A New Algorithm for Promise CSPs. 1-37 - Andrei A. Krokhin
, Jakub Oprsal
, Marcin Wrochna
, Stanislav Zivný
:
Topology and Adjunction in Promise Constraint Satisfaction. 38-79 - Aris Filos-Ratsikas
, Yiannis Giannakopoulos
, Alexandros Hollender
, Philip Lazos
, Diogo Poças
:
On the Complexity of Equilibrium Computation in First-Price Auctions. 80-131 - Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Inapproximability of Matrix p → q Norms. 132-155 - Erin W. Chambers, Jeff Erickson, Kyle Fox, Amir Nayyeri:
Minimum Cuts in Surface Graphs. 156-195 - Zongchen Chen, Kuikui Liu, Eric Vigoda:
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. 196-237 - Martin Grohe, Daniel Neuen
, Daniel Wiebking:
Isomorphism Testing for Graphs Excluding Small Minors. 238-272 - Deepanshu Kush, Benjamin Rossman:
Tree-Depth and the Formula Complexity of Subgraph Isomorphism. 273-325
Volume 52, Number 2, April 2023
- Nikhil Bansal, Jatin Batra
, Majid Farhadi, Prasad Tetali:
On Min Sum Vertex Cover and Generalized Min Sum Set Cover. 327-357 - Sébastien Bouchard, Yoann Dieudonné, Andrzej Pelc:
Want to Gather? No Need to Chatter! 358-411 - Aris Filos-Ratsikas
, Alexandros Hollender
, Katerina Sotiraki
, Manolis Zampetakis
:
Consensus-Halving: Does It Ever Get Easier? 412-451 - Jean-Daniel Boissonnat, Siargey Kachanovich, Mathijs Wintraecken
:
Tracing Isomanifolds in \(\mathbb{R}\) d in Time Polynomial in d using Coxeter-Freudenthal-Kuhn Triangulations. 452-486 - Manish Raghavan
, Aleksandrs Slivkins
, Jennifer Wortman Vaughan
, Zhiwei Steven Wu:
Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits. 487-524 - Alexander A. Sherstov
, Andrey A. Storozhenko, Pei Wu:
An Optimal Separation of Randomized and Quantum Query Complexity. 525-567 - Joshua A. Grochow
, Youming Qiao:
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. 568-617 - Ewan Davies, Will Perkins:
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs. 618-640
Volume 52, Number 3, June 2023
- Tomasz Gogacz, Jerzy Marcinkowski, Andreas Pieris:
Uniform Restricted Chase Termination. 641-683 - Chong Shangguan
, Itzhak Tamo:
Generalized Singleton Bound and List-Decoding Reed-Solomon Codes Beyond the Johnson Radius. 684-717 - Jaroslaw Byrka, Fabrizio Grandoni
, Afrouz Jabal Ameli
:
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree. 718-739 - Mark de Berg, Hans L. Bodlaender
, Sándor Kisfaludi-Bak, Sudeshna Kolay:
An ETH-Tight Exact Algorithm for Euclidean TSP. 740-760 - Arnab Bhattacharyya, Sutanu Gayen
, Eric Price, Vincent Y. F. Tan
, N. V. Vinodchandran
:
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu. 761-793 - Swastik Kopparty, Noga Ron-Zewi
, Shubhangi Saraf, Mary Wootters
:
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes. 794-840
Volume 52, Number 4, August 2023
- Ulrich A. Brodowsky, Stefan Hougardy
, Xianghui Zhong
:
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem. 841-864 - Julien Baste
, Ignasi Sau
, Dimitrios M. Thilikos:
Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm. 865-912 - Dan Alistarh, James Aspnes, Faith Ellen
, Rati Gelashvili, Leqi Zhu:
Why Extension-Based Proofs Fail. 913-944 - Niv Buchbinder
, Moran Feldman
, Mohit Garg:
Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid. 945-967 - Marco Bressan, Enoch Peserico, Luca Pretto:
Sublinear Algorithms for Local Graph-Centrality Estimation. 968-1008 - Sevag Gharibian, François Le Gall:
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. 1009-1038 - Nithin Varma
, Yuichi Yoshida
:
Average Sensitivity of Graph Algorithms. 1039-1081
Volume 52, Number 5, October 2023
- Argyrios Deligkas
, Michail Fasoulakis, Evangelos Markakis:
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games. 1083-1096 - Konstantinos Panagiotou, Leon Ramzews, Benedikt Stufler:
Exact-Size Sampling of Enriched Trees in Linear Time. 1097-1131 - Sayan Bhattacharya, Monika Henzinger
, Danupon Nanongkai
, Xiaowei Wu
:
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover. 1132-1192 - Albert Atserias, Joanna Fijalkow
:
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem. 1193-1229 - Satoru Iwata
, Yu Yokoi:
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals. 1230-1268 - Sam Coy, Artur Czumaj:
Deterministic Massively Parallel Connectivity. 1269-1318 - Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman:
Corrigendum: Metric Embedding via Shortest Path Decompositions. 1319-1320
Volume 52, Number 6, December 2023
- Benny Applebaum
, Eliran Kachlon:
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error. 1321-1368 - Martin Grohe, Daniel Neuen, Pascal Schweitzer:
A Faster Isomorphism Test for Graphs of Small Degree. S18-1 - Urmila Mahadev:
Classical Homomorphic Encryption for Quantum Circuits. S18-189 - Akash Kumar, C. Seshadhri, Andrew Stolman:
Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs. S18-216 - Jatin Batra, Naveen Garg, Amit Kumar:
Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time. S18-158 - Shuichi Hirahara:
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\). S18-349 - Vera Traub, Jens Vygen:
Beating the Integrality Ratio for $s$-$t$-Tours in Graphs. S18-37 - Jeongwan Haah
, Matthew B. Hastings, Robin Kothari, Guang Hao Low:
Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians. S18-250 - Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, Junxing Wang:
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions. S18-85 - Elette Boyle, Vincent Cohen-Addad, Alexandra Kolla, Mikkel Thorup
:
Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018). S18- - Josh Alman, Virginia Vassilevska Williams:
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication. S18-285 - Mika Göös, Aviad Rubinstein:
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. S18-316 - Jesper Nederlof
, Jakub Pawlewicz, Céline M. F. Swennenhuis
, Karol Wegrzycki:
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics. 1369-1412 - Marcel Dall'Agnol
, Tom Gur, Oded Lachish
:
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification. 1413-1463
![](https://dblp1.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.