Author: kintali

by

Book Review of “Boosting : Foundations and Algorithms”

Following is my review of Boosting : Foundations and Algorithms (by Robert E. Schapire and Yoav Freund) to appear in the  SIGACT book review column soon.

Boosting

—————————————————————————————————————-

Book : Boosting : Foundations and Algorithms (by Robert E. Schapire and Yoav Freund)
Reviewer : Shiva Kintali

Introduction

You have k friends, each one earning a small amount of money (say 100 dollars) every month by buying and selling stocks. One fine evening, at a dinner conversation, they told you their individual “strategies” (after all, they are your friends). Is it possible to “combine” these individual strategies and make million dollars in an year, assuming your initial capital is same as your average friend ?

You are managing a group of k “diverse” software engineers each one with only an “above-average” intelligence. Is it possible to build a world-class product using their skills ?

The above scenarios give rise to fundamental theoretical questions in machine learning and form the basis of Boosting. As you may know, the goal of machine learning is to build systems that can adapt to their environments and learn from their experience. In the last five decades, machine learning has impacted almost every aspect of our life, for example, computer vision, speech processing, web-search, information retrieval, biology and so on. In fact, it is very hard to name an area that cannot benefit from the theoretical and practical insights of machine learning.

The answer to the above mentioned questions is Boosting, an elegant method for driving down the error of the combined classifier by combining a number of weak classifiers. In the last two decades, several variants of Boosting are discovered. All these algorithms come with a set of theoretical guarantees and made a deep practical impact on the advances of machine learning, often providing new explanations for existing prediction algorithms.

Boosting : Foundations and Algorithms, written by the inventors of Boosting, deals with variants of AdaBoost, an adaptive boosting method. Here is a quick explanation of the basic version of AdaBoost.

AdaBoost makes iterative calls to the base learner. It maintains a distribution over training examples to choose the training sets provided to the base learner on each round. Each training example is assigned a weight, a measure of importance of correctly classifying an example on the current round. Initially, all weights are set equally. On each round, the weights of incorrectly classified examples are increased so that, “hard” examples get successively higher weight. This forces the base learner to focus its attention on the hard example and drive down the generalization errors.

AdaBoost is fast and easy to implement and the only parameter to tune is the number of rounds. The actual performance of boosting is dependent on the data.

Summary

Chapter 1 provides a quick introduction and overview of Boosting algorithms with practical examples. The rest of the book is divided into four major parts. Each part is divided into 3 to 4 chapters.

Part I studies the properties and effectiveness of AdaBoost and theoretical aspects of minimizing its training and generalization errors. It is proved that AdaBoost drives the training error down very fast (as a function of the error rates of the weak classifiers) and the generalization error arbitrarily close to zero. Basic theoretical bounds on the generalization error show that AdaBoost overfits, however empirical studies show that AdaBoost does not overfit. To explain this paradox, a margin-based analysis is presented to explain the absence of overfitting.
Part II explains several properties of AdaBoost using game-theoretic interpretations. It is shown that the principles of Boosting are very intimately related to the classic min-max theorem of von Neumann. A two-player (the boosting algorithm and the weak learning algorithm) game is considered and it is shown that AdaBoost is a special case of a more general algorithm for playing a repeated game. By reversing the roles of the players, a solution is obtained for the online prediction model thus establishing a connection between Boosting and online learning. Loss minimization is studied and AdaBoost is interpreted as an abstract geometric framework for optimizing a particular objective function. More interestingly, AdaBoost is viewed as a special case of more general methods for optimization of an objective function such as coordinate descent and functional gradient descent.

Part III explains several methods of extending AdaBoost to handle classifiers with more than two output classes. AdaBoost.M1, AdaBoost.MH and AdaBoost.MO are presented along with their theoretical analysis and practical applications. RankBoost, an extension of AdaBoost to study ranking problems is studied. Such an algorithm is very useful, for example, to rank webpages based on their relevance to a given query.

Part IV is dedicated to advanced theoretical topics. Under certain assumptions, it is proved that AdaBoost can handle noisy-data and converge to the best possible classifier. An optimal boost-by-majority algorithm is presented. This algorithm is then modified to be adaptive leading to an algorithm called BrownBoost.

Many examples are given throughout the book to illustrate the empirical performance of the algorithms presented. Every chapter ends with Summary and Bibliography mentioning the related publications. There are well-designed exercises at the end of every chapter. Appendix briefly outlines some required mathematical background.

Opinion

Boosting book is definitely a very good reference text for researchers in the area of machine learning. If you are new to machine learning, I encourage you to read an introductory machine learning book (for example, Machine Learning by Tom M. Mitchell) to better understand and appreciate the concepts. In terms of being used in a course, a graduate-level machine learning course can be designed from the topics covered in this book. The exercises in the book can be readily used for such a course.

Overall this book is a stimulating learning experience. It has provided me new perspectives on theory and practice of several variants of Boosting algorithms. Most of the algorithms in this book are new to me and I had no difficulties following the algorithms and the corresponding theorems. The exercises at the end of every chapter made these topics much more fun to learn.

The authors did a very good job compiling different variants of Boosting algorithms and achieved a nice balance between theoretical analysis and practical examples. I highly recommend this book for anyone interested in machine learning.

—————————————————————————————————————-

by

FOCS 2013 Accepted Papers (with pdf files)

