default search action
APPROX/RANDOM 2023: Atlanta, GA, USA
- Nicole Megow
, Adam D. Smith
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA. LIPIcs 275, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2023, ISBN 978-3-95977-296-9 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:24
- Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin:
On Complexity of 1-Center in Various Metrics. 1:1-1:19 - Kamesh Munagala, Govind S. Sankar, Erin Taylor
Probabilistic Metric Embedding via Metric Labeling. 2:1-2:10 - Karthekeyan Chandrasekaran, Weihang Wang:
Approximating Submodular k-Partition via Principal Partition Sequence. 3:1-3:16 - Lap Chi Lau, Robert Wang, Hong Zhou:
Experimental Design for Any p-Norm. 4:1-4:21 - George Karakostas, Stavros G. Kolliopoulos:
Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines. 5:1-5:17 - Morteza Monemizadeh:
Facility Location in the Sublinear Geometric Model. 6:1-6:24 - Tanvi Bajpai, Chandra Chekuri:
Bicriteria Approximation Algorithms for Priority Matroid Median. 7:1-7:22 - Elena Grigorescu, Nithish Kumar, Young-San Lin:
Approximation Algorithms for Directed Weighted Spanners. 8:1-8:23 - Matej Lieskovský, Jirí Sgall
Approximation Algorithms and Lower Bounds for Graph Burning. 9:1-9:17 - Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz:
The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems. 10:1-10:20 - Eden Chlamtác, Yury Makarychev, Ali Vakilian:
Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment. 11:1-11:19 - Anupam Gupta, Amit Kumar, Debmalya Panigrahi:
Efficient Algorithms and Hardness Results for the Weighted k-Server Problem. 12:1-12:19 - Zachary Friggstad, Ramin Mousavi:
A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs. 13:1-13:18 - Ishan Bansal, Joe Cheriyan, Logan Grout, Sharat Ibrahimpur:
Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals. 14:1-14:14 - Noah G. Singer
Oblivious Algorithms for the Max-kAND Problem. 15:1-15:19 - Felix Höhne, Rob van Stee:
A 10/7-Approximation for Discrete Bamboo Garden Trimming and Continuous Trimming on Star Graphs. 16:1-16:19 - Lindsey Deryckere, Seeun William Umboh
Online Matching with Set and Concave Delays. 17:1-17:17 - Anita Dürr, Nicolas El Maalouly, Lasse Wulf:
An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs. 18:1-18:21 - Josefine Foos, Stephan Held, Yannik Kyle Dustin Spitzley:
Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem. 19:1-19:16 - Danish Kashaev, Guido Schäfer
Round and Bipartize for Vertex Cover Approximation. 20:1-20:20 - Nikhil Ayyadevara, Nikhil Bansal, Milind Prabhu:
On Minimizing Generalized Makespan on Unrelated Machines. 21:1-21:13 - Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai:
An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding. 22:1-22:16 - Kalen Patton, Matteo Russo
Submodular Norms with Applications To Online Facility Location and Stochastic Probing. 23:1-23:22 - Chandra Chekuri, Kent Quanrud:
Independent Sets in Elimination Graphs with a Submodular Objective. 24:1-24:22 - Sepideh Mahabadi, Shyam Narayanan:
Improved Diversity Maximization Algorithms for Matching and Pseudoforest. 25:1-25:22 - Shuchi Chawla, Evangelia Gergatsouli
Approximating Pandora's Box with Correlations. 26:1-26:24 - Mark de Berg, Arpan Sadhukhan
Stable Approximation Algorithms for Dominating Set and Independent Set. 27:1-27:19 - Quanquan C. Liu, Yiduo Ke, Samir Khuller:
Scalable Auction Algorithms for Bipartite Maximum Matching Problems. 28:1-28:24 - Ruben Becker, Arnaud Casteigts, Pierluigi Crescenzi, Bojana Kodric
Giant Components in Random Temporal Graphs. 29:1-29:17 - Johannes Lengler
On Connectivity in Random Graph Models with Limited Dependencies. 30:1-30:22 - Russell Impagliazzo
Synergy Between Circuit Obfuscation and Circuit Minimization. 31:1-31:21 - Meghal Gupta, Rachel Yun Zhang:
Interactive Error Correcting Codes: New Constructions and Impossibility Bounds. 32:1-32:14 - Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda:
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees. 33:1-33:16 - Nader H. Bshouty:
Superpolynomial Lower Bounds for Learning Monotone Classes. 34:1-34:20 - Emin Karayel
An Embarrassingly Parallel Optimal-Space Cardinality Estimation Algorithm. 35:1-35:22 - Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov
Sampling and Certifying Symmetric Functions. 36:1-36:21 - Huck Bennett, Chris Peikert:
Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes. 37:1-37:20 - Konrad Anand, Andreas Göbel, Marcus Pappik, Will Perkins:
Perfect Sampling for Hard Spheres from Strong Spatial Mixing. 38:1-38:18 - Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
Subset Sum in Time 2n/2 / poly(n). 39:1-39:18 - Dorna Abdolazimi, Kasper Lindberg, Shayan Oveis Gharan:
On Optimization and Counting of Non-Broken Bases of Matroids. 40:1-40:14 - Prashanth Amireddy, Srikanth Srinivasan
Low-Degree Testing over Grids. 41:1-41:22 - Rubi Arviv, Lily Chung, Reut Levi, Edward Pyne:
Improved Local Computation Algorithms for Constructing Spanners. 42:1-42:23 - Andrej Bogdanov, Tsun Ming Cheung, Krishnamoorthy Dinesh
Classical Simulation of One-Query Quantum Distinguishers. 43:1-43:17 - Chin Ho Lee, Edward Pyne, Salil P. Vadhan:
On the Power of Regular and Permutation Branching Programs. 44:1-44:22 - Vladimir Braverman, Joel Manning, Zhiwei Steven Wu, Samson Zhou:
Private Data Stream Analysis for Universal Symmetric Norm Estimation. 45:1-45:24 - Lior Gishboliner
Testing Versus Estimation of Graph Properties, Revisited. 46:1-46:18 - Joshua Cook, Ron D. Rothblum:
Efficient Interactive Proofs for Non-Deterministic Bounded Space. 47:1-47:22 - Arijit Bishnu, Arijit Ghosh, Gopinath Mishra:
On the Complexity of Triangle Counting Using Emptiness Queries. 48:1-48:22 - Roy Gotlib, Tali Kaufman:
Fine Grained Analysis of High Dimensional Random Walks. 49:1-49:22 - Venkatesan Guruswami, Shilun Li:
A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. 50:1-50:10 - Yahli Hecht, Dor Minzer, Muli Safra:
NP-Hardness of Almost Coloring Almost 3-Colorable Graphs. 51:1-51:12 - Swastik Kopparty, Vishvajeet N:
Extracting Mergers and Projections of Partitions. 52:1-52:22 - Antonio Blanca, Xusheng Zhang:
Rapid Mixing of Global Markov Chains via Spectral Independence: The Unbounded Degree Case. 53:1-53:19 - Amin Coja-Oghlan, Jane Gao, Max Hahn-Klimroth
The Full Rank Condition for Sparse Random Matrices. 54:1-54:14 - Joshua Cook, Dana Moshkovitz:
Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE. 55:1-55:22 - Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang:
Robustness for Space-Bounded Statistical Zero Knowledge. 56:1-56:21 - Sepehr Assadi, Michael Kapralov
On Constructing Spanners from Random Gaussian Projections. 57:1-57:18 - Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, Chen Wang:
Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance. 58:1-58:23 - Jeremiah Blocki
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity. 59:1-59:24 - Fernando Granha Jeronimo:
Fast Decoding of Explicit Almost Optimal ε-Balanced q-Ary Codes And Fast Approximation of Expanding k-CSPs. 60:1-60:16 - Renato Ferreira Pinto Jr.:
Directed Poincaré Inequalities and L¹ Monotonicity Testing of Lipschitz Functions. 61:1-61:18 - Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan, Will Rosenbaum, Jakub Tetek:
Bias Reduction for Sum Estimation. 62:1-62:21 - Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar
On the Composition of Randomized Query Complexity and Approximate Degree. 63:1-63:23 - Andreas Galanis, Leslie Ann Goldberg, Paulina Smolarova:
Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics. 64:1-64:12 - Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi:
Range Avoidance for Constant Depth Circuits: Hardness and Algorithms. 65:1-65:18 - Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, Dragos Ristache:
Testing Connectedness of Images. 66:1-66:15
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-11-04 20:30 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: