APPROX/RANDOM

Publications

2023

Andreas Galanis, Leslie Ann Goldberg, Paulina Smolarova
Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics. APPROX/RANDOM (2023)
Josefine Foos, Stephan Held, Yannik Kyle Dustin Spitzley
Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem. APPROX/RANDOM (2023)
Matej Lieskovský, Jirí Sgall, Andreas Emil Feldmann
Approximation Algorithms and Lower Bounds for Graph Burning. APPROX/RANDOM (2023)
Nikhil Ayyadevara, Nikhil Bansal, Milind Prabhu
On Minimizing Generalized Makespan on Unrelated Machines. APPROX/RANDOM (2023)
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
On Complexity of 1-Center in Various Metrics. APPROX/RANDOM (2023)
Eden Chlamtác, Yury Makarychev, Ali Vakilian
Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment. APPROX/RANDOM (2023)
Roy Gotlib, Tali Kaufman
Fine Grained Analysis of High Dimensional Random Walks. APPROX/RANDOM (2023)
Karthekeyan Chandrasekaran, Weihang Wang
Approximating Submodular k-Partition via Principal Partition Sequence. APPROX/RANDOM (2023)
Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan
Low-Degree Testing over Grids. APPROX/RANDOM (2023)
Anita Dürr, Nicolas El Maalouly, Lasse Wulf
An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs. APPROX/RANDOM (2023)
Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova, Dragos Ristache
Testing Connectedness of Images. APPROX/RANDOM (2023)
Antonio Blanca, Xusheng Zhang
Rapid Mixing of Global Markov Chains via Spectral Independence: The Unbounded Degree Case. APPROX/RANDOM (2023)
Venkatesan Guruswami, Shilun Li
A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. APPROX/RANDOM (2023)
Kamesh Munagala, Govind S. Sankar, Erin Taylor
Probabilistic Metric Embedding via Metric Labeling. APPROX/RANDOM (2023)
Kalen Patton, Matteo Russo, Sahil Singla
Submodular Norms with Applications To Online Facility Location and Stochastic Probing. APPROX/RANDOM (2023)
Morteza Monemizadeh
Facility Location in the Sublinear Geometric Model. APPROX/RANDOM (2023)
Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang
Robustness for Space-Bounded Statistical Zero Knowledge. APPROX/RANDOM (2023)
Lap Chi Lau, Robert Wang, Hong Zhou
Experimental Design for Any p-Norm. APPROX/RANDOM (2023)
Danish Kashaev, Guido Schäfer
Round and Bipartize for Vertex Cover Approximation. APPROX/RANDOM (2023)
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh
On the Composition of Randomized Query Complexity and Approximate Degree. APPROX/RANDOM (2023)
Front Matter, Table of Contents, Preface, Conference Organization. APPROX/RANDOM (2023)
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
/ poly(n). APPROX/RANDOM (2023)
Mark de Berg, Arpan Sadhukhan, Frits C. R. Spieksma
Stable Approximation Algorithms for Dominating Set and Independent Set. APPROX/RANDOM (2023)
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, Samson Zhou
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity. APPROX/RANDOM (2023)
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich
Synergy Between Circuit Obfuscation and Circuit Minimization. APPROX/RANDOM (2023)
Ilan Doron Arad, Ariel Kulik, Hadas Shachnai
An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding. APPROX/RANDOM (2023)
Noah G. Singer
Oblivious Algorithms for the Max-kAND Problem. APPROX/RANDOM (2023)
Konrad Anand, Andreas Göbel, Marcus Pappik, Will Perkins
Perfect Sampling for Hard Spheres from Strong Spatial Mixing. APPROX/RANDOM (2023)
Lindsey Deryckere, Seeun William Umboh
Online Matching with Set and Concave Delays. APPROX/RANDOM (2023)
Chandra Chekuri, Kent Quanrud
Independent Sets in Elimination Graphs with a Submodular Objective. APPROX/RANDOM (2023)
Yahli Hecht, Dor Minzer, Muli Safra
NP-Hardness of Almost Coloring Almost 3-Colorable Graphs. APPROX/RANDOM (2023)
Zachary Friggstad, Ramin Mousavi
A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs. APPROX/RANDOM (2023)
Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, Emo Welzl
On Connectivity in Random Graph Models with Limited Dependencies. APPROX/RANDOM (2023)
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi
Range Avoidance for Constant Depth Circuits: Hardness and Algorithms. APPROX/RANDOM (2023)
Renato Ferreira Pinto Jr.
Directed Poincaré Inequalities and L¹ Monotonicity Testing of Lipschitz Functions. APPROX/RANDOM (2023)
Quanquan C. Liu, Yiduo Ke, Samir Khuller
Scalable Auction Algorithms for Bipartite Maximum Matching Problems. APPROX/RANDOM (2023)
Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan, Will Rosenbaum, Jakub Tetek
Bias Reduction for Sum Estimation. APPROX/RANDOM (2023)
Amin Coja-Oghlan, Jane Gao, Max Hahn-Klimroth, Joon Lee, Noëla Müller, Maurice Rolvien
The Full Rank Condition for Sparse Random Matrices. APPROX/RANDOM (2023)
Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, Chen Wang
Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance. APPROX/RANDOM (2023)
Nader H. Bshouty
Superpolynomial Lower Bounds for Learning Monotone Classes. APPROX/RANDOM (2023)
Sepideh Mahabadi, Shyam Narayanan
Improved Diversity Maximization Algorithms for Matching and Pseudoforest. APPROX/RANDOM (2023)
Chin Ho Lee, Edward Pyne, Salil P. Vadhan
On the Power of Regular and Permutation Branching Programs. APPROX/RANDOM (2023)
Joshua Cook, Dana Moshkovitz
Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE. APPROX/RANDOM (2023)
Ishan Bansal, Joe Cheriyan, Logan Grout, Sharat Ibrahimpur
Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals. APPROX/RANDOM (2023)
Swastik Kopparty, Vishvajeet N
Extracting Mergers and Projections of Partitions. APPROX/RANDOM (2023)
Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, Christos Tzamos
Approximating Pandora's Box with Correlations. APPROX/RANDOM (2023)
Emin Karayel
An Embarrassingly Parallel Optimal-Space Cardinality Estimation Algorithm. APPROX/RANDOM (2023)
Andrej Bogdanov, Tsun Ming Cheung, Krishnamoorthy Dinesh, John C. S. Lui
Classical Simulation of One-Query Quantum Distinguishers. APPROX/RANDOM (2023)
George Karakostas, Stavros G. Kolliopoulos
Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines. APPROX/RANDOM (2023)

volume 275, 2023

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA APPROX/RANDOM 275 (2023)