FOCS 2013 accepted paper list is here. Following are PDF pointers to online versions.

  • OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, by Jelani Nelson and Huy L. Nguyen [arXiv]
  • A Polynomial Time Algorithm for Lossy Population Recovery, by Ankur Moitra and Michael Saks [arXiv]
  • Direct products in communication complexity, by Mark Braverman, Anup Rao, Omri Weinstein and Amir Yehudayoff [ECCC]
  • Arithmetic circuits: A chasm at depth three, by Ankit Gupta, Pritish Kamath, Neeraj Kayal and Ramprasad Saptharishi [ECCC]
  • Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs, by Joseph Cheriyan and Laszlo A. Vegh [arXiv]
  • The Parity of Directed Hamiltonian Cycles, by Andreas Björklund and Thore Husfeldt [arXiv]
  • Approximating Minimization Diagrams and Generalized Proximity Search, by Sariel Har-Peled and Nirman Kumar [arXiv]
  • Quantum 3-SAT is QMA1-complete, by David Gosset and Daniel Nagaj [arXiv]
  • The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation is Constant, by Vittorio Bilò, Michele Flammini and Luca Moscardelli
  • Strong LTCs with inverse poly-log rate and constant soundness, by Michael Viderman [ECCC]
  • All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs, by Ken-ichi Kawarabayashi and Yusuke Kobayashi
  • Approximating Bin Packing within O(log OPT * log log OPT) bins, by Thomas Rothvoss [arXiv]
  • Common information and unique disjointness, by Gábor Braun, and Sebastian Pokutta [ECCC]
  • Chasing the k-colorability threshold, by Amin Coja-Oghlan and Dan Vilenchik [arXiv]
  • Three-player entangled XOR games are NP-hard to approximate, by Thomas Vidick [arXiv]
  • Fully Dynamic $(1+\epsilon)$-Approximate Matchings, by Manoj Gupta, and Richard Peng [arXiv]
  • Estimating the distance from testable affine-invariant properties, by Hamed Hatami and Shachar Lovett [arXiv]
  • Approximation algorithms for Euler genus and related problems, by Chandra Chekuri and Anastasios Sidiropoulos [arXiv]
  • Polar Codes: Speed of polarization and polynomial gap to capacity, by Venkatesan Guruswami and Patrick Xia [arXiv]
  • An Optimal Randomized Online Algorithm for Reordering Buffer Management, by Noa Avigdor-Elgrabli and Yuval Rabani [arXiv]
  • Approximation Schemes for Maximum Weight Independent Set of Rectangles, by Anna Adamaszek and Andreas Wiese
  • Playing Non-linear Games with Linear Oracles, by Dan Garber, and Elad Hazan
  • Faster Canonical Forms for Strongly Regular Graphs, by Laszlo Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng and John Wilmes
  • Constant rate PCPs for circuit-SAT with sublinear query complexity, by Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir and Henning Stichtenoth [pdf] [video]
  • How to Approximate A Set Without Knowing Its Size In Advance, by Rasmus Pagh, Gil Segev and Udi Wieder [arXiv]
  • Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs, by Michael A. Forbes, and Amir Shpilka [arXiv]
  • On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions, by Natan Rubin
  • Element Distinctness, Frequency Moments, and Sliding Windows, by Paul Beame, Raphael Clifford and Widad Machmouchi
  • Spatial mixing and approximation algorithms for graphs with bounded connective constant, by Alistair Sinclair, Piyush Srivastava and Yitong Yin
  • Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors, by Harold N. Gabow and Piotr Sankowski [arXiv]
  • A linear time approximation scheme for Euclidean TSP, by Yair Bartal and Lee-Ad Gottlieb
  • Interactive Coding, Revisited, by Kai-Min Chung, Rafael Pass and Sidharth Telang [ePrint]
  • Improved approximation for 3-dimensional matching via bounded pathwidth local search, by Marek Cygan [arXiv]
  • Strong Backdoors to Bounded Treewidth SAT, by Serge Gaspers and Stefan Szeider [arXiv]
  • Explicit Subspace Designs, by Venkatesan Guruswami and Swastik Kopparty [ECCC]
  • Dynamic Approximate All-Pairs Shortest Paths: Breaking the $ \tilde O(mn) $ Barrier and Derandomization, Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai
  • On Randomized Memoryless Algorithms for the Weighted $k$-server Problem, by Ashish Chiplunkar and Sundar Vishwanathan [arXiv]
  • Constant-Round Concurrent Zero Knowledge From P-Certificates, by Kai-Min Chung, Huijia Lin and Rafael Pass [ePrint]
  • Learning Sums of Independent Integer Random Variables, by Constantinos Daskalakis, Ilias Diakonikolas, Ryan O’Donnell, Rocco A. Servedio and Li-Yang Tan [pdf]
  • Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses, by Parinya Chalermsook, Bundit Laekhanukit, and Danupon Nanongkai
  • Online Node-weighted Steiner Forest and Extensions via Disk Paintings, by Mohammad Taghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi
  • Klee’s Measure Problem Made Easy, by Timothy M. Chan
  • Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy, by Xin Li [arXiv]
  • Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back, by Aleksander Madry
  • Fourier sparsity, spectral norm, and the Log-rank conjecture, Hing Yin Tsang, Chung Hoi Wong, Ning Xie and Shengyu Zhang [arXiv]
  • Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring, by Vida Dujmović, Pat Morin, and David R. Wood
  • Average Case Lower Bounds for Monotone Switching Networks, by Yuval Filmus, Toniann Pitassi, Robert Robere and Stephen A. Cook [arXiv]
  • PCPs via low-degree long code and hardness for constrained hypergraph coloring, by Irit Dinur and Venkatesan Guruswami
  • The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable, by Marek Cygan, Dániel Marx, Marcin Pilipczuk and Michał Pilipczuk [arXiv]
  • On the communication complexity of sparse set disjointness and exists-equal problems, Mert Sağlam and Gábor Tardos [arXiv]
  • The Simple Economics of Approximately Optimal Auctions, Saeed Alaei, Hu Fu, Nima Haghpanah and Jason Hartline [arXiv]
  • Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems, by Yin Tat Lee and Aaron Sidford [arXiv]
  • Nearly Maximum Flows in Nearly Linear Time, by Jonah Sherman [arXiv]
  • Improved Average-Case Lower Bounds for DeMorgan Formula Size, by Ilan Komargodski, Ran Raz and Avishay Tal [ECCC]
  • Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, by Vitaly Feldman and Jan Vondrak
  • Towards a better approximation for Sparsest Cut?, by Sanjeev Arora, Rong Ge and Ali Kemal Sinop [arXiv]
  • Bandits with Knapsacks, Ashwinkumar Badanidiyuru, Robert Kleinberg and Aleksandrs Slivkins [arXiv]
  • Approximate Constraint Satisfaction Requires Large LP Relaxations, by Siu On Chan, James R. Lee, Prasad Raghavendra and David Steurer
  • Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence, by Mikkel Thorup
  • An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree, by Jochen Koenemann, Sina Sadeghian and Laura Sanità [arXiv]
  • A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits, by Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider [arXiv]
  • The Complexity of Approximating Vertex Expansion, by Anand Louis, Prasad Raghavendra and Santosh Vempala [arXiv]
  • Tight Bounds for Set Disjointness in the Message Passing Model, by Mark Braverman, Faith Ellen, Rotem Oshman, Toni Pitassi and Vinod Vaikuntanathan [arXiv]
  • Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees, Adam Marcus, Daniel A. Spielman and Nikhil Srivastava [arXiv]
  • Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits, by Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters
  • Iterative Row Sampling, by Mu Li, Gary L. Miller, and Richard Peng [arXiv]
  • Simultaneous Resettability from One-Way Functions, Kai-Min Chung, Rafail Ostrovsky, Rafael Pass and Ivan Visconti
  • Rational Protocol Design: Cryptography Against Incentive-driven Adversaries, by Juan Garay , Jonathan Katz, Ueli Maurer, Bjoern Tackmann and Vassilis Zikas
  • Non-positive curvature, and the planar embedding conjecture, by Anastasios Sidiropoulos [arXiv]
  • Local Privacy and Statistical Minimax Rates, by John C. Duchi, Michael I. Jordan, and Martin J. Wainwright [arXiv]
  • The Moser-Tardos Framework with Partial Resampling, by David G. Harris and Aravind Srinivasan
  • On Clustering Induced Voronoi Diagrams, Danny Z. Chen, Ziyun Huang, Yangwei Liu, and Jinhui Xu
  • A forward-backward single-source shortest paths algorithm, by David Wilson and Uri Zwick
  • An O(c^k) n 5-Approximation Algorithm for Treewidth, by Hans L. Bodlaender, Paal G. Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov and Michal Pulipczuk [arXiv]
  • Understanding Incentives: Mechanism Design becomes Algorithm Design, by Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg [arXiv]
  • Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers, by Andrew Drucker
  • From Unprovability to Environementally Friendly Protocols, by Ran Canetti, Huijia Lin and Rafael Pass
  • Adaptive Seeding in Social Networks, by Lior Seeman and Yaron Singer
  • Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy, by Raef Bassily, Adam Groce, Jonathan Katz and Adam Smith

