FOCS 2012 accepted paper list is here. Following are PDF pointers to online versions. Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies [arXiv] Thomas Sauerwald and He Sun Population Recovery and Partial Identification [pdf] Avi Wigderson and Amir Yehudayoff A direct product theorem for the two-party bounded-round public-coin communication complexity [pdf] Rahul Jain and Attila Pereszlenyi and Penghui Yao Positive Results for Concurrently Secure Computation in the Plain Model [pdf] Vipul Goyal Constructive Discrepancy Minimization by Walking on The Edges [arXiv] Shachar Lovett and Raghu Meka Making the Long Code Shorter [pdf] Boaz Barak and Parikshit Gopalan and Johan Hastad and Raghu Meka and Prasad Raghavendra and David Steurer On the homotopy test on surfaces [arXiv] Francis Lazarus and Julien Rivaud Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls [arXiv] Thomas Holenstein and Makrand Sinha Partially Symmetric Functions are Efficiently Isomorphism-Testable [arXiv] Eric Blais and Amit Weinstein and Yuichi Yoshida The computational hardness of counting in two-spin models on d-regular graphs [arXiv] Allan Sly and Nike Sun A PTAS for Computing the Supremum of Gaussian Processes [arXiv] Raghu Meka The tile assembly model is intrinsically universal [arXiv] David Doty and Jack H. Lutz and Matthew J. Patitz and Robert T. Schweller and Scott M. Summers and Damien Woods Hardness of Finding Independent Sets in Almost q-Colorable Graphs Subhash Khot and Rishi Saket The Privacy of the Analyst and The Power of the State Cynthia Dwork and Moni Naor and Salil Vadhan Higher Cell Probe Lower Bounds for Evaluating Polynomials Kasper Green Larsen Faster Algorithms for Rectangular Matrix Multiplication [arXiv] Francois Le Gall A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2 Julia Chuzhoy and Shi Li Iterative rounding approximation algorithms for degree-bounded node-connectivity network design [arXiv] Takuro Fukunaga and R. Ravi Pseudorandomness from Shrinkage [ECCC] Russell Impagliazzo and Raghu Meka and David Zuckerman An additive combinatorics approach relating rank to communication complexity [ECCC] Eli Ben-Sasson and Shachar Lovett and Noga Ron-Zewi Designing FPT algorithms for cut problems using randomized contractions Rajesh Chitnis and Marek Cygan and MohammadTaghi Hajiaghayi and Marcin Pilipczuk and Michaï¿½ Pilipczuk Sparse affine-invariant linear codes are locally testable [ECCC] Eli Ben-Sasson and Noga Ron-Zewi and Madhu Sudan A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions [arXiv] Daniel M. Kane How to Construct Quantum Random Functions [ePrint] Mark Zhandry A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs [pdf] Lyle Ramshaw and Robert E. Tarjan Matching with our Eyes Closed Gagan Goel and Pushkar Tripathi A New Infinity of Distance Oracles for Sparse Graphs Mihai Patrascu and Liam Roditty and Mikkel Thorup A Permanent Approach to the Traveling Salesman Problem Nisheeth K. Vishnoi Everywhere-Sparse Spanners via Dense Subgraphs [arXiv] Eden Chlamtac and Michael Dinitz and Robert Krauthgamer Learning-graph-based Quantum Algorithm for k-distinctness [arXiv] Aleksandrs Belovs Beck's three permutations conjecture: A counterexample and some consequences Alantha Newman and Ofer Neiman and Aleksandar Nikolov Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space [pdf] Sariel Har-Peled and Nirman Kumar On the complexity of finding narrow proofs [arXiv] Christoph Berkholz Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths Fabrizio Grandoni and Virginia Vassilevska Williams LP Rounding for k-Centers with Non-uniform Hard Capacities Marek Cygan and MohammadTaghi Hajiaghayi and Samir Khuller A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint [arXiv] Yuval Filmus and Justin Ward Faster SDP hierarchy solvers for local rounding algorithms Venkatesan Guruswami and Ali Kemal Sinop Combinatorial coloring of 3-colorable graphs [arXiv] Ken-ichi Kawarabayashi and Mikkel Thorup Approximation Limits of Linear Programs (Beyond Hierarchies) [arXiv] Gábor Braun and Samuel Fiorini and Sebastian Pokutta and David Steurer A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization Niv Buchbinder and Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz Lower bounds on Information Complexity via zero-communication protocols and applications [arXiv] Iordanis Kerenidis and Sophie Laplante and Virginie Lerays and Jeremie Roland and David Xiao Better Pseudorandom Generators from Milder Pseudorandom Restrictions Parikshit Gopalan and Raghu Meka and Omer Reingold and Luca Trevisan and Salil Vadhan Almost Optimal Canonical Property Testers for Satisfiability Christian Sohler On Range Searching with Semialgebraic Sets II Pankaj K. Agarwal and Jiri Matousek and Micha Sharir MIP* contains NEXP Tsuyoshi Ito and Thomas Vidick Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's normalization lemma Ketan D. Mulmuley Single Source - All Sinks Max Flows in Planar Digraphs Jakub Lacki and Yahav Nussbaum and Piotr Sankowski and Christian Wulff-Nilsen The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy [arXiv] Jeremiah Blocki and Avrim Blum and Anupam Datta and Or Sheffet Formulas Resilient to Short-Circuit Errors Yael Kalai and Allison Lewko and Anup Rao Efficient Interactive Coding Against Adversarial Noise [ECCC] Zvika Brakerski and Yael Tauman Kalai How to Allocate Tasks Asynchronously Dan Alistarh and Michael A. Bender and Seth Gilbert and Rachid Guerraoui New Limits to Classical and Quantum Instance Compression [pdf] Andrew Drucker Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits [ECCC] Chris Beck and Russell Impagliazzo and Shachar Lovett The Locality of Distributed Symmetry Breaking [arXiv] Leonid Barenboim and Michael Elkin and Seth Pettie and Johannes Schneider Representative sets and irrelevant vertices: New tools for kernelization [arXiv] Stefan Kratsch and Magnus Wahlström Approximating the Expansion Profile and Almost Optimal Local Graph Clustering [arXiv] Shayan Oveis Gharan and Luca Trevisan Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings [arXiv] Marek Cygan and Harold N. Gabow and Piotr Sankowski Learning Topic Models --- Going beyond SVD [arXiv] Sanjeev Arora and Rong Ge and Ankur Moitra Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification Xin Li The power of linear programming for valued CSPs [arXiv] Johan Thapper and Stanislav Zivny Constructing Non-Malleable Commitments: A Black-Box Approach Vipul Goyal and Chen-Kuei Lee and Rafail Ostrovsky and Ivan Visconti Active Property Testing [pdf] Maria-Florina Balcan and Eric Blais and Avrim Blum and Liu Yang The Dynamics of Influence Systems [arXiv] Bernard Chazelle Online Matching with Stochastic Rewards Aranyak Mehta and Debmalya Panigrahi Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas [ECCC] Gregory Valiant The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal [arXiv] Zhiyi Huang and Sampath Kannan How to Compute in the Presence of Leakage [ECCC] Shafi Goldwasser and Guy Rothblum On-line Indexing for General Alphabets Tsvi Kopelowitz Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg Split and Join: Strong Partitions and Universal Steiner Trees for Graphs [arXiv] Costas Busch and Chinmoy Dutta and Jaikumar Radhakrishnan and Rajmohan Rajaraman and Srivathsan Srinivasagopalan From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique Nir Bitansky and Omer Paneth Quasi-optimal multiplication of linear differential operators Alexandre Benoit and Alin Bostan and Joris van der Hoeven Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis Matthias Poloczek and Mario Szegedy Concave Generalized Flows with Applications to Market Equilibria [arXiv] Laszlo A. Vegh The Cutting Plane Method is Polynomial for Perfect Matchings Karthekeyan Chandrasekaran and Laszlo A. Vegh and Santosh S. Vempala Computing Multiplicities of Lie Group Representations [arXiv] Matthias Christandl and Brent Doran and Michael Walter A New Direction for Counting Perfect Matchings Taisuke Izumi and Tadashi Wadayama Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms [pdf] Fedor Fomin and Daniel Lokshtanov and Neeldhara Misra and Saket Saurabh Lower Bounds for Interactive Compression by Constant-Depth Circuits Arkadev Chattopadhyay and Rahul Santhanam
I have been teaching (courses related to algorithms and complexity) for the past six years (five years as a PhD student at GeorgiaTech, and the past one year at Princeton). One of the most challenging and interesting part of teaching is creating new exercises to help teach the important concepts in an efficient way. We often need lots of problems to include in homeworks, midterms, final exams and also to create practice problem sets.
We do not get enough time to teach all the concepts in class because the number of hours/week is bounded. I personally like to teach only the main concepts in class and design good problem sets so that students can learn the generalizations or extensions of the concepts by solving problems hands-on. This helps them develop their own intuitions about the concepts.
Whenever I need a new exercise I hardly open a physical textbook. I usually search on internet and find exercises from a course website (or) “extract” an exercise from a research paper. There are hundreds of exercises “hidden” in pdf files across several course homepages. Instructors often spend lots of time designing them. If these exercises can reach all the instructors and students across the world in an efficiently-indexed form, that will help everybody. Instructors will be happy that the exercises they designed are not confined to just one course. Students will have an excellent supply of exercises to hone their problem-solving skills.
During 2008, half-way through my PhD, I started collected the exercises I like in a private blog. At the same time I registered the domain trueshelf.com to make these exercises public. In 2011, towards the end of my PhD, I started using the trueshelf.com domain and made a public blog so that anybody can post an exercise. [ Notice that I did not use the trueshelf.com domain for three years. During these three years I got several offers ranging upto $5000 to sell the domain. So I knew I got the right name ] Soon, I realized that wordpress is somewhat “static” in nature and does not have enough “social” features I wanted. A screenshot of the old website is shown below.
The new version of TrueShelf is a social website enabling “crowd-sourcing” of exercises in any area. Here is the new logo, I am excited about
The goal of TrueShelf is to aid both the instructors and students by presenting quality exercises with tag-based indexing. Read the TrueShelf FAQ for more details. Note that we DO NOT allow users to post solutions. Each user may add his own “private” solution and notes to any exercise. I am planning to add more features soon.
In the long-run, I see TrueShelf becoming a ”Youtube for exercises”. Users will be able to create their own playlists of exercises (a.k.a problem sets) and will be recommended relevant exercises. Test-preparation agencies will be able to create their own channels to create sample tests.
Let’s see how TrueShelf evolves.