Login / Signup
APPROX/RANDOM
2023
2023
2023
Keyphrases
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)