———————————————————————————————————————————————————–

by

TrueShelf 1.0

One year back (on 6/6/12) I announced a beta version of TrueShelf, a social-network for sharing exercises and puzzles especially in mathematics and computer science. After an year of testing and adding new features, now I can say that TrueShelf is out of beta.

TrueShelf turned out to be a very useful website. When students ask me for practice problems (or books) on a particular topic, I simply point them to trueshelf and tell them the tags related to that topic. When I am advising students on research projects, I first tell them to solve all related problems (in the first couple of weeks) to prepare them to read research papers.

Here are the features in TrueShelf 1.0.

  • Post an exercise (or) multiple-choice question (or) video (or) notes.
  • Solve any multiple-choice question directly on the website.
  • Add topic and tags to any post
  • Add source or level (high-school/undergraduate/graduate/research).
  • Show text-books related to a post
  • Show related posts for every post.
  • View printable version (or) LaTex version of any post.
  • Email / Tweet / share on facebook (or) Google+ any post directly from the post.
  • Add any post to your Favorites
  • Like (a.k.a upvote) any post.

Feel free to explore TrueShelf, contribute new exercises and let me know if you have any feedback (or) new features you want to see. You can also follow TrueShelf on facebook, twitter and google+. Here is a screenshot highlighting the important features.

trueshelf

by

Graceful Diameter-6 Trees

Graceful Tree Conjecture is one of my favorite open problems (See this earlier post). Trees with diameter 4 and 5 are known to be graceful a decade ago.

One of my advisees, Matt Superdock, made progress towards proving that all diameter 6 trees are graceful. Matt is an undergraduate senior in our Mathematics Department. He proved that an interesting class of diameter 6 trees are graceful. His thesis is available here.

I hope his work motivates more researchers to make progress towards resolving Graceful Tree Conjecture, particularly for diameter 6 trees. Matt’s work really tests the limit of current techniques. Perhaps we need new techniques/insights to prove that all diameter 6 trees are graceful.

 

 

 

by

Happy Birthday Paul Erdos

Today (March 26 2013) is the 100th Birthday of Paul Erdos. The title of my Blog is inspired by one of his famous sayings “My Brain is Open”. In one of my earlier posts I mentioned a book titled “The Man Who Loved Only Numbers” about his biography.

Paul Erdos published more than 1500 papers. Most of them left a legacy of open problems and conjectures. What is your favorite open problem from Erdos’s papers ? Leave a comment. Hope we can solve some of his open problems during this special year.

Here are some interesting links :

If you know any interesting Erdos links, leave a comment.

Here is a painting of Paul Erdos, I made couple years back.

paul_erdos_painting

by

STOC 2013 Accepted Papers (with pdf files)

STOC 2013 accepted paper list is here. Following are PDF pointers to online versions.

————————————————————————————-

Max flows in O(nm) time or less [pdf]
James Orlin (MIT)

Multidimensional Approximate Agreement in Byzantine Asynchronous Systems
Hammurabi Mendes (Brown University) and Maurice Herlihy (Brown University)

