Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID35th SODA 2024, Alexandria, VA, USA
- David P. Woodruff:
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024. SIAM 2024, ISBN 978-1-61197-791-2 - Guru Guruganesh, Aranyak Mehta, Di Wang, Kangning Wang:
Prior-Independent Auctions for Heterogeneous Bidders. 1-18 - Shiri Ron:
Impossibilities for Obviously Strategy-Proof Mechanisms. 19-40 - Yannai A. Gonczarowski, Nicole Immorlica, Yingkai Li, Brendan Lucier:
Revenue Maximization for Buyers with Costly Participation. 41-73 - Hannaneh Akrami, Jugal Garg:
Breaking the 3/4 Barrier for Approximate Maximin Share. 74-91 - Paul Dütting, Michal Feldman, Yoav Gal Tzur:
Combinatorial Contracts Beyond Gross Substitutes. 92-108 - Ramiro Deo-Campo Vuong, Shaddin Dughmi, Neel Patel, Aditya Prasad:
On Supermodular Contracts and Dense Subgraphs. 109-132 - Parinya Chalermsook, Seth Pettie, Sorrachai Yingchareonthawornchai:
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns. 133-149 - Pankaj K. Agarwal
, Esther Ezra, Micha Sharir:
Vertical Decomposition in 3D and 4D with Applications to Line Nearest-Neighbor Searching in 3D. 150-170 - Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou:
Dynamic Dictionary with Subconstant Wasted Bits per Key. 171-207 - Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg:
Dynamic Dynamic Time Warping. 208-242 - Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, Monika Henzinger, Lara Ost:
Dynamically Maintaining the Persistent Homology of Time Series. 243-295 - Tuukka Korhonen, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski:
Fully dynamic approximation schemes on planar and apex-minor-free graphs. 296-313 - Baris Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma:
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations. 314-345 - Mathieu Mari, Anish Mukherjee, Michal Pilipczuk, Piotr Sankowski:
Shortest Disjoint Paths on a Grid. 346-365 - Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov:
Tree Containment Above Minimum Degree is FPT. 366-376 - Eduard Eiben, Tomohiro Koana, Magnus Wahlström:
Determinantal Sieving. 377-423 - Vasilis Livanos, Ruta Mehta:
Minimization is Harder in the Prophet World. 424-461 - Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, Yifan Wang:
Bandit Algorithms for Prophet Inequality and Pandora's Box. 462-500 - Yiding Feng, Chien-Ju Ho, Wei Tang:
Rationality-Robust Information Design: Bayesian Persuasion under Quantal Response. 501-546 - José Correa, Tobias Harks, Anja Schedel, José Verschae:
Equilibrium Dynamics in Market Games with Exchangeable and Divisible Resources. 547-568 - Ali Khodabakhsh, Emmanouil Pountourakis, Samuel Taggart:
Simple Delegated Choice. 569-590 - Lap Chi Lau, Kam Chuen Tung, Robert Wang:
Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues. 591-624 - Jana Cslovjecsek, Michal Pilipczuk, Karol Wegrzycki:
A polynomial-time OPTɛ-approximation algorithm for maximum independent set of connected subgraphs in a planar graph. 625-638 - Vera Traub, Laura Vargas Koch, Rico Zenklusen:
Single-Source Unsplittable Flows in Planar Graphs. 639-668 - Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi:
2-Approximation for Prize-Collecting Steiner Forest. 669-693 - Yu Chen, Zihan Tan:
An Ω~(√log|T|) Lower Bound for Steiner Point Removal. 694-698 - Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue:
Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable. 699-711 - Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi:
Meta-theorems for Parameterized Streaming Algorithms‡. 712-739 - Jana Cslovjecsek, Martin Koutecký, Alexandra Lassota, Michal Pilipczuk, Adam Polak:
Parameterized algorithms for block-structured integer programs with large entries. 740-751 - Edouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé:
Factoring Pattern-Free Permutations into Separable ones. 752-779 - Magnus Wahlström:
Representative set statements for delta-matroids and the Mader delta-matroid. 780-810 - Raphael A. Meyer, Cameron Musco, Christopher Musco:
On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation. 811-845 - Chandra Sekhar Mukherjee, Jiapeng Zhang:
Detecting Hidden Communities by Power Iterations with Connections to Vanilla Spectral Algorithms. 846-879 - Abhinav Bhardwaj, Van Vu:
Matrix Perturbation: Davis-Kahan in the Infinity Norm. 880-934 - Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal, Euiwoong Lee, Arnaud de Mesmay, Alantha Newman, Tony Chang Wang:
A PTAS for ℓ0-Low Rank Approximation: Solving Dense CSPs over Reals. 935-961 - Daniel Dadush, Akshay Ramachandran:
Strongly Polynomial Frame Scaling to High Precision. 962-981 - Alaa Ibrahim, Bruno Salvy:
Positivity Certificates for Linear Recurrences. 982-994 - Monika Henzinger, Jalaj Upadhyay, Sarvagya Upadhyay:
A Unifying Framework for Differentially Private Sums under Continual Observation. 995-1018 - Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou:
Optimal Bounds on Private Graph Approximation. 1019-1049 - David Rasmussen Lolck, Rasmus Pagh:
Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy. 1050-1066 - Moni Naor, Eugene Pekel:
Adjacency Sketches in Adversarial Environments. 1067-1098 - Christopher Trevisan:
Sorting and Selection in Rounds with Adversarial Comparisons. 1099-1119 - Fatima Elsheimy, Giorgos Tsimos, Charalampos Papamanthou:
Deterministic Byzantine Agreement with Adaptive O(n · f) Communication. 1120-1146 - Edouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii:
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes. 1147-1165 - Seth Pettie, Gábor Tardos:
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices. 1166-1176 - Jesse Campion Loth, Kevin Halasz, Tomás Masarík, Bojan Mohar, Robert Sámal:
Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic. 1177-1193 - Aleksander B. G. Christiansen, Eva Rotenberg, Daniel Rutschmann:
Triangulations Admit Dominating Sets of Size 2n/7. 1194-1240 - Vida Dujmovic, Robert Hickingbotham, Jedrzej Hodor, Gwenaël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, David R. Wood:
The Grid-Minor Theorem Revisited. 1241-1245 - Sharareh Alipour, Amir Jafari, Mohammad Hassan Mazidi, Seyed Abolfazl Najafian:
Partial Coloring Complex, Vertex Decomposability and Tverberg's Theorem with Constraints. 1246-1259 - Karl Bringmann:
Approximating Subset Sum Ratio faster than Subset Sum. 1260-1277 - Mehrdad Ghadiri, Richard Santiago, F. Bruce Shepherd:
A Parameterized Family of Meta-Submodular Functions. 1278-1306 - Adam Brown, Aditi Laddha, Madhusudhan Reddy Pittu, Mohit Singh:
Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs. 1307-1327 - Joshua Brakensiek, Neng Huang, Uri Zwick:
Tight approximability of MAX 2-SAT and relatives, under UGC. 1328-1344 - Naoto Ohsaka:
Gap Amplification for Reconfiguration Problems. 1345-1366 - Omar Alrabiah, Venkatesan Guruswami, Ray Li:
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. 1367-1378 - Benny Applebaum, Eliran Kachlon:
Conflict Checkable and Decodable Codes and Their Applications. 1379-1424 - Vishesh Jain, Huy Tuan Pham:
Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings. 1425-1436 - Gwenaël Joret, Piotr Micek, Michal Pilipczuk, Bartosz Walczak:
Cliquewidth and Dimension. 1437-1446 - Vít Jelínek, Michal Opler, Jakub Pekárek:
The Hierarchy of Hereditary Sorting Operators. 1447-1464 - Zhongtian He, Shang-En Huang, Thatchaphol Saranurak:
Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts. 1465-1502 - Zhongtian He, Shang-En Huang, Thatchaphol Saranurak:
Cactus Representation of Minimum Cuts: Derandomize and Speed up. 1503-1541 - Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi:
Beyond the Quadratic Time Barrier for Network Unreliability. 1542-1567 - Yu Chen, Zihan Tan:
On (1 + ɛ)-Approximate Flow Sparsifiers. 1568-1605 - Adam Karczmarz:
Max s, t-Flow Oracles and Negative Cycle Detection in Planar Digraphs. 1606-1620 - Moses Charikar, Kangning Wang, Prasanna Ramakrishnan, Hongxun Wu:
Breaking the Metric Voting Distortion Barrier. 1621-1640 - Shuchi Chawla, Kristin Sheridan:
Composition of nested embeddings with an application to outlier removal. 1641-1668 - Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.:
On Approximability of Steiner Tree in ℓp-metrics. 1669-1703 - Moses Charikar, Ruiquan Gao:
Improved Approximations for Ultrametric Violation Distance. 1704-1737 - Moritz Buchem, Katja Ettmayr, Hugo K. K. Rosado, Andreas Wiese:
A (3 + ɛ)-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds. 1738-1765 - Weiming Feng, Liqiang Liu, Tianren Liu:
On Deterministically Approximating Total Variation Distance. 1766-1791 - Simina Brânzei, Davin Choo, Nicholas J. Recker:
The Sharp Power Law of Local Search on Expanders. 1792-1809 - Nathaniel Harms, Viktor Zamaraev:
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank. 1810-1833 - Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin, Olga Ratseeva, Grigory Reznikov, Denil Sharipov:
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds. 1834-1853 - Radu Curticapean:
Count on CFI graphs for #P-hardness. 1854-1871 - Peter Bürgisser, Gorav Jindal:
On the Hardness of PosSLP. 1872-1886 - Evangelos Kosinas:
Computing the 5-Edge-Connected Components in Linear Time. 1887-2119 - Abhishek Dhawan:
Edge-Coloring Algorithms for Bounded Degree Multigraphs. 2120-2157 - Julia Gaudio, Xiaochun Niu, Ermin Wei:
Exact Community Recovery in the Geometric SBM. 2158-2184 - Julia Chuzhoy, Sanjeev Khanna:
A Faster Combinatorial Algorithm for Maximum Bipartite Matching. 2185-2235 - Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan:
Higher-Order Cheeger Inequality for Partitioning with Buffers. 2236-2274 - David G. Harris:
Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time. 2275-2304 - Kent Quanrud:
Faster exact and approximation algorithms for packing and covering matroids via push-relabel. 2305-2336 - Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan:
New SDP Roundings and Certifiable Approximation for Cubic Optimization. 2337-2362 - Suprovat Ghoshal, Anand Louis:
New Approximation Bounds for Small-Set Vertex Expansion. 2363-2375 - Will Perkins, Yuzhou Wang:
On the hardness of finding balanced independent sets in random bipartite graphs. 2376-2397 - Ainesh Bakshi, Ewin Tang:
An Improved Classical Singular Value Transformation for Quantum Machine Learning. 2398-2453 - Guanzhong Li, Lvzhou Li, Jingquan Luo:
Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem. 2454-2480 - Anirudh Krishna, Inbal Livni Navon, Mary Wootters:
Viderman's algorithm for quantum LDPC codes. 2481-2507 - Gregory Rosenthal:
Efficient Quantum State Synthesis with One Query. 2508-2534 - Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian:
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. 2535-2567 - Shiri Chechik, Tianyi Zhang:
Nearly Optimal Approximate Dual-Failure Replacement Paths. 2568-2596 - Adam Karczmarz, Wojciech Nadara, Marek Sokolowski:
Exact Shortest Paths with Rational Weights on the Word RAM. 2597-2608 - Greg Bodwin, Bernhard Haeupler, Merav Parter:
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free. 2609-2642 - Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu:
Simpler and Higher Lower Bounds for Shortcut Sets. 2643-2656 - Sébastien Collette, John Iacono:
Distances and shortest paths on graphs of bounded highway dimension: simple, fast, dynamic. 2657-2678 - Siddhartha Banerjee, Kamesh Munagala, Yiheng Shen, Kangning Wang:
Fair Price Discrimination. 2679-2703 - Ariel D. Procaccia, Isaac Robinson, Jamie Tucker-Foltz:
School Redistricting: Wiping Unfairness Off the Map. 2704-2724 - Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth:
Oracle Efficient Online Multicalibration and Omniprediction. 2725-2792 - Varun Suriyanarayana, Varun Sivashankar, Siddharth Gollapudi, David B. Shmoys:
Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints. 2793-2828 - Étienne Bamas, Alexander Lindermayr, Nicole Megow, Lars Rohwedder, Jens Schlöter:
Santa Claus meets Makespan and Matroids: Algorithms and Reductions. 2829-2860 - Mélanie Cambus, Fabian Kuhn, Etna Lindy, Shreyas Pai, Jara Uitto:
A (3 + ɛ)-Approximate Correlation Clustering Algorithm in Dynamic Streams. 2861-2880 - Christian Konrad, Kheeran K. Naidu:
An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation. 2881-2899 - Itai Dinur:
Time-Space Lower Bounds for Bounded-Error Computation in the Random-Query Model. 2900-2915 - Chien-Chung Huang, François Sellier:
Robust Sparsification for Matroid Intersection with Applications. 2916-2940 - Namiko Matsumoto, Arya Mazumdar:
Robust 1-bit Compressed Sensing with Iterative Hard Thresholding. 2941-2979 - Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford:
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time. 2980-2998 - Wenyu Jin, Xiaorui Sun, Mikkel Thorup:
Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time. 2999-3026 - Anastasiia Alokhina, Jan van den Brand:
Fully Dynamic Shortest Path Reporting Against an Adaptive Adversary. 3027-3039 - Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani:
Fully Dynamic Matching: -Approximation in Polylog Update Time. 3040-3061 - Chandra Chekuri, Aleksander Bjørn Grodt Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, Chris Schwiegelshohn:
Adaptive Out-Orientations with Applications. 3062-3088 - Monika Henzinger, Jason Li, Satish Rao, Di Wang:
Deterministic Near-Linear Time Minimum Cut in Weighted Graphs. 3089-3139 - Xin Lyu, Hongxun Wu, Junzhao Yang:
The Cost of Parallelizing Boosting. 3140-3155 - Itay Safran, Daniel Reichman, Paul Valiant:
How Many Neurons Does it Take to Approximate the Maximum? 3156-3183 - Andreas Galanis, Alkis Kalavasis, Anthimos Vardis Kandiros:
Learning Hard-Constrained Models with One Sample. 3184-3196 - Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao, Sihan Liu:
Online Robust Mean Estimation. 3197-3235 - Emmanuel Pilliat, Alexandra Carpentier, Nicolas Verzelen:
Optimal rates for ranking a permuted isotonic matrix in polynomial time. 3236-3273 - Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka:
Faster Sublinear-Time Edit Distance. 3274-3301 - Daniel Gibney, Ce Jin, Tomasz Kociumaka, Sharma V. Thankachan:
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization. 3302-3332 - Nick Fischer:
Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem. 3333-3353 - Philip Bille, Inge Li Gørtz:
Sparse Regular Expression Matching. 3354-3375 - Rajat De, Dominik Kempa:
Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data. 3376-3392 - Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon:
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time. 3393-3440 - Emilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari, Antonis Skarlatos:
Dynamic algorithms for k-center on graphs. 3441-3462 - Jakub Lacki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram, Václav Rozhon:
Fully Dynamic Consistent k-Center Clustering. 3463-3484 - Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh:
Dynamic Algorithms for Matroid Submodular Maximization. 3485-3533 - Jan van den Brand, Sebastian Forster, Yasamin Nazari, Adam Polak:
On Dynamic Graph Algorithms with Predictions. 3534-3557 - Sally Dong, Gramoz Goranci, Lawrence Li, Sushant Sachdeva, Guanghao Ye:
Fast Algorithms for Separable Linear Programs. 3558-3604 - Rémy Défossez, Christoph Haase, Alessio Mansutti, Guillermo A. Pérez:
Integer Programming with GCD Constraints. 3605-3658 - Haotian Jiang, Yin Tat Lee, Zhao Song, Lichen Zhang:
Convex Minimization with Integer Minima in Õ(n4) Time. 3659-3684 - Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford:
A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions. 3685-3723 - Telikepalli Kavitha, Kazuhisa Makino, Ildikó Schlotter, Yu Yokoi:
Arborescences, Colorful Forests, and Popularity. 3724-3746 - Max Gläser, Marc E. Pfetsch:
Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation. 3747-3764 - François Le Gall:
Faster Rectangular Matrix Multiplication by Combination Loss Analysis. 3765-3791 - Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou:
New Bounds for Matrix Multiplication: from Alpha to Omega. 3792-3835 - Songsong Li, Chaoping Xing:
Fast Fourier transform via automorphism groups of rational function fields. 3836-3859 - Victor Y. Pan:
Nearly Optimal Black Box Polynomial Root-finders. 3860-3900 - Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi:
Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits. 3901-3918 - Ruiwen Dong:
The Identity Problem in nilpotent groups of bounded class. 3919-3959 - Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan, Peilin Zhong:
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree. 3960-3996 - Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, Peilin Zhong:
Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth. 3997-4061 - Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi:
A Nearly Linear-Time Distributed Algorithm for Exact Maximum Matching. 4062-4082 - Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin:
A Distributed Palette Sparsification Theorem. 4083-4123 - Nairen Cao, Shang-En Huang, Hsin-Hao Su:
Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds. 4124-4154 - Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, Isabella Ziccardi:
The Minority Dynamics and the Power of Synchronicity. 4155-4176 - Anish Hebbar, Arindam Khan, K. V. N. Sreenivas:
Bin Packing under Random-Order: Breaking the Barrier of 3/2. 4177-4219 - Anupam Gupta, Amit Kumar, Debmalya Panigrahi:
Poly-logarithmic Competitiveness for the k-Taxi Problem. 4220-4246 - Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii:
Controlling Tail Risk in Online Ski-Rental. 4247-4263 - Romain Cosson:
Breaking the k/ log k Barrier in Collective Tree Exploration via Tree-Mining. 4264-4282 - Niv Buchbinder, Anupam Gupta, Daniel Hathcock, Anna R. Karlin, Sherry Sarkar:
Maintaining Matroid Intersections Online. 4283-4304 - Asaf Shapira, Henrique Stagni:
A Tight Bound for Testing Partition Properties. 4305-4320 - Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio:
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. 4321-4337 - Xi Chen, Cassandra Marcussen:
Uniformity Testing over Hypergrids with Subcube Conditioning. 4338-4370 - Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar:
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model. 4371-4394 - Dor Minzer, Kai Zhe Zheng:
Adversarial Low Degree Testing. 4395-4409 - Yi-Jun Chang, Da Wei Zheng:
Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs. 4410-4450 - Timothy M. Chan, Pingan Cheng, Da Wei Zheng:
An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism. 4451-4463 - Natan Rubin:
Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions. 4464-4501 - Siu-Wing Cheng, Haoqiang Huang:
Solving Fréchet Distance Problems by Algebraic Geometric Methods. 4502-4513 - Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, Keegan Yao:
Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings. 4514-4529 - Anupam Gupta, Gregory Kehne, Roie Levin:
Set Covering with Our Eyes Wide Shut. 4530-4553 - Nemanja Draganic, Rajko Nenadov:
Edge-disjoint paths in expanders: online with removals. 4554-4563 - Sujoy Bhore, Arnold Filtser, Csaba D. Tóth:
Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings. 4564-4579 - Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Jan Olkowski:
Power of Posted-price Mechanisms for Prophet Inequalities. 4580-4604 - Neel Patel, David Wajc:
Combinatorial Stationary Prophet Inequalities. 4605-4630 - Shuyi Yan:
Edge-weighted Online Stochastic Matching: Beating. 4631-4640 - Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams, Zixuan Xu:
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation. 4641-4669 - Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann:
The Time Complexity of Fully Sparse Matrix Multiplication. 4670-4703 - Nick Fischer, Marvin Künnemann, Mirza Redzic:
The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties. 4704-4727 - Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, Tijn de Vos:
Fast 2-Approximate All-Pairs Shortest Paths. 4728-4757 - Barna Saha, Christopher Ye:
Faster Approximate All Pairs Shortest Paths. 4758-4827 - Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang:
Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results. 4828-4848 - Yan Alves Radtke, Stefan Felsner, Johannes Obenaus, Sandro Roch, Manfred Scheucher, Birgit Vogtenhuber:
Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles. 4849-4871 - Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick:
Delaunay Bifiltrations of Functions on Point Clouds. 4872-4891 - Pankaj K. Agarwal, Sariel Har-Peled, Rahul Raychaudhury, Stavros Sintos:
Fast Approximation Algorithms for Piercing Boxes by Points. 4892-4908 - Éric Colin de Verdière, Vincent Despré, Loïc Dubois:
Untangling Graphs on Surfaces. 4909-4941 - Pankaj K. Agarwal, Dan Halperin, Micha Sharir, Alex Steiger:
Near-Optimal Min-Sum Motion Planning for Two Square Robots in a Polygonal Environment. 4942-4962 - Louis Golowich:
New Explicit Constant-Degree Lossless Expanders. 4963-4971 - Zongchen Chen, Yuzhou Gu:
Fast Sampling of b-Matchings and b-Edge Covers. 4972-4987 - Zongchen Chen:
Combinatorial Approach for Factorization of Variance and Entropy in Spin Systems. 4988-5012 - Dmitriy Kunisky:
Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation. 5013-5028 - Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, Thuy-Duong Vuong:
Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses. 5029-5056 - Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis:
Smoothed Complexity of SWAP in Local Graph Partitioning. 5057-5083 - Cameron Musco, Kshiteej Sheth:
Sublinear Time Low-Rank Approximation of Toeplitz Matrices. 5084-5117 - Moses Charikar, Michael Kapralov, Erik Waingarten:
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. 5118-5144 - Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Code Sparsification and its Applications. 5145-5168 - Arun Jambulapati, Victor Reis, Kevin Tian:
Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory. 5169-5208 - Kent Quanrud:
Quotient sparsification for submodular functions. 5209-5248 - Tuukka Korhonen, Daniel Lokshtanov:
Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition. 5249-5275 - Akanksha Agrawal, Paloma T. Lima, Daniel Lokshtanov, Saket Saurabh, Roohani Sharma:
Odd Cycle Transversal on P5-free Graphs in Quasi-polynomial Time. 5276-5290 - Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski:
Sparse induced subgraphs in P6-free graphs. 5291-5299 - Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than:
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More. 5300-5331 - Hung Le, Christian Wulff-Nilsen:
VC Set Systems in Minor-free (Di)Graphs and Applications. 5332-5360
a service of 
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 2024-05-14 21:19 CEST 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:
