Accepted papers in Random - 27 Papers
|
- Guy Bresler, Elchanan Mossel and Allan Sly. Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms
- Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman and Orly Yahalom.On the Query Complexity of Testing Orientations for being Eulerian
- Nicla Bernasconi, Konstantinos Panagiotou and Angelika Steger. On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs
- Raphael Yuster. Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
- Homin Lee, Jeffrey Jackson, Rocco Servedio and Andrew Wan. Learning random monotone DNF
- Edo Liberty, Nir Ailon and Amit Singer. Dense Fast Random Projections and Lean Walsh Transforms
- David Woodruff. Corruption and Recovery-Efficient Locally Decodable Codes
- Noga Alon, Ido Ben Eliezer and Michael Krivelevich. Small sample spaces cannot fool low degree polynomials
- Andrej Bogdanov, Elchanan Mossel and Salil Vadhan. The complexity of distinguishing Markov Random Fields
- Hariharan Narayanan and Partha Niyogi. Sampling Hypersurfaces through Diffusion
- Tali Kaufman, Simon Litsyn and Ning Xie. Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
- Ariel Gabizon and Ronen Shaltiel. Increasing the Output Length of Zero-Error Dispersers
- Matei David, Toniann Pitassi and Emanuele Viola. Improved Separations between Nondeterministic and Randomized Multiparty Communication
- Vikraman Arvind and Partha Mukhopadhyay. Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size
- Venkat Guruswami, James Lee and Avi Wigderson. Euclidean sections of L_1^N with sublinear randomness and error-correcting codes over the reals
- Eli Ben-Sasson and Michael Viderman. Tensor Products of Weakly Smooth Codes are Robust
- Hang Dinh and Alexander Russell. Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
- dan Gutfreund and Salil Vadhan. Limitations of Hardness vs. Randomness under Uniform Reductions
- Martin Fürer and Shiva Kasiviswanathan. Approximately Counting Embeddings into Random Graphs
- Anup Rao and David Zuckerman. Extractors for Three Uneven-Length Sources
- Anup Rao. A 2-Source Almost-Extractor for Linear Entropy
- Dan Gutfreund and Guy Rothblum. The Complexity of Local List Decoding
- Eric Blais. Improved Bounds for Testing Juntas
- Kai-Min Chung and Salil Vadhan. Tight Bounds for Hashing Block Sources
- Avner Magen and Anastasios Zouzias. Nearly tight dimensionality reductions the preserve volumes
- Bela Csaba and Ali Shokoufandeh. Optimal Random Matchings on Trees and Application
- Gregory Sorkin. The Power of Choice in a Generalized Polya Urn Model
Accepted papers in Approx - 20 Papers
- Yuval Lando and Zeev Nutov. Inapproximability of Survivable Networks
- Zeev Nutov. Approximating Directed Weighted-Degree Constrained Networks
- Nir Halman and Chung-Lun Li. Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks
- Jean Cardinal and Eythan Levy. Connected Vertex Covers in Dense Graphs
- Venkat Guruswami and Prasad Raghavendra. Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness
- MohammadAli Safari and Mohammad Salavatipour. A constant factor approximation for minimum λ-edge-connected κ-subgraph with metric costs
- Richard Matthew McCutchen and Samir Khuller. Streaming algorithms for k-center clustering with outliers and with anonymity
- Guy Kortsarz, Michael Langberg and Zeev Nutov. Approximating Maximum Subgraphs Without Short Cycles
- Aravind Srinivasan. Budgeted allocations in the full-information setting
- Thanh Nguyen. A simple LP relaxation for the Asymmetric Traveling Salesman Problem
- Mihai B\u{a}doiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos and Morteza Zadimoghaddam. Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
- Eden Chlamtac and Gyanit Singh. Improved Approximation Guarantees Through Higher Levels of SDP Hierarchies
- Viswanath Nagarajan and R Ravi. The Directed Minimum Latency Problem
- Monaldo Mastrolilli, Nikolaus Mutsanas and Ola Svensson. Approximating Single Machine Scheduling with Scenarios
- Arash Asadpour, Uriel Feige and Amin Saberi. On Max-Min Fair Allocations and Hypergraph Matchings
- Adrian Dumitrescu and Minghui Jiang. Sweeping points
- Lukasz Kowalik and Marcin Mucha. Deterministic 7/8-approximation for the Metric Maximum TSP
- Jacob Scott and David Karger. Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP
- Micah Adler and Brent Heeringa. Approximating Optimal Binary Decision Trees
- Shashi Mittal and Andreas S. Schulz. A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined Into One
|