Non-Black-Box Simulation in the Fully Concurrent Setting
Vipul Goyal (Microsoft Research, India)

Approximation Resistance from Pairwise Independent Subgroups [ECCC]
Siu On Chan (UC Berkeley)

Average-Case Lower Bounds for Formula Size [ECCC]
Ilan Komargodski (Weizmann Institute of Science) and Ran Raz (Weizmann Institute of Science)

New Independent Source Extractors with Exponential Improvement [ECCC]
Xin Li (University of Washington)

Random Lattice Triangulations: Structure and Algorithms [arXiv]
Pietro Caputo (University of Rome III), Fabio Martinelli (University of Rome III), Alistair Sinclair (UC Berkeley), and Alexandre Stauffer (University of Rome III)

The Complexity of Non-Monotone Markets [arXiv]
Xi Chen (Columbia University), Dimitris Paparas (Columbia University), and Mihalis Yannakakis (Columbia University)

Optimal Euclidean spanners: really short, thin and lanky [arXiv]
Michael Elkin (Ben-Gurion University) and Shay Solomon (Weizmann Institute of Science)

Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression [arXiv]
Xiangrui Meng (Stanford University) and Michael W. Mahoney (Stanford University)

Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data [ePrint]
Nir Bitansky (Tel Aviv University), Ran Canetti (Boston University and Tel Aviv University), Alessandro Chiesa (MIT), and Eran Tromer (Tel Aviv University)

Sparsity lower bounds for dimensionality reducing maps [arXiv]
Jelani Nelson (Institute for Advanced Study) and Huy L. Nguyen (Princeton University)

Approximating k-Median via Pseudo-Approximation [arXiv]
Shi Li (Princeton University) and Ola Svensson (EPFL)

Byzantine Agreement in Polynomial Expected Time
Valerie King (University of Victoria) and Jared Saia (University of New Mexico)

Equivalence of Deterministic One-Counter Automata is NL-complete [arXiv]
Stanislav Bohm (Technical University of Ostrava), Stefan Goller (University of Bremen), and Petr Jancar (Technical University of Ostrava)

Answering n^{2+o(1)} Counting Queries with Differential Privacy is Hard [arXiv]
Jonathan Ullman (Harvard University)

Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond [ePrint]
Shafi Goldwasser (MIT), Yael Kalai (Microsoft Research, New England), Raluca Ada Popa (MIT), Vinod Vaikuntanathan (University of Toronto), and Nickolai Zeldovich (MIT)

Lower bounds for RAMs and quantifier elimination
Miklos Ajtai (IBM Almaden Research Center)

New Bounds on Matching Vector Families [arXiv]
Abhishek Bhowmick (University of Texas at Austin), Zeev Dvir (Princeton University), and Shachar Lovett (UC San Diego)

The complexity of finite-valued CSPs [arXiv]
Johan Thapper (Universite Paris-Sud 11) and Stanislav Zivny (University of Warwick)

Structured Recursive Separator Decompositions for Planar Graphs in Linear Time [arXiv]
Philip N. Klein (Brown University), Shay Mozes (MIT), and Christian Sommer (MIT)

Inverting well-conditioned matrices in Quantum Logspace
Amnon Ta-Shma (Tel-Aviv University)

List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound [ECCC]
Venkatesan Guruswami (Carnegie Mellon University) and Chaoping Xing (Nanyang Technological University)

Quasipolynomial-time Canonical Form for Steiner Designs
Laszlo Babai (University of Chicago) and John Wilmes (University of Chicago)

Constraint Satisfaction, Packet Routing, and the Lovasz Local Lemma [pdf]
David G. Harris (University of Maryland) and Aravind Srinivasan (University of Maryland)

Low Rank Approximation and Regression in Input Sparsity Time [arXiv]
Kenneth L. Clarkson (IBM Almaden Research) and David P. Woodruff (IBM Almaden Research)

Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
Aaron Bernstein (Columbia University)

A o(n) monotonicity tester for boolean functions over the hypercube
Deeparnab Chakrabarty (Microsoft Research, India) and C. Seshadhri (Sandia National Laboratories, Livermore)

On the list decodability of random linear codes with large error rates
Mary Wootters (University of Michigan)

Simple Deterministic Algorithms for Fully Dynamic Maximal Matching [arXiv]
Ofer Neiman (Ben-Gurion University) and Shay Solomon (Weizmann Institute of Science)

Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems [HTML]
Sariel Har-Peled (University of Illinois at Urbana Champaign) and Benjamin Raichel (University of Illinois at Urbana Champaign)

Every locally characterized affine-invariant property is testable [arXiv]
Arnab Bhattacharyya (DIMACS), Eldar Fischer (Technion), Hamed Hatami (McGill), Pooya Hatami (University of Chicago), and Shachar Lovett (UC San Diego)

Superlinear advantage for exact quantum algorithms [arXiv]
Andris Ambainis (University of Latvia)

Efficient rounding for the noncommutative Grothendieck inequality [arXiv]
Assaf Naor (New York University), Oded Regev (New York University), and Thomas Vidick (MIT)

A node-capacitated Okamura-Seymour theorem [arXiv]
James R. Lee (University of Washington), Manor Mendel (Open University), and Mohammad Moharrami (University of Washington)

Lee-Yang Theorems and the Complexity of Computing Averages [arXiv]
Alistair Sinclair (UC Berkeley) and Piyush Srivastava (UC Berkeley)

Beyond Worst-Case Analysis in Private Singular Vector Computation [arXiv]
Moritz Hardt (IBM Almaden Research) and Aaron Roth (University of Pennsylvania)

Classical Hardness of Learning with Errors
Zvika Brakerski (Stanford University), Adeline Langlois (ENS de Lyon), Chris Peikert (Georgia Tech), Oded Regev (New York University), and Damien Stehle (ENS de Lyon)

Coevolutionary Opinion Formation Games
Kshipra Bhawalkar (Stanford University), Sreenivas Gollapudi (Microsoft Research, Silicon Valley), and Kamesh Munagala (Duke University)

