default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSIAM Journal on Computing, Volume 51
Volume 51, Number 1, February 2022
- Dirk Nowotka
, Aleksi Saarela:
An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences. 1-18 - Clément Carbonnel, Miguel Romero, Stanislav Zivný:
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side. 19-69 - Alkida Balliu, Sebastian Brandt, Dennis Olivetti:
Distributed Lower Bounds for Ruling Sets. 70-115 - Kristóf Bérczi, Endre Boros, Ondrej Cepek, Petr Kucera, Kazuhisa Makino:
Approximating Minimum Representations of Key Horn Functions. 116-138 - Vera Traub, Jens Vygen:
An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem. 139-173
Volume 51, Number 2, April 2022
- Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam:
Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model. 17-333 - Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman:
Metric Embedding via Shortest Path Decompositions. 290-314 - Andy Drucker, Ravi Kumar, Amit Sahai, Mohit Singh:
Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of Computing (STOC 2017). 17- - Jin-Yi Cai, Zhiguo Fu:
Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain. 17-50 - Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon:
Derandomization from Algebraic Hardness. 315-335 - Satoru Iwata, Yusuke Kobayashi:
A Weighted Linear Matroid Parity Algorithm. 17-238 - Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra:
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs. 17-305 - Yin Tat Lee, Santosh S. Vempala:
Geodesic Walks in Polytopes. 17-400 - Pierre Gillibert, Julius Jonusas, Michael Kompatscher, Antoine Mottet, Michael Pinsker:
When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems. 175-213 - Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs. 254-289 - Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan:
Deciding Parity Games in Quasi-polynomial Time. 17-152 - Julia Chuzhoy, David H. K. Kim, Rachit Nimavat:
New Hardness Results for Routing on Disjoint Paths. 17-189 - Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma:
An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy. 17-31 - William M. Hoza, Chris Umans:
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace. 17-281 - Danny Nguyen, Igor Pak:
Short Presburger Arithmetic Is Hard. 1-31 - Mohammad Bavarian, Thomas Vidick, Henry Yuen:
Anchored Parallel Repetition for Nonlocal Games. 214-253
Volume 51, Number 3, June 2022
- Pawel M. Idziak, Jacek Krzaczkowski:
Satisfiability in MultiValued Circuits. 337-378 - Arturo Merino, Ondrej Micka, Torsten Mütze:
On a Combinatorial Generation Problem of Knuth. 379-423 - Gilad Asharov, Wei-Kai Lin, Elaine Shi:
Sorting Short Keys in Circuits of Size ${o(n \log n)}$. 424-466 - Piotr Indyk, Tal Wagner:
Optimal (Euclidean) Metric Compression. 467-491 - Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer. 492-548 - Giulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone:
Elastic-Degenerate String Matching via Fast Matrix Multiplication. 549-576 - Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami:
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. 577-626 - Timothy M. Chan, Sariel Har-Peled, Mitchell Jones:
Optimal Algorithms for Geometric Centers and Depth. 627-663 - Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král, Kristýna Pekárková:
Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming. 664-700 - Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke:
Almost Tight Bounds for Reordering Buffer Management. 701-722 - Chih-Hung Liu:
Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions. 723-765 - Moran Feldman, Ola Svensson, Rico Zenklusen:
A Framework for the Secretary Problem on the Intersection of Matroids. 766-819 - Arkadev Chattopadhyay, Nikhil S. Mande:
A Short List of Equalities Induces Large Sign-Rank. 820-848 - Lijie Chen, Hanlin Ren:
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization. 20-115 - Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg:
Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions. 20-75 - Siddharth Bhandari, Sayantan Chakraborty:
Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs. 20-54 - Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes:
Explicit Near-Ramanujan Graphs of Every Degree. 20-1 - Huacheng Yu:
Nearly Optimal Static Las Vegas Succinct Dictionary. 20-174 - Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen:
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020). 20- - Vera Traub, Jens Vygen, Rico Zenklusen:
Reducing Path TSP to TSP. 20-24 - Konrad Anand, Mark Jerrum:
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing. 1280-1295 - John Hershberger, Subhash Suri, Hakan Yildiz:
A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane. 1296-1340
Volume 51, Number 4, August 2022
- Holger Dell, John Lapinskas, Kitty Meeks:
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle. 849-899 - Lap Chi Lau, Hong Zhou:
A Local Search Framework for Experimental Design. 900-951 - Haim Kaplan, Yishay Mansour, Yossi Matias, Uri Stemmer:
Differentially Private Learning of Geometric Concepts. 952-974 - Anupam Gupta, Amit Kumar, Debmalya Panigrahi:
Caching with Time Windows and Delays. 975-1017 - Lap Chi Lau, Hong Zhou:
A Spectral Approach to Network Design. 1018-1064 - Esther Ezra, Micha Sharir:
On Ray Shooting for Triangles in 3-Space and Related Problems. 1065-1095 - Renato Paes Leme, Jon Schneider:
Contextual Search via Intrinsic Volumes. 1096-1125 - Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri:
Tighter Bounds on MultiParty Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling. 1126-1171 - Urmila Mahadev:
Classical Verification of Quantum Computations. 1172-1229 - Jonathan Tidor, Yufei Zhao:
Testing Linear-Invariant Properties. 1230-1279 - MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeedreza Seddighin, Xiaorui Sun:
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier. 1341-1367 - Nathan Mull, Shuo Pang, Alexander A. Razborov:
On CDCL-Based Proof Systems with the Ordered Decision Strategy. 1368-1399 - Anne Broadbent, Alex Bredariol Grilo:
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge. 1400-1450
Volume 51, Number 5, December 2022
- Jonathan Leake, Nisheeth K. Vishnoi:
On the Computability of Continuous Maximum Entropy Distributions with Applications. 1451-1505 - Guillaume Ducoffe, Michel Habib, Laurent Viennot:
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik-Chervonenkis Dimension. 1506-1534 - Yaonan Jin, Shunhua Jiang, Pinyan Lu, Hengjie Zhang:
Tight Revenue Gaps among Multiunit Mechanisms. 1535-1579 - Alessio Conte, Roberto Grossi, Andrea Marino, Takeaki Uno, Luca Versari:
Proximity Search for Maximal Subgraph Enumeration. 1580-1625 - Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall:
A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines. 1626-1691 - Yuval Rabani, Amir Shpilka:
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions. 1692-1702
Volume 51, Number 6, December 2022
- Simon Apers, Ronald de Wolf:
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving. 1703-1742 - John Augustine, William K. Moses Jr., Amanda Redlich, Eli Upfal:
Balanced Allocation: Patience Is Not a Virtue. 1743-1768 - Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, Eylon Yogev:
One-Way Functions and (Im)perfect Obfuscation. 1769-1795 - Constantinos Daskalakis, Maxwell Fishelson, Brendan Lucier, Vasilis Syrgkanis, Santhoshini Velusamy:
Multi-Item Nontruthful Auctions Achieve Good Revenue. 1796-1838 - Alessandro Chiesa, Tom Gur, Igor Shinkar:
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. 1839-1865 - Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. 1866-1930
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.
last updated on 2026-01-29 02:09 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
