|
Accepted papers in Random - Papers
- Lidor Avigad and Oded Goldreich. Testing Graph Blow-Up
- Thomas Watson. Query Complexity in Errorless Hardness Amplification
- Oded Goldreich and Tali Kaufman. Proximity Oblivious Testing and the Role of Invariances
- Eldar Fischer and Eyal Rozenberg. Inflatable graph properties and natural property tests
- Anindya De and Thomas Watson. Extractors and Lower Bounds for Locally Samplable Sources
- Omri Weinstein, Ronitt Rubinfeld, Dana Ron and Muli Safra. Approximating the influence of a monotone Boolean function in $O(\sqrt{n})$ query complexity
- Eli Ben-Sasson and Madhu Sudan. Limits on the rate of locally testable affine-invariant codes
- Gilad Tsur and Dana Ron. On Approximating the Number of Relevant Variables in a Function
- Nayantara Bhatnagar, Andrej Bogdanov and Elchanan Mossel. The Computational Complexity of Estimating MCMC Convergence Time
- Dana Dachman-Soled and Rocco Servedio. A canonical form for testing Boolean function properties
- Irit Dinur and Tali Kaufman. Dense locally testable codes cannot have constant rate and distance
- Andris Ambainis, Andrew Childs and Yi-Kai Liu. Quantum property testing for bounded-degree graphs
- Domingos Dellamonica, Subrahmanyam Kalyanasundaram, Daniel Martin, Vojtech Rodl and Asaf Shapira. A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma
- Varsha Dani and Cristopher Moore. Independent sets in random graphs from the weighted second moment method
- Brett Hemenway, Martin Strauss, Rafail Ostrovsky and Mary Wootters. Public-Key Locally-Decodable Codes with Short Keys
- Amit Chakrabarti and Ranganath Kondapally. Everywhere-Tight Information Cost Tradeoffs for Augmented Index
- Venkatesan Guruswami and Carol Wang. Optimal rate list decoding via derivative codes
- Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka and Madhu Sudan. On Sums of Locally Testable Affine Invariant Properties
- Shachar Lovett and Srikanth Srinivasan. Correlation bounds for poly-size AC0 circuits with n^{1−o(1)} symmetric gates
- Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda and Linji Yang. Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
- Sarah Miracle, Dana Randall and Amanda Pascoe Streib. Clustering in Interfering Models of Binary Mixtures
- Zhiyi Huang and Sampath Kannan. On Sampling from Multivariate Distributions
- Tobias Friedrich and Lionel Levine. Fast Simulation of Large-Scale Growth Models
- Alan Edelman, Avinatan Hassidim, Huy Nguyen and Krzysztof Onak. An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
- Sergei Artemenko and Ronen Shaltiel. Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Andrew Drucker. Efficient Probabilistically Checkable Debates
- Daniel Kane, Raghu Meka and Jelani Nelson. Almost Optimal Explicit Johnson-Lindenstrauss Transformations
- Joshua Brody and David Woodruff. Streaming Algorithms with One-Sided Estimation
- Mohammed Abdullah, Colin Cooper and Moez Draief. Viral Processes by Random Walks on Random Graphs
Accepted papers in Approx - Papers
- Michael Crouch and Andrew Mcgregor. Periodicity and Cyclic Shifts via Linear Sketches
- Adrian Dumitrescu, Minghui Jiang and Janos Pach. Opaque sets
- Nachshon Cohen and Zeev Nutov. A $(1+\ln 2)$-approximation algorithm for minimum-cost $2$-edge-connectivity augmentation of trees with constant radius
- Yair Bartal, Douglas Carroll, Adam Meyerson and Ofer Neiman. Bandwidth and Low Dimensional Embedding
- Timothy Carnes and David Shmoys. Primal-Dual Schema and Lagrangian Relaxation for the k-Location Routing Problem
- Sanjeev Arora and Rong Ge. New Tools for Graph Coloring
- Johan Håstad. Satisfying degree d equations over GF[2]^n
- Sagi Snir and Raphael Yuster. A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs
- Sandor Fekete, Tom Kamphans, Alexander Kroeller, Joseph Mitchell and Christiane Schmidt. Exploring and Triangulating a Region by a Swarm of Robots
- Venkatesan Chakaravarthy, Amit Kumar, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal. Scheduling Resources for Throughput Maximization
- Michael Kapralov and Rina Panigrahy. Multiplicative approximations of random walk transition probabilities
- Maurice Cheung and David Shmoys. A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
- M. Reza Khani and Mohammad Salavatipour. Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems
- Feodor Dragan and Ekkehard Koehler. An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- Anand Bhalgat, Deeparnab Chakrabarty and Sanjeev Khanna. Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs
- Anand Bhalgat, Deeparnab Chakrabarty and Sanjeev Khanna. Social Welfare in One-sided Matching Markets without Money
- Rohit Khandekar, Guy Kortsarz and Zeev Nutov. Approximating node-connectivity and prize-collecting network-design problems with degree constraints
- Chandan Dubey and Thomas Holenstein. Approximating lattice problems using an approximate shortest vector oracle
- Moran Feldman, Seffi Naor and Roy Schwartz. Improved Competitive Ratios for Submodular Secretary Problems
- Inge Li Gørtz and Viswanath Nagarajan. Locating Depots for Capacitated Vehicle Routing
- Parinya Chalermsook. Coloring and Maximum Independent Set of Rectangles
- Piotr Berman, Erik D. Demaine and Morteza Zadimoghaddam. O(1)-Approximations for Maximum Movement Problems
- Zhiyi Huang, Lei Wang and Yuan Zhou. Black-Box Reductions in Mechanism Design
- Sushant Sachdeva and Rishi Saket. Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
- Per Austrin, Mark Braverman and Eden Chlamtac. Inapproximability of NP-Complete Variants of Nash Equilibrium
- Marek Karpinski and Warren Schudy. Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
- Nikhil Bansal, Ravishankar Krishnaswamy and Barna Saha. On Capacitated Set Cover Problems
- Anand Louis, Prasad Raghavendra, Prasad Tetali and Santosh Vempala. Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions
- Khanh Do Ba and Piotr Indyk. Sparse recovery with partial support knowledge
|
PDF Format
Plain Text