Predicate Encryption for Circuits
Sergey Gorbunov (University of Toronto), Vinod Vaikuntanathan (University of Toronto), and Hoeteck Wee (George Washington University)

On the complexity of Trial and Error [arXiv]
Xiaohui Bei (Nanyang Technological University), Ning Chen (Nanyang Technological University), and Shengyu Zhang (The Chinese University of Hong Kong)

Fast Routing Table Construction Using Small Messages [arXiv]
Christoph Lenzen (Weizmann Institute of Science) and Boaz Patt-Shamir (Tel Aviv University)

Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas [arXiv]
Manindra Agrawal (Indian Institute of Technology, Kanpur), Chandan Saha (Indian Institute of Science), and Nitin Saxena (Hausdorff Center for Mathematics)

Explicit Lower Bounds via Geometric Complexity Theory [arXiv]
Peter Burgisser (University of Paderborn) and Christian Ikenmeyer (University of Paderborn)

Shielding circuits with groups [ePrint]
Eric Miles (Northeastern University) and Emanuele Viola (Northeastern University)

Extending continuous maps: polynomiality and undecidability [pdf]
Martin Cadek (Masaryk University Brno), Marek Krcal (Charles University Prague), Jiri Matousek (Charles University Prague and ETH Zurich), Lukas Vokrinek (Masaryk University Brno), and Uli Wagner (EPFL)

Testing Subdivision-Freeness: Property Testing Meets Structural Graph Theory
Ken-ichi Kawarabayashi (National Institute of Informatics and JST ERATO Kawarabayashi Project) and Yuichi Yoshida (National Institute of Informatics and Preferred Infrastructure, Inc.)

Some Trade-off Results for Polynomial Calculus
Chris Beck (Princeton University), Jakob Nordstrom (KTH Royal Institute of Technology), and Bangsheng Tang (Tsinghua University)

Going After the k-SAT Threshold [arXiv]
Amin Coja-Oghlan (Goethe University) and Konstantinos Panagiotou (University of Munich)

Composable and Efficient Mechanisms [arXiv]
Vasilis Syrgkanis (Cornell University) and Eva Tardos (Cornell University)

Tatonnement Beyond Gross Substitutes? Gradient Descent to the Rescue
Yun Kuen Cheung (New York University), Richard Cole (New York University), and Nikhil Devanur (Microsoft Research, Redmond)

Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
David Eisenstat (Brown University) and Philip N. Klein (Brown University)

The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
Albert Gu (Carnegie Mellon University), Anupam Gupta (Carnegie Mellon University), and Amit Kumar (Indian Institute of Technology, Delhi)

On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs
Anupam Gupta (Carnegie Mellon University), Kunal Talwar (Microsoft Research, Silicon Valley), and David Witmer (Carnegie Mellon University)

Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids [arXiv]
Deeparnab Chakrabarty (Microsoft Research, India), C. Seshadhri (Sandia National Labs, Livermore), and Deeparnab Chakrabarty (Microsoft Research, India)

On the Concrete Efficiency of Probabilistically Checkable Proofs [ECCC]
Eli Ben-Sasson (Technion and MIT), Alessandro Chiesa (MIT), Daniel Genkin (Technion), and Eran Tromer (Tel Aviv University)

Polynomial-time perfect matchings in dense hypergraphs
Peter Keevash (Queen Mary, University of London), Fiachra Knox (Queen Mary, University of London), and Richard Mycroft (University of Birmingham)

Large-Treewidth Graph Decompositions and Applications
Chandra Chekuri (University of Illinois at Urbana-Champaign) and Julia Chuzhoy (Toyota Technological Institute, Chicago)

Differential Privacy for the Analyst via Private Equilibrium Computation [arXiv]
Justin Hsu (University of Pennsylvania), Aaron Roth (University of Pennsylvania), and Jonathan Ullman (Harvard University)

Succinct Sampling from Discrete Distributions [pdf]
Karl Bringmann (Max Planck Institute for Informatics) and Kasper Green Larsen (MADALGO, Aarhus University)

The Orbit Problem in Higher Dimensions [pdf]
Ventsislav Chonev (Oxford University), Joel Ouaknine (Oxford University), and James Worrell (Oxford University)

Homomorphic Fingerprints under Misalignments
Alexandr Andoni (Microsoft Research, Silicon Valley), Assaf Goldberger (Tel Aviv University), Andrew McGregor (University of Massachusetts), and Ely Porat (Bar-Ilan University)

Approximation Resistance on Satisfiable Instances for Predicates with Few Accepting Inputs
Sangxia Huang (KTH Royal Institute of Technology)

An Information Complexity Approach to Extended Formulations [ECCC]
Mark Braverman (Princeton University) and Ankur Moitra (Institute for Advanced Study)

Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem
Niv Buchbinder (Tel Aviv University), Joseph (Seffi) Naor (Technion), and Roy Schwartz (Microsoft Research, Redmond)

A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut [arXiv]
Daniel Kane (Stanford University) and Raghu Meka (Institute for Advanced Study and DIMACS)

Analysis of Spectral Partitioning through Higher Order Spectral Gap [arXiv]
Tsz Chiu Kwok (The Chinese University of Hong Kong), Lap Chi Lau (The Chinese University of Hong Kong), Yin Tat Lee (The Chinese University of Hong Kong), Shayan Oveis Gharan (Stanford University), and Luca Trevisan (Stanford University)

Quantum de Finetti Theorems under Local Measurements with Applications [arXiv]
Fernando G.S.L. Brandao (ETH Zurich) and Aram W. Harrow (University of Washington)

Stochastic Combinatorial Optimization via Poisson Approximation [arXiv]
Jian Li (IIIS, Tsinghua University) and Wen Yuan (IIIS, Tsinghua University)

Natural Proofs, Derandomization, and Lower Bounds [arXiv]
Ryan Williams (Stanford University)

