|
Accepted papers in Random - Papers
- A Combination of Testability and Decodability by Tensor Products-Michael Viderman
- Rainbow Connectivity of Random Sparse Graphs-Alan Frieze and Charalampos E. Tsourakakis
- Almost k-wise vs. k-wise Independent Permutations, and Uniformity for General Group Actions-Noga Alon and Shachar Lovett
- Extractors for Turing-machine Sources-Emanuele Viola
- Two-Sided Error Proximity Oblivious Testing-Oded Goldreich and Igor Shinkar
- On the Coin Weighing Problem with the Presence of Noise-Nader H. Bshouty
- Limitations of Local Filters of Lipschitz and Monotone Functions-Pranjal Awasthi and Madhav Jha and Marco Molinaro and Sofya Raskhodnikova
- Tight Bounds on the Threshold for Permuted k-colorability-Varsha Dani and Cristopher Moore and Anna Olson
- Maximal Empty Boxes Amidst Random Points-Adrian Dumitrescu and Minghui Jiang
- Extractors for Polynomial Sources over Constant-Size Fields of Small Characteristic-Eli Ben-Sasson and Ariel Gabizon
- A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller Codes-Noga Ron-Zewi and Madhu Sudan
- A Discrepancy Lower Bound for Information Complexity-Mark Braverman and Omri Weinstein
- Analysis of k-means++ for Separable Data-Ragesh Jaiswal and Nitin Garg
- Pseudorandomness for Linear Length Branching Programs and Stack Machines-Andrej Bogdanov and Periklis A. Papakonstantinou and Andrew Wan
- Tight Bounds for Testing k-Linearity-Eric Blais and Daniel Kane
- Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors-Ariel Gabizon and Ronen Shaltiel
- Finding Small Sparse Cuts Locally by Random Walk-Tsz Chiu Kwok and Lap Chi Lau
- A Sharper Local Lemma with Improved Applications-Kashyap Kolipaka and Mario Szegedy and Yixin Xu
- On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation-Jelani Nelson and Huy L. Nguyen and David P. Woodruff
- Multiple-choice Balanced Allocation in (almost) Parallel-Petra Berenbrink and Artur Czumaj and Matthias Englert and Tom Friedetzky and Lars Nagel
- Spectral Norm of Symmetric Functions -Anil Ada and Omar Fawzi and Hamed Hatami
- An Explicit VC-Theorem for Low-Degree Polynomials -Eshan Chattopadhyay and Adam Klivans and Pravesh Kothari
- Mirror Descent based Interactive Database Privacy -Prateek Jain and Abhradeep Thakurta
- Optimal Hitting Sets for Combinatorial Shapes -Aditya Bhaskara and Devendra Desai and Srikanth Srinivasan
- Testing Lipschitz Functions on Hypergrid Domains -Pranjal Awasthi and Madhav Jha and Marco Molinaro and Sofya Raskhodnikova
- Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming -Amit Chakrabarti and Ranganath Kondapally and Zhenghui Wang
- Sparse and Lopsided Set Disjointness via Information Theory -Anirban Dasgupta and Ravi Kumar and D. Sivakumar
- Downward Self-Reducibility of the Permanent - Revisited -Sanjeev Arora and Arnab Bhattacharyya and Rajsekar Manokaran and Sushant Sachdeva
Accepted papers in Approx - Papers
- Approximating Bounded Occurrence Ordering CSPs-Venkatesan Guruswami and Yuan Zhou
- Approximating Minimum-Cost Connected $T$-joins-Joseph Cheriyan and Zachary Friggstad and Zhihan Gao
- On the NP-hardness of Max-Not-2-Johan Hastad
- Improved Inapproximability for TSP-Michael Lampis
- New and Improved Bounds for the Minimum Set Cover Problem-Rishi Saket and Maxim Sviridenko
- Additive Approximation for Near-Perfect Phylogeny Construction-Pranjal Awasthi and Avrim Blum and Jamie Morgenstern and Or Sheffet
- Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply-Parinya Chalermsook and Julia Chuzhoy and Sampath Kannan and Sanjeev Khanna
- Approximation Algorithms for Generalized and Variable-sized Bin Covering-Matthias Hellwig and Alexander Souza
- iBGP and Constrained Connectivity-Michael Dinitz and Gordon Wilfong
- The Remote Set Problem on Lattices-Ishay Haviv
- Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues-Suguru Tamaki and Yuichi Yoshida
- Online Flow Time Scheduling in the Presence of Preemption Overhead-Ho-Leung Chan and Tak-Wah Lam and Rongbin Li
- Online Scheduling of Jobs with Fixed Start Times on Related Machines-Leah Epstein and Lukasz Jez and Jiri Sgall and Rob van Stee
- A Systematic Approach to Bound Factor Revealing LPs and its Application to the Metric and Squared Metric Facility Location Problems-Cristina G. Fernandes and Luis A. A. Meira and Flavio K. Miyazawa and Lehilton L. C. Pedrosa
- Improved Spectral-Norm Bounds for Clustering-Pranjal Awasthi and Or Sheffet
- Maximum Matching in Semi-Streaming with Few Passes-Christian Konrad and Frédéric Magniez and Claire Mathieu
- Hardness of Vertex Deletion and Project Scheduling-Ola Svensson
- Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems-Per Austrin and Toniann Pitassi and Yu Wu
- What's the frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid-Petros Boufounos and Volkan Cevher and Anna C. Gilbert and Yi Li and Martin J. Strauss
- Prize-collecting Survivable Network Design in Node-weighted Graphs-Chandra Chekuri and Alina Ene and Ali Vakilian
- New Approximation Results for Resource Replication Problems-Samir Khuller and Barna Saha and Kanthi K. Sarpatwar
- The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover-Dana Moshkovitz
- Approximating Minimum Linear Ordering Problems-Satoru Iwata and Prasad Tetali and Pushkar Tripathi
- Planarizing an Unknown Surface-Yury Makarychev and Anastasios Sidiropoulos
- Approximation Algorithm for Non-Boolean MAX k-CSP-Konstantin Makarychev and Yury Makarychev
- A New Point of NP-Hardness for 2-to-1 Label Cover-Per Austrin and Ryan O'Donnell and John Wright
- Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four-Cenny Wenner
- Primal-dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs-Piotr Berman and Grigory Yaroslavtsev
|
PDF Format
Plain Text
