- 2017
- Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun:
Sample-Based High-Dimensional Convexity Testing. APPROX-RANDOM 2017: 37:1-37:20 - Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten:
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. APPROX-RANDOM 2017: 38:1-38:21 - Rupam Acharyya, Daniel Stefankovic:
Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences. APPROX-RANDOM 2017: 23:1-23:22 - Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, Vivek Madan:
On the Expansion of Group-Based Lifts. APPROX-RANDOM 2017: 24:1-24:13 - Vedat Levi Alev, Lap Chi Lau:
Approximating Unique Games Using Low Diameter Graph Decomposition. APPROX-RANDOM 2017: 18:1-18:15 - Noga Alon, Omri Ben-Eliezer:
Efficient Removal Lemmas for Matrices. APPROX-RANDOM 2017: 25:1-25:18 - Omer Angel, Abbas Mehrabian, Yuval Peres:
The String of Diamonds Is Tight for Rumor Spreading. APPROX-RANDOM 2017: 26:1-26:9 - Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, Roger Wattenhofer:
Min-Cost Bipartite Perfect Matching with Delays. APPROX-RANDOM 2017: 1:1-1:20 - Haim Avron, Kenneth L. Clarkson, David P. Woodruff:
Sharper Bounds for Regularized Data Fitting. APPROX-RANDOM 2017: 27:1-27:22 - Jess Banks, Robert Kleinberg, Cristopher Moore:
The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime. APPROX-RANDOM 2017: 28:1-28:22 - Anna Ben-Hamou, Yuval Peres:
Cutoff for a Stratified Random Walk on the Hypercube. APPROX-RANDOM 2017: 29:1-29:10 - Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, Chao Xu:
Global and Fixed-Terminal Cuts in Digraphs. APPROX-RANDOM 2017: 2:1-2:20 - Arnab Bhattacharyya, Sivakanth Gopi, Avishay Tal:
Lower Bounds for 2-Query LCCs over Large Alphabet. APPROX-RANDOM 2017: 30:1-30:20 - Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee:
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. APPROX-RANDOM 2017: 31:1-31:20 - Jaroslaw Blasiok, Jian Ding, Jelani Nelson:
Continuous Monitoring of l_p Norms in Data Streams. APPROX-RANDOM 2017: 32:1-32:13 - Glencora Borradaile, Baigong Zheng:
A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs. APPROX-RANDOM 2017: 3:1-3:13 - Joshua Brakensiek:
Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques. APPROX-RANDOM 2017: 33:1-33:15 - Joshua Brakensiek, Venkatesan Guruswami:
The Quest for Strong Inapproximability Results with Perfect Completeness. APPROX-RANDOM 2017: 4:1-4:20 - Sarah Cannon, David A. Levin, Alexandre Stauffer:
Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings. APPROX-RANDOM 2017: 34:1-34:21 - Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Agnostic Learning from Tolerant Natural Proofs. APPROX-RANDOM 2017: 35:1-35:19 - L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak, Nisheeth K. Vishnoi:
On the Complexity of Constrained Determinantal Point Processes. APPROX-RANDOM 2017: 36:1-36:22 - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Axis-Parallel Tests for Tensor Product Codes. APPROX-RANDOM 2017: 39:1-39:22 - Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, Tobias Kapetanopoulos:
Charting the Replica Symmetric Phase. APPROX-RANDOM 2017: 40:1-40:17 - Dean Doron, François Le Gall, Amnon Ta-Shma:
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers. APPROX-RANDOM 2017: 41:1-41:20 - Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou:
Streaming Periodicity with Mismatches. APPROX-RANDOM 2017: 42:1-42:21 - S. Luna Frank-Fischer, Venkatesan Guruswami, Mary Wootters:
Locality via Partially Lifted Codes. APPROX-RANDOM 2017: 43:1-43:17 - Cody R. Freitag, Eric Price, William J. Swartworth:
Testing Hereditary Properties of Sequences. APPROX-RANDOM 2017: 44:1-44:10 - Alan M. Frieze, Wesley Pegden:
Traveling in Randomly Embedded Random Graphs. APPROX-RANDOM 2017: 45:1-45:17 - Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher S. Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, Yifeng Zhang:
Scheduling Problems over Network of Machines. APPROX-RANDOM 2017: 5:1-5:18 - Michel X. Goemans, Francisco Unda:
Approximating Incremental Combinatorial Optimization Problems. APPROX-RANDOM 2017: 6:1-6:14