Majority is Stablest : Discrete and SoS [arXiv]
Anindya De (UC Berkeley), Elchanan Mossel (UC Berkeley), and Joe Neeman (UC Berkeley)

Combinatorial Walrasian Equilibrium
Michal Feldman (The Hebrew University of Jerusalem and Harvard University), Nikolai Gravin (Nanyang Technological University), and Brendan Lucier (Microsoft Research, New England)

Simultaneous Auctions are (almost) Efficient [arXiv]
Michal Feldman (The Hebrew University of Jerusalem and Harvard University), Hu Fu (Cornell University), Nikolai Gravin (Nanyang Technological University), and Brendan Lucier (Microsoft Research, New England)

The Geometry of Differential Privacy: The Sparse and Approximate Cases [arXiv]
Aleksandar Nikolov (Rutgers University), Kunal Talwar (Microsoft Research, Silicon Valley), and Li Zhang (Microsoft Research, Silicon Valley)

Fully device-independent quantum key distribution [arXiv]
Umesh Vazirani (UC Berkeley) and Thomas Vidick (MIT)

Delegation for Bounded Space
Yael Tauman Kalai (Microsoft Research, New England), Ran Raz (Weizmann Institute of Science), and Ron D. Rothblum (Weizmann Institute of Science)

A new family of locally correctable codes based on degree-lifted algebraic geometry codes [ECCC]
Eli Ben Sasson (Technion and MIT), Ariel Gabizon (Technion), Yohay Kaplan (Technion), Swatik Kopparty (Rutgers University), and Shubangi Saraf (Rutgers University)

Interactive Proofs of Proximity: Delegating Computation in Sublinear Time
Guy Rothblum (Microsoft Research, Silicon Valley), Salil Vadhan (Harvard University), and Avi Wigderson (Institute for Advanced Studies)

How Robust are Linear Sketches to Adaptive Inputs? [arXiv]
Moritz Hardt (IBM Almaden Research) and David P. Woodruff (IBM Almaden Research)

The Approximate Rank of a Matrix and its Algorithmic Applications [ECCC]
Noga Alon (Tel Aviv University) and Santosh Vempala (Georgia Tech)

Communication Lower Bounds Using Directional Derivatives [ECCC]
Alexander A. Sherstov (UC Los Angelos)

Fast approximation algorithms for the diameter and radius of sparse graphs [pdf]
Liam Roditty (Bar Ilan University) and Virginia Vassilevska Williams (UC Berkeley and Stanford University)

Approximation Guarantees for the Quantum Local Hamiltonian Problem and Limitations for Quantum PCPs
Fernando G.S.L. Brandao (ETH Zurich) and Aram W. Harrow (University of Washington)

On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography [ePrint]
Omer Paneth (Boston University) and Nir Bitansky (Tel Aviv University)

THE LOSS OF SERVING IN THE DARK
Yossi Azar (Tel Aviv University), Ilan Cohen (Tel Aviv University), and Iftah Gamzu (Tel Aviv University)

Tight Bounds for Online Vector Bin Packing
Yossi Azar (Tel Aviv University), Ilan Cohen (Tel Aviv University), Seny Kamara (Microsoft Research, Redmond), and Bruce Shepherd (McGill University)

A Complete Dichotomy Rises from the Capture of Vanishing Signatures [arXiv]
Jin-Yi Cai (University of Wisconsin at Madison), Heng Guo (University of Wisconsin at Madison), and Tyson Williams (University of Wisconsin at Madison)

A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time [arXiv]
Jonathan A. Kelner (MIT), Lorenzo Orecchia (MIT), Aaron Sidford (MIT), and Zeyuan Allen Zhu (MIT)

Low-rank Matrix Completion using Alternating Minimization [arXiv]
Prateek Jain (Microsoft Research, India), Praneeth Netrapalli (The University of Texas at Austin), and Sujay Sanghavi (The University of Texas at Austin)

Multi-Stage Propagation and Quasipolynomial-Time Isomorphism Testing of Steiner 2-Systems
Xi Chen (Columbia University), Xiaorui Sun (Columbia University), and Shang-Hua Teng (University of Southern California)

Strong ETH Holds For Regular Resolution
Chris Beck (Princeton University) and Russell Impagliazzo (UC San Diego)

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques [arXiv]
Vitaly Feldman (IBM Research Almaden), Elena Grigorescu (Purdue University), Lev Reyzin (University of Illinois at Chicago), Santosh Vempala (Georgia Tech), and Ying Xiao (Georgia Tech)

Bottom-k and Priority Sampling, Set Similarity and Subset Sums with Minimal Independence
Mikkel Thorup (AT&T Labs-Research and University of Copenhagen)

Prior-Independent Mechanisms for Scheduling
Shuchi Chawla (University of Wisconsin at Madison), Jason D. Hartline (Northwestern University), David Malec (University of Wisconsin at Madison), and Balasubramanian Sivan (University of Wisconsin at Madison)

From information to exact communication [ECCC]
Mark Braverman (Princeton University), Ankit Garg (Princeton Unviersity), Denis Pankratov (University of Chicago), and Omri Weinstein (Princeton University)

Interactive Channel Capacity [ECCC]
Gillat Kol (Weizmann Institute of Science) and Ran Raz (Weizmann Institute of Science)

Fast Hamiltonicity checking via bases of perfect matchings [arXiv]
Marek Cygan (University of Warsaw), Stefan Kratsch (Max Planck Institute), and Jesper Nederlof (Utrecht University)

Witness Encryption and its Applications
Sanjam Garg (UC Los Angelos), Craig Gentry (IBM Watson Research Lab), Amit Sahai (UC Los Angelos), and Brent Waters (The University of Texas at Austin)

Non-Black-Box Simulation from One-Way Functions And Applications to Resettable Security [ePrint]
Kai-Min Chung (Cornell University), Rafael Pass (Cornell University), and Karn Seth (Cornell University)

A New Approach to Computing Maximum Flows using Electrical Flows
Satish Rao (UC Berkeley) and Nikhil Srivastava (Microsoft Research, India)

————————————————————————————-

by

Recreational Math Books – Part II

In my previous post (see here) I mentioned some interesting puzzle books. In today’s post I will mention different type of recreational math books i.e., biographical books. Here are my top three books in this category. They are must-read books for anybody even remotely interested in mathematics.

There are about three mathematics : (1)  Andrew Wiles, whose determination to solve Fermat’s Last Theorem inspires future generations and gives a strong message that patience and focus are two of the most important assets that every mathematician should posses. (2) Paul Erdos, whose love for mathematics is so deep and prolific and (3) Srinivasa Ramanujan, whose story is different from any other mathematician ever.

1) Fermat’s Enigma: The Epic Quest to Solve the World’s Greatest Mathematical Problem

This is one of the first “recreational” books I read. It starts with the history of Fermat’s last theorem (FLT), discusses the life style of early mathematicians and moves on to talk about Andrew Wiles’s 8 year long journey proving FLT. Watch this BBC documentary for a quick overview of Andrew Wiles’s story.

2) The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth

Paul Erdos is one of the greatest and most prolific mathematicians ever. The title of my blog is inspired by one of his famous sayings “My Brain is Open”. I don’t want to reveal any details of this book. You will enjoy this book more if you read it without knowing anything about Paul Erdos. I should warn you that there are some really tempting open problems in this book. When I first read this book (during my PhD days) I spent almost one full semester reading papers related to Twin Prime Conjecture and other number-theoretic problems. I also wrote a paper titled “A generalization of Erdos’s proof of Bertrand-Chebyshev’s theorem”. Watch this documentary “N is a number” for a quick overview of Paul Erdos’s story.

3) The Man Who Knew Infinity: A Life of the Genius Ramanujan

This is a very dense book. I bought it five years back and only recently finished reading it. This books covers lots of “topics” : south indian life-style, Hardy’s life, Ramanujan’s proofs and his flawed proofs, his journey to work with Hardy, his health struggles etc. It is definitely worth-reading to know the details of Ramanujan’s passion for mathematics.

—————————————————————————————————————————————

by

Recreational Math Books – Part I

Most of us encounter math puzzles during high-school. If you are really obsessed with puzzles, actively searching and solving them, you will very soon run out of puzzles !! One day you will simply realize that you are not encountering any new puzzles. No more new puzzles. Poof. They are all gone. You feel like screaming “Give me a new puzzle“. This happened to me around the end of my undergrad days. During this phase of searching for puzzles, I encountered Graceful Tree Conjecture and realized that there are lots of long-standing open “puzzles”. I don’t scream anymore. Well… sometimes I do scream when my proofs collapse. But that’s a different kind of screaming.

Sometimes, I do try to create new puzzles. Most of the puzzles I create are either very trivial to solve (or) very hard and related to long-standing conjectures. Often it takes lots of effort and ingenuity to create a puzzle with right level of difficulty.

In today’s post, I want to point you to some of the basic puzzle books that everybody should read. So, the next time you see a kid screaming “Give me a new puzzle“, simply point him/her to these books. Hopefully they will stop screaming for sometime. If they comeback to you soon, point them to Graceful Tree Conjecture  🙂

1) Mathematical Puzzles: A Connoisseur’s Collection by Peter Winkler

2) Mathematical Mind-Benders by Peter Winkler

3) The Art of Mathematics: Coffee Time in Memphis by Bela Bollobás

4) Combinatorial Problems and Exercises by Laszlo Lovasz

5) Algorithmic Puzzles by Anany Levitin and Maria Levitin

I will mention more recreational math books in part 2 of this blog post.

by

How to teach Algorithms ?

Algorithms

Algorithms are everywhere. They help us travel efficiently, retrieve information from huge data sets, secure money transactions, recommend movies, books, videos, predict stock market etc. It is very tough to think about a daily task that does not benefit from efficient algorithms. Often the algorithms behind most of these tasks are very simple, yet their impact is tremendous. When I say “simple”, they are simple to people who know them. Most common people consider algorithms too mathematical. They assume that it is beyond their capability to understand algorithms. What they do not realize is that algorithms are often simple extensions of our daily rational thinking process.

For example, almost everybody considers it stupid to buy an item for $24 and pay $6 shipping, if there is free shipping for orders of more than $25. If you add one more item of cost $1, you saved $5. Also, when we pack our bags for travel, most of us try to do it as “efficiently” as possible, trying to carry as many “valuable” things as possible while trying to avoid paying for extra luggage on airlines. We consider these rational choices. Algorithms are simply “step-by-step procedures to achieve these rational objectives“.

If you are an instructor (like me), teaching Algorithms, you might have noticed that most students (around 70%) are intimidated when they take a basic algorithms course. Most of them DO end up doing well in the course, but they consider the process painful. If they reflect on the course, most often they say “that course was a nightmare, I don’t remember what I learnt in that course”. They do not seem to have enjoyed the course. Probably they might remember 30% of the material. This is definitely not acceptable for such a fundamental course.

Often, when I comeback to my office after teaching, I say to myself  “I should have given them one more example, to help them get better intuition”. You can always do better job if you are given more time. Alas, we have time-bounded classes and almost infinite details to cover. We expect students to learn some concepts on their own and develop their own intuitions. We want to give “good” reading material. So, their understanding depends on how well these readings are written.

Today’s post is about “How to teach Algorithms ?” Here is one of my experiences, while I was teaching an undergrad algorithms course at GeorgiaTech. I was teaching dynamic programming. I gave several examples to make sure that they understand the paradigm. At the end of the class, almost 50% of class had questions, because this is the first time they saw dynamic programming. I told them to see me in my office hours. I quickly implemented a java applet to show how the matrix entries are filled by the algorithm, step by step. When I showed them this applet and a pseudo-code side-by-side (highlighting every current line of code being executed), almost all of the students understood the main idea behind dynamic programming. Some of them also said “it is easy”. I was glad and wanted to add more algorithms in my code.

The Kintali Language

The goal is to have a very simple to understand “executable pseudo-code” along with an animation framework that “understands” this language. So I started designing a new language and called it Kintali language, for lack of a better word 🙂 . I borrowed syntax from several pseudo-codes. It took me almost two years to implement all the necessary features keeping in mind a broad range of algorithms. I developed an interpreter to translate this language into an intermediate representation with callbacks to an animation library. This summer, I finally implemented the animation library and the front-end in Objective-C. The result is the Algorithms App for iPad, released on Sep 20, 2012. This is my attempt to teach as many algorithms as possible by intuitive visualization and friendly exercises.

Features

Current version has Sorting algorithms (Insertion Sort, Bubble Sort, Quick Sort and MergeSort). The main advantage of my framework will be demonstrated once I add graph algorithms. I will add some “adaptive” exercises and games too. For example, one of the games is to predict what is the next matrix entry that will be filled next by an algorithm.

Also, I have the necessary framework to visually demonstrate recursion (by showing the recursion tree), dynamic programming (by showing the status (filled or waiting to be filled) of matrix entries), divide and conquer (by splitting the data) etc. Since the framework is ready, adding new algorithms will not take much time.

Here is a screenshot of Quick Sort in action.

quicksort

Platforms

After I developed the interpreter, I was wondering what platforms to support first. I went ahead with iPad because I developed the interpreter in C. Objective-C is a superset of C. The Mac desktop version should be available in couple of weeks. In the long run I will implement the Android, Linux and Windows 8 versions too.

Goal

The big goal here is to “almost” replace an algorithms textbook. I added a button to access relevant wikipedia articles (within the app) describing the corresponding algorithms. With simple pseudo-code, intuitive animations, adaptive exercises and easy access to online articles, I think this goal is definitely achievable.

Questions

I have some quick questions to all the instructors and students of Algorithms.

  • What algorithms do you want to see soon i.e., what algorithms did you have most difficulty learning/teaching ?
  • What are some current methods you use to overcome the limitations of “static” textbooks ?
  • Any more ideas to make algorithms more fun and cool to learn/teach ?

I wanted to write this post after achieving at least 100 downloads. I assumed this will take a month. To my surprise, there were 100 downloads from 15 countries, in the first 40 hours. I guess I have to add new features faster than I planned.

TrueShelf and Algorithms App are new additions to my hobbies. The others being Painting, BoardGames and Biking. Man’s got to have some hobbies. 🙂

Follow Algorithms App on Facebook, Twitter and Google+.

Download Algorithms App for iPad

——————————————————————————————————————————————————

by

Open Problems from Lovasz and Plummer’s Matching Theory Book

I always have exactly one bed-time mathematical book to read (for an hour) before going to sleep. It helps me learn new concepts and hopefully stumble upon interesting open problems. Matching Theory by Laszlo Lovasz and Michael D. Plummer has been my bed-time book for the last six months. I bought this book 3 years back (during my PhD days) but never got a chance to read it. This book often disappears from Amazon’s stock. I guess they are printing it on-demand.

If you are interested in learning the algorithmic and combinatorial foundations of Matching Theory (with a historic perspective), then this book is a must read. Today’s post is about the open problems mentioned in Matching Theory book. If you know the status (or progress) of these problems, please leave a comment.

—————————————————————————-

1 . Consistent Labeling and Maximum Flow 

Conjecture (Fulkerson) : Any consistent labelling procedure results in a maximum flow in polynomial number of steps.

—————————————————————————-

2. Toughness and Hamiltonicity

The toughness of a graph G, t(G) is defined to be +\infty, if G = K_n and to be min(|S|/c(G-S)), if G \neq K_n. Here c(G-S) is the number of components of G-S.

Conjecture (Chvatal 1973) : There exists a positive real number t_0 such that for every graph G, t(G) \geq t_0 implies G is Hamiltonian.

—————————————————————————-

3. Perfect Matchings and Bipartite Graphs

Theorem : Let X be a set, X_1, \dots, X_t \subseteq X and suppose that |X_i| \leq r for i = 1, \dots, t. Let G be a bipartite graph such that

a) X \subseteq V(G),

b) G - X_i has a perfect matching , and

c) if any edge of G is deleted, property (b) fails to hold in the resulting graph.

Then, the number of vertices in G with degree \geq 3 is at most r^3 {t \choose 3}.

Conjecture : The conclusion of the above theorem holds for non-bipartite graphs as well.

—————————————————————————-

4. Number of Perfect Matchings

Conjecture (Schrijver and W.G.Valiant 1980) : Let \Phi(n,k) denote the minimum number of perfect matchings a k-regular bipartite graph on 2n points can have. Then, \lim_{n \to \infty} (\Phi(n,k))^{\frac{1}{n}} = \frac{(k-1)^{k-1}}{k^{k-2}}.

—————————————————————————-

5. Elementary Graphs

Conjecture : For k \geq 3 there exist constants c_1(k) > 1 and c_2(k) > 0 such that every k-regular elementary graph on 2n vertices, without forbidden edges , contains at least c_2(k){\cdot}c_1(k)^n perfect matchings. Furthermore c_1(k) \to \infty as k \to \infty.

—————————————————————————-

6. Number of colorations

Conjecture (Schrijver’83) : Let G be a k-regular bipartite graph on 2n vertices. Then the number of colorings of the edges of G with k given colors is at least (\frac{(k!)^2}{k^k})^n.

—————————————————————————-

7. The Strong Perfect Graph Conjecture (resolved)

Theorem : A graph is perfect if and only if it does not contain, as an induced subgraph, an odd hole or an odd antihole.

—————————————————————————-