Graph Theory

ICS 2010 Accepted Papers (with pdf files)

2009-11-02T09:04:00.013-05:00

ICS 2010 accepted paper list is here. List with abstracts is here. Following is a list with links to pdf files. Please leave a comment if I missed any pdf files. If you haven't uploaded your accepted paper on your homepages/arXiv/ECCC please do so. As and when I find new files on the internet, I will update them here.

Update : Slides of the talks are available online.

Are Stable Instances Easy? [pdf]
Yonatan Bilu and Nathan Linial
On the Construction of One-Way Functions from Average Case Hardness [ECCC]
Noam Livne
Leveraging Collusion in Combinatorial Auctions
Jing Chen, Silvio Micali, and Paul Valiant
Guaranteeing Perfect Revenue From Perfectly Informed Players [pdf]
Jing Chen, Avinatan Hassidim, and Silvio Micali
A New Look at Selfish Routing [pdf]
Christos Papadimitriou and Gregory Valiant
Symmetric LDPC codes and local testing
Tali Kaufman and Avi Wigderson
Derandomizing Algorithms on Product Distributions and Other Applications of Order-Based Extraction [pdf]
Ariel Gabizon and Avinatan Hassidim
Game Theory with Costly Computation [pdf]
Joseph Halpern and Rafael Pass
On the power of a unique quantum witness [pdf]
Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath and Shengyu Zhang
Interactive Proofs For Quantum Computations [arXiv]
Dorit Aharonov, Michael Ben-Or, Elad Eban
Adversarial Leakage in Games [pdf]
Noga Alon, Yuval Emek, Michal Feldman, and Moshe Tennenholtz
Bounds on the quantum satisfiability threshold [arXiv]
Sergey Bravyi and Cristopher Moore and Alexander Russell
Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions [arXiv]
Brendan Lucier
Space-Efficient Estimation of Robust Statistics [pdf]
Steve Chien; Katrina Ligett; Andrew McGregor
Hard instances for satsifiability and quasi-one-way functions [pdf]
Andrej Bogdanov and Kunal Talwar and Andrew Wan
Weight Distribution and List-Decoding Size of Reed-Muller Codes
Tali Kaufman and Shachar Lovett
Memory Consistency Conditions for Self-Assembly Programming [arXiv]
Aaron Sterling
Distribution-Specific Agnostic Boosting [arXiv]
Vitaly Feldman
Circuit Lower Bounds, Help Functions, and the Remote Point Problem [arXiv]
Vikraman Arvind and Srikanth Srinivasan
Playing games without observing payoffs
Michal Feldman, Adam Kalai and Moshe Tennenholtz
Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities [pdf]
Vijay V. Vazirani and Mihalis Yannakakis
Breaking and making quantum money [arXiv]
Scott Aaronson, Edward Farhi, David Gosset, Jonathan Kelner, Avinatan Hassidim, Andrew Lutomirski, and Peter Shor
Non-Malleable Codes [eprint]
Stefan Dziembowski and Krzysztof Pietrzak and Daniel Wichs
Bounding Rationality by Discounting Time [arXiv]
Lance Fortnow and Rahul Santhanam
A New Approach to Strongly Polynomial Linear Programming
Mihaly Barasz and Santosh Vempala
Robustness of the Learning with Errors Assumption [pdf]
Shafi Goldwasser, Yael Kalai, Chris Peikert, Vinod Vaikuntanathan
Local Algorithms for Finding Interesting Individuals in Large Networks [pdf]
Mickey Brautbar and Michael Kearns
Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature? [pdf]
Benny Applebaum and Yuval Ishai and Eyal Kushilevitz
A New Approximation Technique for Resource-Allocation Problems [pdf]
Barna Saha, Aravind Srinivasan
Analytical Tools for Natural Algorithms
Bernard Chazelle
Effectively Polynomial Simulations [pptx] [pdf]
Toniann Pitassi and Rahul Santhanam
Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior [pdf]
Maria-Florina Balcan and Avrim Blum and Yishay Mansour
Computational Complexity and Information Asymmetry in Financial Products [pdf]
Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge
Cryptographic Complexity Classes and Computational Complexity Assumptions [pdf]
Hemanta K. Maji (1), Manoj Prabhakaran (1), Mike Rosulek (2)
Cache Replacement Policies for Multicore Processors [pdf]
Avinatan Hassidim
Pan-Private Streaming Algorithms [pdf]
Cynthia Dwork Moni Naor Toni Pitassi Guy Rothblum Sergey Yekhanin
Reaching Consensus on Social Networks [pdf]
Elchanan Mossel and Grant Schoenebeck
Proof-Carrying Data and Hearsay from Signature Cards [pdf]
Alessandro Chiesa, Eran Tromer
Global Alignment of Molecular Sequences via Ancestral State Reconstruction [pdf]
Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sebastien Roch

SODA 2010 accepted papers

2009-09-04T13:28:00.002-04:00

SODA 2010 accepted papers list is here.
Here is a list with abstracts.

FOCS 2009 Accepted Papers (with pdf files)

2009-07-02T13:24:00.023-04:00

FOCS 2009 accepted paper list is here. List with abstracts is here. Following is a list with links to pdf files. Leave a comment if I missed any pdf files. If you haven't uploaded your accepted paper on your homepages please do so.

Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions [pdf]
Zeev Nutov.

Randomized Self-Assembly for Exact Shapes [pdf]
David Doty.

Symmetry and approximability of submodular maximization problems [pdf]
Jan Vondrak.

Fully Dynamic $(2 + \eps)$ Approximate All-Pairs Shortest Paths with $O(\log \log n)$ Query and Close to Linear Update Time
Aaron Bernstein.

Bounded Independence Fools Halfspaces [pdf]
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio and Emanuele Viola.

A Parallel Repetition Theorem for Any Interactive Argument [pdf]
Iftach Haitner.

Two-message quantum interactive proofs are in PSPACE [arXiv]
Rahul Jain, Sarvagya Upadhyay and John Watrous.

Extensions to the Method of Multiplicities, with applications to Kakeya sets and Mergers [pdf]
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf and Madhu Sudan.

Optimal Long Code Test with One Free Bit [ps]
Nikhil Bansal and Subhash Khot.

Combinatorial PCPs with efficient verifiers [pdf] [summary]
Or Meir.

A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP [arXiv]
Jeff Cheeger, Bruce Kleiner and Assaf Naor.

Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
Ben Reichardt. [arXiv]

Multiparty Communication Complexity and Threshold Circuit Complexity of AC^0
Dang-Trinh Huynh-Ngoc and Paul Beame. [pdf]

Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP [pdf]
Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi and Howard Karloff.

Delaunay Triangulations in O(sort(n)) and Other Transdichotomous and Hereditary Algorithms in Computational Geometry [pdf] [summary]
Kevin Buchin and Wolfgang Mulzer.

Polynomial hierarchy, Betti numbers and a real analogue of Toda's Theorem
Saugata Basu and Thierry Zell. [arXiv]

Learning Decision Trees From Random Examples: a Smoothed Analysis [pdf]
Adam Kalai, Shang-Hua Teng and Alex Samorodnitsky.

A Complete Characterization of Statistical Query Learning with Applications to Evolvability [pdf]
Vitaly Feldman.

Optimal quantum strong coin flipping [arXiv]
André Chailloux and Iordanis Kerenidis.

Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size [pdf]
Ankur Moitra.

Submodular Function Minimization under Covering Constraints [ps.gz]
Satoru Iwata and Kiyohito Nagano.

An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design [arXiv]
Julia Chuzhoy and Sanjeev Khanna.

Blackbox Polynomial Identity Testing for Depth 3 Circuits [ECCC]
Neeraj Kayal and Shubhangi Saraf.

The Complexity of Rationalizing Network Formation [pdf]
Shankar Kalyanaraman and Christopher Umans.

Exact And Approximate Pattern Matching In The Streaming Model
Ely Porat and Benny Porat.

A new probability using typical moments and concentration results [arXiv]
Ravindran Kannan.

Orthogonal Range Reporting in Three and Higher Dimensions [pdf]
Peyman Afshani, Lars Arge and Kasper Dalgaard Larsen.

Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks [arXiv]
Yossi Azar, Benjamin Birnbaum, L. Elisa Celis, Nikhil R. Devanur and Yuval Peres.

SDP Integrality Gaps with Local $\ell_1$-Embeddability [pdf]
Subhash Khot and Rishi Saket.

On the Power of Randomization in Algorithmic Mechanism Design [pdf]
Shahar Dobzinski and Shaddin Dughmi.

Constraint Satisfaction Problems of Bounded Width [pdf] [slides]
Libor Barto and Marcin Kozik.

On Allocating Goods to Maximize Fairness [arXiv]
Deeparnab Chakrabarty, Julia Chuzhoy and Sanjeev Khanna.

Regularity Lemmas and Combinatorial Algorithms [summary] [pdf]
Nikhil Bansal and Ryan Williams.

One bit encryption is complete
Steven Myers and abhi shelat.

Composition of low-error 2-query PCPs using decodable PCPs [ECCC]
Irit Dinur and Prahladh Harsha.

Smoothed Analysis of Multiobjective Optimization [pdf]
Heiko Roeglin and Shang-Hua Teng.

k-Means has Polynomial Smoothed Complexity [arXiv]
David Arthur, Bodo Manthey and Heiko Roeglin.

Reducibility Among Fractional Stability Problems [pdf] [ECCC] [arXiv]
Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng.

Online Stochastic Matching: Beating 1-1/e [pdf]
Jon Feldman, Aranyak Mehta, Vahab Mirrokni and S. Muthukrishnan.

The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems [arXiv]
Sandy Irani and Daniel Gottesman.

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities [arXiv]
Xi Chen, Decheng Dai, Ye Du and Shang-Hua Teng.

Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy [pdf]
Yi Deng, Vipul Goyal and Amit Sahai.

Space-Efficient Framework for Top-k String Retrieval Problems [pdf]
Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter.

(Meta) Kernelization [pdf]
Hans Bodlaender, Fedor Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh and Dimitrios Thilikos.

Choice-memory tradeoff in allocations [arXiv]
Noga Alon, Ori Gurel-Gurevich and Eyal Lubetzky.

The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
Eyal Kushilevitz and Enav Weinreb.

Convergence to Equilibrium in Local Interaction Games [pdf]
Andrea Montanari and Amin Saberi.

Instance-Optimal Geometric Algorithms [ps]
Peyman Afshani, Jeremy Barbay and Timothy M. Chan.

Planarity allowing few error vertices in linear time [pdf]
Ken-ichi Kawarabayashi.

Constructing Small-Bias Sets from Algebraic-Geometric Codes [pdf]
Avraham Ben-Aroya and Amnon Ta-Shma.

Oblivious Routing for the L_p-norm [pdf]
Matthias Englert and Harald Räcke.

The Intersection of Two Halfspaces Has High Threshold Degree [ECCC] [arXiv]
Alexander Sherstov.

Distance Oracles for Sparse Graphs [html] [pdf]
Christian Sommer, Elad Verbin and Wei Yu.

Universal Blind Quantum Computation [arXiv]
Anne Broadbent, Joseph Fitzsimons and Elham Kashefi.

Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization [arXiv]
Tanmoy Chakraborty, Zhiyi Huang and Sanjeev Khanna.

Decomposing Coverings and the Planar Sensor Cover Problem [pdf]
Matt Gibson and Kasturi Varadarajan.

Extracting Correlations
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.

The Data Stream Space Complexity of Cascaded Norms [pdf]
T.S. Jayram and David Woodruff.

Faster generation of random spanning trees [pdf]
Jonathan Kelner and Aleksander Madry.

Integrality gaps for Strong SDP Relaxations of Unique Games [pdf]
Prasad Raghavendra and David Steurer.

How to Round Any CSP [pdf]
Prasad Raghavendra and David Steurer.

KKL, Kruskal-Katona, and monotone nets [pdf]
Ryan O'Donnell and Karl Wimmer.

Higher eigenvalues of graphs [pdf]
Jonathan Kelner, James Lee, Gregory Price and Shanghua Teng.

Efficient sketches for Earth-Mover Distance, with applications [pdf]
Alexandr Andoni, Khanh Do Ba, Piotr Indyk and David Woodruff.

Agnostic Learning of Monomials by Halfspaces is Hard [pdf]
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra and Yi Wu.

An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk [arXiv]
Ashish Goel and Ian Post.

Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions [pdf]
Gagan Goel, Chinmay Karande, Pushkar Tripathi and Lei Wang.

Local Graph Partitions for Approximation and Testing [html]
Avinatan Hassidim, Jonathan Kelner, Huy Nguyen and Krzysztof Onak.

Linear systems over composite moduli [pdf]
Arkadev Chattopadhyay and Avi Wigderson.

Models for the compressible Web [pdf]
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi and Prabhakar Raghavan.

Breaking the Multicommodity Flow Barrier for O(sqrt(log n))-approximations to Sparsest Cut [arXiv]
Jonah Sherman.

A Probabilistic Inequality with Applications to Threshold Direct Product Theorems [ECCC]
Falk Unger.

2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness [summary] [pdf]
Yael Tauman Kalai, Xin Li and Anup Rao.

---------------------------------------------------------------------------------------

FOCS notification

2009-06-25T13:24:00.005-04:00

I just received an email that the following paper is accepted to FOCS 2009. You can find a pdf of its full version here.

Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng
Reducibility Among Fractional Stability Problems

Since we had electronic proceedings at STOC'09, I am hoping that FOCS'09 continues this tradition. If so, it makes sense to remove the upper bound on the number of pages for the camera-ready version. I cannot imagine converting these 50 page results into a 10 page paper.

Barriers Everywhere

2009-06-22T20:50:00.003-04:00

Two upcoming workshops :

It would be great if the talks at (1) are recorded. Video talks are great resource for the community, since not everybody can afford (money/time) to attend all these great workshops. Talks at Intractability Center are are always recorded, which is great !!

PPAD-complete problems on wikipedia

2009-06-17T15:40:00.002-04:00

As requested by many of the readers of my blog, I added a wikipedia entry for PPAD-complete problems. It is called List of PPAD-complete problems. I added only the contents. I will try to add more content when I get time. Please feel free to edit and make it as informative (with definitions of problems, references, open problems etc) as possible.

Hamilton Paths Puzzle

2009-06-17T14:33:00.003-04:00

Prove the following :

Let G be an undirected graph and G' its complement. Let h(G) be the number of Hamilton paths of G, then h(G) + h(G') is even.

Update : Assume that the number of vertices of G is at least 5.

2009 Fulkerson Prize

2009-05-26T12:07:00.005-04:00

It seems 2009 Fulkerson Prize is awarded to the following paper.

Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas : The Strong Perfect Graph Theorem, Annals of Mathematics Vol. 164 (2006), 51 -- 229 [pdf]

This is the fourth time for Paul Seymour, third time for Neil Robertson and second time for Robin Thomas. The list of past winners is here and here.

My Other Blog

2009-05-23T18:38:00.003-04:00

I started a new blog (exclusively for technical posts) using wordpress. I like latex-editing features of wordpress much better than blogger. I will continue to use this blog for quick theory-related announcements, puzzles and other fun stuff.

Valiant's 60th Birthday Celebration

2009-05-22T14:10:00.002-04:00

The program for Valiant's birthday celebration is listed on STOC 2009 website. Next week (May30th to June 5th) is an exciting week. Valian't Birthday celebration, followed by STOC 2009, followed by complexity workshop. I am glad that I will be attending all of them.

Godel Prize 2009

2009-05-20T22:30:00.002-04:00

Via My Biased Coin....

The 2009 Godel Prize is awarded to Omer Reingold, Salil Vadhan and Avi Wigderson for their work on Zig-zag product of graphs. Here are the related papers :

STOC 2009 and Complexity Workshop at Princeton

2009-05-15T11:04:00.004-04:00

I am attending STOC 2009 and this workshop titled "Complexity and Cryptography: Status of Impagliazzo's Worlds" at Princeton. It is scheduled right after STOC 2009. I am planning to drive to STOC (Maryland) and then to princeton. Looking forward to one week of excellent theory talks !!

Anybody in and around atlanta (or) on the way to maryland, let me know if you want to join the drive. I have two more vacancies in my car.

Synchronizing Research Documents

2009-05-08T13:58:00.003-04:00

I have been using dropbox for the last two months and am very happy with it. Dropbox is an online service to synchronize your files across your computers. I use it to synchronize my research documents. Here is a quick list of features I liked :

Simple interface. Adds a folder in your file explorer (windows/mac). This folder can be used like any folder on your computer.
Automatic synchronization. Modify files without worrying about synching them. Drag and drop to add new files.
Saves the files locally and on the dropbox server. You can also access your files online from any computer using web-browser.
Uses CVS like protocol (sending only the diff-file to the server). You can recover older versions of your files.
You can create shared folders with other friends. This helps a lot when you are collaborating. You can share the files, without emailing them back and forth.
You can essentially use dropbox as a CVS server.

For more information visit Dropbox Wiki.

A Compendium of PPAD-complete problems

2009-05-03T18:40:00.003-04:00

Motivated by my recent paper (joint work with Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng) and a suggestion of Noam Nisan, I created a compendium of PPAD-complete problems. Please let me know if you see any additions/corrections.

I Just Do Theory

2009-04-20T08:56:00.003-04:00

Via Aaronson's blog. This is song called 'I Just Do Theory' is aaaaaawesome.
Here is an mp3 file and pdf file of lyrics.
My best line in the lyrics is 'Playing games in PPAD' because that's what I am doing now.

I guess the next step is to make a video :)

Complexity 2009 accepted papers

2009-04-15T09:27:00.003-04:00

Complexity 2009 accepted papers list is out. Almost every paper sounds interesting to me.

ICALP 2009 accepted papers

2009-04-07T23:53:00.003-04:00

ICALP 2009 accepted papers list is out. Matching my research interests, the following papers sound interesting to me :

Adam Klivans, Phil Long and Rocco Servedio. Learning Halfspaces with Malicious Noise
Neeraj Kayal and Timur Nezhmetdinov. Factoring groups efficiently
Barna Saha and Samir Khuller. On Finding Dense Subgraphs
Harry Buhrman, Lance Fortnow and Rahul Santhanam. Unconditional Lower Bounds against Advice
Michael Ummels and Dominik Wojtczak. The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games

I wish ICALP and other theory conferences follow the recent trend of FOCS/STOC/SODA of uploading the abstracts of the accepted papers.

Free Online Video Lectures

2009-03-24T19:09:00.003-04:00

From my bookmarks : here are some great websites with video lectures :

Research Channel : Awesome site with lots of theory talks. Most of the theory talks are either from University of Washington (or) Microsoft Research. I used it extensively during my first year of PhD.

Video Lectures : Another awesome site with great theory talks.

MIT's Open Courseware : MIT has a decent collection of free course material. Some include video lectures. Years back, I learnt linear algebra from Strang's video lectures . I still use them for quick reference.

Stanford's Engineering Everywhere is upcoming. It has very few courses compared to MIT.

Last but not the least, Academic Earth covers many areas with good quality video lectures.

Did I miss any good sites ? Please leave a comment if you know other websites with free video lectures.

Dick Lipton's and Noam Nisan's Blogs

2009-03-20T15:41:00.003-04:00

There are two new theory blogs.....

Dick Lipton's Gödel’s Lost Letter and P=NP : This is an awesome blog. During my first semester at GeorgiaTech I took Dick's course on 'Open Problems in CS theory'. What an excellent course that was !! In every class, Dick proposed at least three open problems along with possible ways to attack them and required references. Since, it was my first semester at Gatech, some of these problems intimidated me. Nevertheless, I maintained a special notebook and scribbled each and every problem and references he mentioned, hoping to revisit them later. I am gald that all his open problems are being documented in his blog.

Noam Nisan's Algorithmic game theory is very fresh. Just launcheded yesterday.

Complexity of Ken Ken Game

2009-03-13T15:52:00.002-04:00

I came across this puzzle named Ken Ken. It is Sudoku-type puzzle with arithmetic constraints. Here is a complexity question :

Is solving n x n Ken Ken puzzle NP-complete ?

NP-completeness results are known for similar games like Sudoku. Here is a paper on mathematics of Septoku. Here is David Eppstein's list of games with complexity results.

2008 ACM Turing Award

2009-03-10T13:31:00.003-04:00

ACM has named Barbara Liskov as the winner of the 2008 Turing Award...... "for contributions to practical and theoretical foundations of programming language and system design, especially related to data abstraction, fault tolerance, and distributed computing."

More details in the press release.
Interview with Barbara Liskov.
Liskov substitution principle.

Sloan Fellows 2009

2009-02-17T14:57:00.002-05:00

Sloan Research Fellows for the year 2009 are announced. The list can be found here. For a list of theory Sloan fellows (and related comments) follow this post on complexity blog.

Free Algebraic Curves Book

2009-02-16T01:44:00.003-05:00

William Fulton's Algebraic Curves book is available free online. What distinguishes it from other books is the excellent set of exercise problems.

SoCG 2009 accepted papers

2009-02-14T04:46:00.002-05:00

SoCG 2009 accepted papers list is here.

STOC 2009 accepted papers

2009-02-07T03:57:00.001-05:00

STOC 2009 accepted papers list is here.
Here is a list with the abstracts

Linial-Nisan Conjecture

2009-01-23T09:09:00.007-05:00

As most of you already know, Linial-Nisan Conjecture is settled by Mark Braverman. This settles a major open problem. Read the following blog posts for more details :

Braverman's paper is on his homepage.

Pure Mathematics

2009-01-21T08:55:00.005-05:00

This comic strip from Abstruse Goose is simply aaawesome !! Click the image to enlarge.

Long Live Pure Mathematics.....

Finding a Second Hamilton Circuit

2009-01-20T05:01:00.005-05:00

Given an undirected graph does it have a Hamilton circuit ? It is well-known that this is an NP-complete problem. Consider the following problem :

ANOTHER HAMILTON CIRCUIT : Given a Hamilton circuit in a graph find another hamilton circuit.

It is easy to see that ANOTHER HAMILTON CIRCUIT is FNP-complete. What if we are given a Hamilton graph which is guaranteed to have a second Hamilton circuit. Following is a simple exercise :

Exercise : Prove that if a cubic graph has a hamilton circuit then it must have a second one

The above exercise is called Smith's Theorem. Now consider the following computational poblem :

SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit.

Since the second hamilton circuit is guaranteed to exist, SMITH belongs to complexity class TFNP. Note that TFNP is a semantic class. In a beautiful paper [1] Papadimitriou defined several syntactic classes (e.g., PPA, PPAD, PPP) in TFNP. Papadimitriou proved that SMITH is in the complexity class PPA [1]. Here is an open problem mentioned in [1].

Open Problem : Find a polynomial time algorithm for SMITH (or) Prove that SMITH is PPA-complete.

[1] Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994)

Train Probability Puzzle

2009-01-12T09:24:00.003-05:00

The probability of observing a train in 30 minutes on a track is 665/729. What is the probability of observing a train in 5 minutes ?

Hint : Shoot for an elegant solution.

Troyis Game

2009-01-07T03:58:00.005-05:00

I came across this game called Troyis. Being a theoretician, whenever I come across a new game, the first question that comes to my mind is "What is its complexity ?". Here is the decision version of Troyis :

TROYIS : Given an instance of Troyis, can you paint all the white cells in <= k clicks ?

Here is a puzzle : Prove (or disprove) that TROYIS is NP-complete.

Polynomials difference puzzle

2008-12-30T01:47:00.002-05:00

Here is a cute puzzle about difference of polynomials.

Caterpillar graphs are graceful

2008-12-15T02:05:00.002-05:00

Let T(V,E) be a tree, with |V|=n. A graceful labeling of T is an assignment of labels (from 1 to n) to the vertices such that if the edges are labeled with the absolute difference of their incident vertices, then each edge receives a unique label (i.e., each of the n-1 edges receive labels fron 1 to n-1). It is easy to see that stars and paths are graceful.

A caterpillar graph is a tree such that if all leaves and their incident edges are removed, the remainder of the graph forms a path. Here's a cute problem :

Prove that all caterpillar graphs are graceful

Hint : Given a graceful labeling find another labeling with a special property and apply induction.

Have fun solving this. I almost gave you the solution.

Legendre's Conjecture

2008-11-24T00:37:00.007-05:00

Bertrand's postulate states that for every positive integer n, there is always at least one prime p such that n < p < 2n This was proved by Chebyshev in 1850, Ramanujan in 1919 and Erdos in 1932.

Legendre's conjecture states that there is a prime number between n² and (n+1)² for every positive integer n. It is one of the four Landau's problems, considered as four basic problems about prime numbers. The other three problems are (i) Goldbach's conjecture : can every even integer n > 2 be written as the sum of two primes ? (ii) Twin prime conjecture : are there infinitely many primes p such that p+2 is prime ? (iii) are there infinitely many primes p such that p-1 is a perfect square ? All these problems are open till date.

How about the following generalization of the Bertrand's postulate :

Does there exist a prime number p, such that kn < p < (k+1)n for all integer n>1 and k <= n ?

A positive answer for k = n would prove Legendre's conjecture.
I proved the following theorem :

Theorem : For any integer 1 < k < n, there exists a number N(k) such that for all n >= N(k), there is at least one prime between kn and (k+1)n.

My proof is based on Erdos's proof of Bertrand-Chebyshev theorem and uses elementary combinatorial techniques without appealing to the prime number theorem. You can find a preprint on my homepage.

My Favorite Math Movies

2008-11-20T12:21:00.010-05:00

Here are my top five math movies, along with my favorite quotes. I will not talk about the storylines, because I don't want to spoil the fun.

N is a number : I was sad that I did not see Paul Erdös in person, until I saw this documentary. This is a documentary about Paul Erdös, the wandering mathematician, the man who loved only numbers. Watch this if you want to see him walk, talk, crack math jokes and inspire people around him. You can also see other famous mathematicans collaborating with him.

Euler, when he died, he simply collapsed and said "I am finished". An when I told this story, somebody callously remarked : "Another conjecture of Euler's was proven".
What is the purpose of life ? "Prove and conjecture and keep the SF's score low".

Pi : I should warn you that this is a disturbing move. Here are couple of quotes.

Restate my assumptions: One, Mathematics is the language of nature. Two, Everything around us can be represented and understood through numbers. Three: If you graph the numbers of any system, patterns emerge. Therefore, there are patterns everywhere in nature. Evidence: The cycling of disease epidemics;the wax and wane of caribou populations; sun spot cycles; the rise and fall of the Nile.
You want to find the number 216 in the world, you will be able to find it everywhere. 216 steps from a mere street corner to your front door. 216 seconds you spend riding on the elevator. When your mind becomes obsessed with anything, you will filter everything else out and find that thing everywhere.

Proof : This is a perfect math movie with top-notch performances from Gwyneth Paltrow and Anthony Hopkins, an awesome screenplay and a satisfying ending. The following conversation about Hardy-Ramanujan number is aptly placed in the movie.

Robert: Catherine, if every day you lost were a year, it would be a very interesting freaking number.

Catherine: 33 and a quarter years is not interesting.

Robert: Stop it, you know exactly what I mean.

Catherine: 1729 weeks.

Robert: 1729, great number. The smallest number expressed ...

Robert and Catherine: ... as the sum of two cubes in two different ways.

Robert: 12³ + 1³ = 1729.

Catherine: And 10³ + 9³. Yes, we've got it, thank you.

Robert: You see? Even your depression is mathematical.

A Beautiful Mind : Well, everybody knows about this oscar-winning movie.

Sometimes, our expectations are betrayed by the numbers.
Good morning, eager young minds.
Find a truly original idea. It is the only way I will ever distinguish myself. It is the only way I will ever matter.
[Sol] John, you should go easy. There are other things besides work. [Nash] : What are they ?

Good Will Hunting : In my previous post I mentioned an elementary graph theory problem from this movie. Also, there is a scene in which the characters talk about a math problem and joining two vertices of a tree. Are they talking about 1-trees ? If you don't know what a 1-tree is, read Held-Karp relaxation of Traveling Saleman Problem. The best scenes of the movie are the conversations between Will and Sean.

You really hypnotised me, you know.
I'm pumped! Let the healing begin!
I can't learn anything from you, I can't read in some freaking book. Unless you want to talk about you, who you are.
[Will] You just cash in your chips and you walk away ? [Sean] Hey, at least I played a hand.

Btw, Pi, Proof and A Beautiful Mind have excellent soundtracks too. I would like to see more movies of this kind. If you know of any good math movies, leave a comment.

The Good Will Hunting Problem

2008-11-09T18:44:00.000-05:00

Here is a problem from the movie Good Will Hunting, shown in the screenshot below.

For the the graph G(V,E) shown above, find the following :

The adjacency matrix A :

The matrix giving the number of 3 step walks in G : [A^k]_ij is the number of paths of length k from i to j. So, the answer is A³.

The generating function for walks from point i to j : The generating function is as follows. Here are more examples of generating functions.

The generating function for walks from points 1 to 3 : Simplify the above formula using cramer's rule for i=1 and j=3.

How are mathematics texts written ?

2008-11-04T13:37:00.000-05:00

If you are wondering how mathematics texts are written, check this out. Very funny ;)

Click the above picture to enlarge.

List Coloring

2008-11-02T19:12:00.000-05:00

I have been reading some papers on list-coloring of planar graphs. Here's a quick overview of this topic.

A proper coloring of a graph is an assignment of colors to vertices of a graph such that no two adjacent vertices receive the same color. A graph is k-colorable if it can be properly colored with k colors. For example, the famous Four Color Theorem states that "Evey planar graph is 4-colorable". This is tight, since a complete graph on four vertices is 4-colorable but not 3-colorable. Deciding if a graph is 3-colorable is NP-hard. It is natural to ask which planar graphs are 3-colorable. Grotzsch's Theorem states that "Every triangle-tree planar graph is 3-colorable".

Given a graph and given a set L(v) of colors for each vertex v, a list coloring is a proper coloring such that every vertex v is assigned a color from the list L(v). A graph is k-list-colorable (or k-choosable) if it has a proper list coloring no matter how one assigns a list of k colors to each vertex.

If a graph is k-choosable then it is k-colorable (set each L(v) = {1,...k}). But the converse is not true. Following is a bipartite graph (2-colorable) that is not 2-choosable (corresponding lists are shown).

A graph is k-degenerate if each non-empty subgraph contains a vertex of degree at most k. The following fact is easy to prove by induction :

A k-degenerate graph is (k+1)-choosable

Are there k-degenerate graphs that are k-choosable ? Following are some known results and open problems :

Every bipartite planar graph is 3-choosable [Alon & Tarsi '92]. It is easy to prove that every bipartite planar graph is 3-degenerate.
Every planar is 5-choosable [Thomassen '94]. Note that every planar graph is 5-degenerate. There are planar graphs which are not 4-choosable [Voigt '93].
Every planar graph of girth at least 5 is 3-choosable. This implies grotzsch's theorem in a very cute way [Thomassen '03]. There are planar graphs of girth 4 which are not 3-choosable [Voigt '95].

Conjecture : Every 3-colorable planar graph is 4-choosable.

Note : A recent paper [DKT '08], presents a very short proof of Grotzsch's theorem and a linear-time algorithm for 3-coloring such graphs.

References :

[Alon & Tarsi '92] N. Alon, M. Tarsi: Colorings and orientations of graphs. Combinatorica 12(2): 125-134 (1992)
[Thomassen '94] C. Thomassen: Every Planar Graph Is 5-Choosable. J. Comb. Theory, Ser. B 62(1): 180-181 (1994)
[Voigt '93] M. Voigt: List colourings of planar graphs. Discrete Mathematics 120(1-3): 215-219 (1993)
[Thomassen '03] C. Thomassen: A short list color proof of Grötzsch's theorem. J. Comb. Theory, Ser. B 88(1): 189-192 (2003)
[Voigt '95] M. Voigt : A not 3-choosable planar graph without 3-cycles. Discrete Mathematics 146(1-3): 325-328 (1995)
[DKT '08] Z. Dvorak and K. Kawarabayashi and R. Thomas : Three-coloring triangle-free planar graphs in linear time. To appear in SODA 09.

P vs NP on arxiv

2008-10-29T13:21:00.000-04:00

There is a paper on Arxiv claiming that P != NP.
Here are the other papers on DBLP from this author.

Friendly Numbers

2008-10-28T17:18:00.000-04:00

Pythagoras said "220 and 284 are friendly numbers" !! These numbers have a special property : Each is equal to the sum of the other's proper divisors. Proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110 (they sum to 284). Proper divisors of 284 are 1, 2, 4, 71 and 142 (they sum to 220). More example include (1184, 1210), (17296, 18416). It is not known whether there are infinitely many friendly numbers. Twin primes are a pair of consecutive odd numbers both of which are prime.

Theorem : There are infinitely many friendly numbers. (proof)

Conjecture : There are infinitely many twin primes.

SODA 2009 accepted papers

2008-09-09T19:32:00.000-04:00

SODA 2009 accepted papers list is here.
Here is a list with the abstracts.

ISAAC 2008 accepted papers

2008-08-26T14:47:00.000-04:00

ISAAC 2008 accepted papers list is here.

IMO 2008 Results

2008-07-25T17:17:00.000-04:00

49th International Mathematical Olympiad results are announced. Three participants secured full marks, as opposed to 2007, when nobody scored 42.

Common Puzzles

2008-07-23T16:03:00.000-04:00

Most of my friends are geeks. So when we get together on a friday night (or) driving to a conference, we don't talk about politics, movies or celebrities. Instead we throw math puzzles at each other. Here are some of the common puzzles I ran into....

The Banana-eating Camel : You have 3,000 bananas that must be transported across a desert that is 1,000 kilometers wide. You have a camel that has a 1,000 banana capacity. However, the camel must eat one banana for each kilometer that it walks. What is the largest number of bananas that can be transported across the desert?

12 Balls : There are 12 balls. They all look alike but one of them is faulty; it weights differently. It is not known, if this ball is heavier or lighter than the other balls. How to find the faulty ball by three weighs on a simple balance ?

Linked Lists : You are given a pointer to the head of a singly linked list that might (or might not) have a loop somewhere (i.e., an element pointing back to an element). The length of the list is finite, but unknown. Devise an algorithm that detects if there is a loop. You must use only a constant amount of memory space and not destroy the list.

Two Integers : I'm thinking of two integer numbers, each if them is more than 1 and their sum is less than 100. I tell my friend A the sum of these two numbers, and another friend B, product of these two numbers. Then such a dialog took place:
B: I can't determine what are these numbers.
A: Ah, i knew you wouldn't be able to do this.
B: Oh, then i know what they are!
A: Oh, then i know them too!

Can you determine the numbers?

Stick triangle : A stick is broken at random into three pieces. What is the probability that the pieces can form a triangle?

These are the easiest ones (the appetizers). Have fun solving them. I will add more difficult puzzles in future posts...

The Dark Knight and Game Theory

2008-07-21T00:30:00.000-04:00

I watch very few movies, because I don't like to be disappointed. Most of the time I come out of the theater with some sort of disappointment. This movie is a waste of time.... Is the director stupid.... Is that scene really necessary to the script... are my usual reactions.

Once in a while, comes a perfect movie that makes me very happy. So happy, that I watch it 2-3 times during the same weekend. I am very glad to add 'The Dark Knight' to my list (which has less than twenty movies) of perfect movies. This is because of its strong characters, focused direction, flawless script and dedicated performances.

'The Dark Knight' is not a run-of-the-mill superhero movie, where one guy with super-human powers, fights the evil and everybody else waits for him to rescue them and clean up the mess, because he is the ONE. 'The Dark Knight' is all about a GAME. The game between good and evil. The game we all play in our minds daily, before making any choice.

****** SPOILER ALERT BEGIN ******

Lets look at the following game, based on the famous Prisoner's dilemma :

There are two players A and B in two different rooms located far enough. A is given a detonator that would blow B's room and kill B. B is given a detonator that would blow A's room and kill A. Both A and B were told that they will be killed in 15 minutes, unless they use the detonator and kill the other player, in which case the survivor is let go !!

What would you do, if you are A ?
I know !! The answer is obvious. Kill B.
Why ?
Come on !! It is the rational choice.
Evolution is based on survival of the fittest.
Greed is a virtue necessary for our existence. Blah blah blah...

You don't know who B is ? B might not want to kill you.
Well.... I don't want to take any chances.
I don't think B is a stupid. I don't want to be a stupid.
I will kill B and survive and win.

****** SPOILER ALERT END ******

Often there is a thin line between good and evil. Sometimes we cross the line and justify it as rational choice.

Do you evaluate the costs of sticking with your principles, before crossing the line ?
Do you want to do business with your principles ?
Can you stick to your principles at any cost ?

The movie raises questions on these moral dilemmas.

Often we are twisted by our past to make extreme choices. Some of us try to compensate by making evil choices. Some of us are afraid to show our good side and some afraid to show the evil side.

How many times did we hear people say "If you are nice, people will take advantage of you. You have to be SMART".

Oh yeah !! That makes a lot of sense. Let's all be smart.

A Proof of the Riemann hypothesis !!

2008-07-02T17:27:00.000-04:00

The following paper on arXiv claims a proof of Riemann hypothesis.

A Proof of the Riemann hypothesis, by Xian-Jin Li

In one of my previous posts, I pointed to a paper claiming Riemann hypothesis to be false.

FOCS 2008 accepted list

2008-06-24T13:26:00.001-04:00

FOCS 2008 accepted papers list is here.

Firefox download day

2008-06-17T15:02:00.000-04:00

I am an ardent fan of open source software. In the recent past, I made some (code, bug-fix and testing) contributions to open source projects like gcc, bison and mySQL. There is no doubt that some of the open-source softwares made a huge impact, much more than commercial softwares. Some of the great examples are Linux, gcc, gdb, python, eclipse and of course the one and only firefox. Firefox has redefined the internet browsing experience.

Mozilla is attempting to set a Guinness World Record for most software downloads in a 24 hours. Today is the download day. I guess this would be the geekiest world record ever. Currently, there is no world record for software downloads.

Firefox 3 promises many exciting new features. Here is a video tour. Here is PC magazine's review of firefox 3. You can download firefox 3 here.

More Links :

Screencast overview of firefox 3.
Top 10 firefox 3 features.
Field Guide to Firefox 3.
Power User's Guide to Firefox 3.
Set Firefox 3 to Launch Gmail for mailto Links

SODA 2009 Call for papers

2008-06-10T15:03:00.000-04:00

SODA 2009 submission server is up. There are five new changes about SODA 2009. I am very happy to see these new changes and here's why :

Pre-submission of abstracts one week before the deadline

encourages authors to be more systematic. Helps programming committee to organize submissions and plan in a better way.

The submission must include a full proof of the results

I always wanted to see this rule. Makes reviewers' life easier.

Submitting authors are encouraged to post their submission on their website.

See my guest post here. I hope authors do make their papers publicly available.

A list of accepted papers, along with the short abstracts, will be posted on the internet.

Wow !! This helps researchers to quickly know what problems are being solved in the community and request authors for full papers (if they have not posted online).

Submission uses Easychair

I remember submitting a paper to SODA 2008 through some complicated e-mailing process. That was not an elegant process for a top conference like SODA !! I sent e-mails to couple of PC member requesting them to use easy chair in SODA 2009. I am glad they are doing it now !!

Happy to see these changes in SODA. Way to go !!

ESA 2008

2008-05-27T10:47:00.000-04:00

ESA 2008 accepted papers list is here.

List Coloring of Planar Graphs

2008-04-24T19:25:00.000-04:00

I have been reading some papers on list-coloring of planar graphs. Here's a quick overview of this topic.

A proper coloring of a graph is an assignment of colors to vertices of a graph such that no two adjacent vertices receive the same color. A graph is k-colorable if it can be properly colored with k colors. For example, the famous Four Color Theorem (4CT) states that "Evey planar graph is 4-colorable". This is tight, since K4 is 4-colorable but not 3-colorable. Deciding if a graph is 3-colorable is NP-hard. It is natural to ask which planar graphs are 3-colorable. Grotzsch's Theorem states that "Every triangle-tree planar graph is 3-colorable".

Given a graph and given a set L(v) of colors for each vertex v, a list coloring is a proper coloring such that every vertex v is assigned a color from the list L(v). A graph is k-list-colorable (or k-choosable) if it has a proper list coloring no matter how one assigns a list of k colors to each vertex.

If a graph is k-choosable then it is k-colorable (set each L(v) = {1,...k}). But the converse is not true. Following is a bipartite graph (2-colorable) that is not 2-choosable (corresponding lists are shown).

A graph is k-degenerate if each non-empty subgraph contains a vertex of degree at most k. The following fact is easy to prove by induction :

A k-degenerate graph is (k+1)-choosable

Are there k-degenerate graphs that are k-choosable ? Following are some known results and open problems :

Every bipartite planar graph is 3-choosable [Alon & Tarsi]. It is easy to prove that every bipartite planar graph is 3-degenerate.
Every planar is 5-choosable [Thomassen'94]. Note that every planar graph is 5-degenerate. There are planar graphs which are not 4-choosable [Voigt'93].
Every planar graph of girth at least 5 is 3-choosable. This implies grotzsch's theorem in a very cute way [Thomassen'03]. There are planar graphs of girth 4 which are not 3-choosable [Voigt'95].

Conjecture : Every 3-colorable planar graph is 4-choosable.

Note : A recent paper [DKT'08], presents a very short proof of Grotzsch's theorem and a linear-time algorithm for 3-coloring such graphs.

References :

[Alon & Tarsi'92] N. Alon, M. Tarsi: Colorings and orientations of graphs. Combinatorica 12(2): 125-134 (1992)
[Thomassen'94] C. Thomassen: Every Planar Graph Is 5-Choosable. J. Comb. Theory, Ser. B 62(1): 180-181 (1994)
[Voigt'93] M. Voigt: List colourings of planar graphs. Discrete Mathematics 120(1-3): 215-219 (1993)
[Thomassen'03] C. Thomassen: A short list color proof of Grötzsch's theorem. J. Comb. Theory, Ser. B 88(1): 189-192 (2003)
[Voigt'95] M. Voigt : A not 3-choosable planar graph without 3-cycles. Discrete Mathematics 146(1-3): 325-328 (1995)
[DKT'08] Z. Dvorak and K. Kawarabayashi and R. Thomas : Three-coloring triangle-free planar graphs in linear time. To appear in SODA 09.

Testing triangle-freeness

2008-04-20T18:43:00.000-04:00

Given an undirected graph G(V,E), how fast can we detect if G is triangle-free ? Cubic time is obvious. Let A be the adjacency matrix of G. We can detect triangle-freeness of G in the same complexity as multiplying two boolean matrices (AxA) (duh !!). This simple algorithm is the best known !! In other words, following is the open problem :

Is testing triangle-freeness as difficult as the Boolean multiplication of two |V| x |V | matrices?

A recent paper [1] addressess this problem partially. In a related note, the complexity of all pairs shortest paths (APSP) is still unresolved. Is APSP (for undirected graphs) as difficult as the Boolean multiplication of two |V| x |V | matrices?

[1] N. Alon, T. Kaufman, M. Krivelevich, and D. Ron. Testing triangle-freeness in general graphs. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 279-288, 2006.

Tiling chessboard by L-shaped trominoes

2008-04-18T18:17:00.000-04:00

Can you cover all but one square of an n x n chessboard by L-shaped trominoes?

Claim : If n is a power of 2, you can always do it !!

Have fun proving this !!

EC 2008

2008-04-13T12:24:00.000-04:00

EC 2008 accepted papers list is here.

Lipton Symposium and Trotter Conference

2008-04-09T15:38:00.000-04:00

I am eagerly waiting for the following two excellent conferences at GeorgiaTech :

The Lipton Theory Symposium (Apr 26 - Apr 28 2008) : Celebrating Dick Lipton's 60th birthday. Consists of very diverse and interesting set of talks.

New Directions in Algorithms, Combinatorics and Optimization (May 5 - May 9 2008) : Honoring the 65th Birthday of William T. Trotter. Excellent set of invited speakers and talks.

SWAT 2008 and ICALP 2008

2008-04-08T11:07:00.000-04:00

SWAT 2008 accepted papers list is here. (via dense outliers)
ICALP 2008 accepted papers list is here and here. (via mybiasedcoin)

25 Horses Puzzle

2008-04-02T23:15:00.000-04:00

There are 25 horses and only five tracks in a race (i.e., you can race 5 horses at a time). There is no stop clock !! Assume that there are no ties.

1: What is the minimum number of races needed to determine the 3 fastest horses in order from fastest to slowest ?
2: ..... to find out the fastest one ?
3: ..... to rank all of them from fastest to slowest ?
4: ..... to find the top k fastest horses ?

GeorgiaTech CS in Top 10

2008-04-01T16:04:00.000-04:00

The College of Computing at Georgia Tech jumped into the Top 10 (ranked 9th) in the latest rankings of graduate computer science (CS) programs by U.S. News & World Report. Within Computer Science GeorgiaTech is in top 10 in the following major research fields :)

Theory : 9th
Artificial Intelligence : 7th
Systems : 10th
Graphics/Visualization : 4th
Databases : 7th

Also, Georgia Tech is ranked 7th in Discrete Mathematics and Combinatorics.

Using Latex with Powerpoint

2008-03-19T17:00:00.000-04:00

Next week, I am going to give a talk at DIMACS/DyDAn Workshop on Secure Internet Routing. While preparing slides for my presentation, I realized that I LOVE powerpoint for its support for animation, but I HATE using its equation-editor. Also, I don't like preparing slides in latex (using beamer) due to lack of decent animation tools. I was googling around for a solution and found the following alternatives to combine the best of both worlds :

1) TexPoint : I like its support for inline latex compilation. But it is not free and I found many limitations in math fonts and \displaystyle.

2) Tex4PPT : This does not support Office 2007 yet. So I did not explore it.

3) Inkscape : This is the BEST way to combine latex and powerpoint. Its is FREE and opensource too !! Install Inkscape and follow these instructions to add support for latex. Inkscape allows you to type any crazy latex equation and convert into .eps format. You can even ungroup symbols in an equation and assign different colors to different symbols. Add the .eps file in the ppt file (using Insert -> Picture) and you can zoom-in/zoom-out the image without sacrificing the resolution !!

2007 ACM Turing Award

2008-02-05T13:26:00.000-05:00

ACM has named Edmund M. Clarke, E. Allen Emerson, and Joseph Sifakis the winners of the 2007 Turing Award...... "for their original and continuing research in a quality assurance process known as Model Checking".

STOC 2008

2008-02-03T15:01:00.000-05:00

STOC 2008 accepted papers list is here

Graph Isomosphism

2008-01-03T20:03:00.000-05:00

I found another paper claiming that graph isomorphism is in P.

FOCS, STOC, SODA statistics

2007-12-25T15:49:00.000-05:00

Merry Christmas and Happy New Year to all.

I noticed that DBLP added new features to search by a combination of author and venue. Here are some statistics for top theory conferences :

Most STOC Papers :
Avi Wigderson(43)
Robert Endre Tarjan(32)
Frank Thomson Leighton(27)
Uriel Feige(25)
Prabhakar Raghavan(24), Noam Nisan(24)

Most FOCS Papers :
Noga Alon(29)
Avi Wigderson(28), Baruch Awerbuch(28)
Christos H. Papadimitriou(26), Zvi Galil(26)

Most SODA Papers :

Pankaj K. Agarwal(26)
David Eppstein(25)
S. Muthukrishnan(23)
Uri Zwick(22), Micha Sharir(22)

Graph Isomorphism in P ?!?!

2007-11-14T23:41:00.000-05:00

I came across this paper claiming that Graph Isomorphism is in P.
I haven't read the paper yet. I don't know how reliable arxiv is (or) if this paper is reviewed !!

Graceful Trees !!

2007-07-28T17:19:00.000-04:00

I posted my favorite open problem (is every tree graceful ?) on the open problem garden. There are many more interesting open problems on this site.

A request to FOCS/STOC PC members

2007-07-25T23:23:00.000-04:00

Please read my guest post on Computational Complexity blog.

IIT Kharagpur CSE Silver Jubilee Alumni Reunion

2007-07-25T16:13:00.000-04:00

The Computer Science & Engineering Department at IIT Kharagpur has completed 25 years of its existence. If you are IIT-KGP-CSE alumni you can register for the events at the following site :

IIT Kharagpur CSE Silver Jubilee Alumni Reunion

Open Problem Garden !!

2007-07-13T10:09:00.000-04:00

Let me point you to this great site on open problems in mathematics, graph theory and theoretical computer science.

Open Problem Garden

I found this through Computational Complexity blog.

Turing's paper in FOCS ?

2007-07-05T00:38:00.000-04:00

Any PhD student in Theoretical Computer Science would find this hilarious !!

FOCS'36 notification

Einstein's Biography

2007-05-27T13:44:00.000-04:00

A recently released book titled Einstein: His Life and Universe is a biography of Albert Einstein.

One of his famous quotes, which I like the most is the following:

"Imagination is more important than knowledge. For knowledge is limited to all we now know and understand, while imagination embraces the entire world, and all there ever will be to know and understand".

Early to rise

2007-05-22T00:03:00.000-04:00

If you are lazy (like me) to wake up early in the morning you might want to try these cool (and annoying) alarm clocks.

Riemann hypothesis

2007-03-31T16:53:00.000-04:00

There is a paper on Arxiv claiming that the Riemann Hypothesis is false !!!

Tom Leighton's Talk

2007-03-12T14:23:00.000-04:00

Tom Leighton's Talk on "The Challenges of Delivering Content and Applications on the Internet"

Six Degrees

2006-12-09T17:32:00.000-05:00

In Spring 2005, I took this excellent course on networked information. This course introduced me to a new set of exciting problems. I learnt new techniques and models (mostly related to real-world networks like WWW, social networks, etc) through the reading list.

For those of you willing to know the motivation behind these models and their importance in the real-world, I recommend the following book :

Six Degrees : The Science of a Connected Age
by Duncan J. Watts

I am sure you will enjoy reading it.

Health is Wealth

2006-09-04T18:10:00.000-04:00

Some useful links....

Fields Medal 2006

2006-08-22T15:36:00.000-04:00

Fields Medal and other award winners are announced here.
Perelman has declined the Fields Medal !!

To PhD or Not To PhD

2006-08-05T17:56:00.000-04:00

Some interesting links on research life and PhD....

Principles of Effective Research by Michael A. Nielsen

How to Be a Good Graduate Student by Marie desJardins

The Ph.D Experience by Mihir Bellare

Network flow : integer vs real values

2006-07-28T17:20:00.000-04:00

Integer values are assumed in the analysis of most of the algorithms based on network flow. The reason for this is as follows.....

If the capacities on all the edges are integral then there always exists an integral flow.

If the capacities are rational numbers we can take the LCM and apply the same network flow algorithm (ford-fulkerson) by choosing augmenting paths arbitrarily.

If the capacities are real numbers, ford-fulkerson algorithm runs in polynomial time if augmenting paths are chosen via BFS. The algorithm might not terminate if the augmenting paths are chosen arbitrarily.

Assuming integer values makes the analysis much simpler, without worrying about how the augmenting paths are chosen. As said earlier, real-values can be handled efficiently using BFS.

A recent paper [1] analyzes the DFS approach of choosing augmenting paths.

[1] Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data Brian C Dean, Michel X. Goemans, Nicole Immorlica. To appear in the proceedings of the 14th annual European Symposium on Algorithms (ESA), 2006.

Graph Theory Books

2006-07-27T16:49:00.000-04:00

Free online (third) edition of Diestel's Graph Theory book is available here. This is one of the first books on Graph Theory, I read. Graph Theory with Applications by Bondy and Murty is another good introductory book. Its free online edition is here. I find lots of references to this book in graph theory and discrete math publications. Douglas West's Book is another excellent introductory book. Together these three books make an invaluable addition to your theory books library. I like the exercises in these books. If you read the chapters carefully you can come up with elegant and beautiful proofs for the exercises. If books have taglines, I would call these books Graph Theory: Fun Unlimited.

Complexity of Graph Isomorphism

2006-07-24T17:11:00.000-04:00

With the weekend temperatures of CA reaching 100, I had no choice but to sit at home in front of my small but efficient table fan. Having nothing else to do, I picked up this book, 'The Graph Isomorphism Problem: Its Structural Complexity', addressing the complexity of the graph isomorphism problem (ISO). The book uses ISO to illustrate the concepts of structural complexity. I learnt more about the structural complexity theory from this book than the ISO itself. This book makes an excellent weekend read (if you have some necessary background in graph theory and computational complexity). I am glad I read this book.

ISO problem is to decide whether there is a bijective mapping from the nodes of one graph to the nodes of the second graph such that the edge connections are respected. It is considered to be a hard problem and is not known to be in P or NP-Complete. Many researchers believe that ISO is not NP-Complete !! A complexity class called GI (graph isomorphism), (which is conjectured to be disjoint from both P and NP-Complete) is defined to understand the complexity of ISO !!

However, NP-Completeness of sub-graph isomorphism can be proved by reduction from HAMILTONIAN-PATH. (duh !)

ISO is in P for the following restricted classes :

bounded-degree graphs
planar graphs
trees (read this book "Algorithms on Trees and Graphs" by Gabriel Valiente for the various versions of tree-isomorphism (labeled vs unlabeled, top-down vs bottom-up))

ISO finds its applications in a wide range of areas like computational biology, data-mining, computational chemistry, matrix theory and so on. If you are looking for software, nauty serves as an excellent practical tool for graph isomorphism.

The Man Who Loved Only Numbers

2006-07-21T16:44:00.000-04:00

Paul Erdos and Erdos Number need no introduction. If you haven't read the book 'The Man Who Loved Only Numbers', here is a video lecture (by the author of the book) on the lifestyle of Paul Erdos.

Triangle Completion Game

2006-07-17T17:55:00.000-04:00

This game can be played by two people with paper and pencil.

Draw five points (vertices).

Player A starts by connecting any two vertices (i.e., adds an edge) with RED color.
Player B connects another two vertices (which are not previously connected) with GREEN color.
Player A again connects two more vertices with RED color.
and so on...

The first player to complete a triangle with his own color loses. i.e., the players' objective is to force the opponent to complete a triangle. If there is no triangle of any color then the game is a draw.

Claim : If player A starts the game (i.e., adds the first edge) then A can always force his opponent (B) to lose !!

Have fun proving this...

Stop Global Warming

2006-07-15T17:24:00.000-04:00

Following are some very simple ways to stop Global Warming....

You can completely stop paper mail. (Eg : I pay all my bills online. I don't get any paper mail in my mail box (except books from amazon)).
Do not use paper towels in the kitchen or living room. Instead use cloth towels. You can buy a dozen of them for less than $10 at costco.
Take print-outs (on both sides) only when necessary.
Use recycled paper for your research work (or) informal notes.
Never use paper cups, plastic spoons. Use washable mugs, metal spoons instead.
Make sure you turn off lights when you are not using them.
Use a different trash can for recyclable garbage and help in recycling.
Use cold water whenever you can (Eg: washing hands, dishes etc.,). Also, do not waste water.
Reuse plastic containers, plastic bags.
Use public transport and/or carpool whenever you can.
Turn your desktops off in the nights and when not in use.
Spend some time in educating people around you. Join an environmental organization if you can (Eg: you can spend saturday/sunday).

Hope you incorporate these steps in your lifestyles.

Related Links :

Blue man group on global warming.
Al Gore's Speech.

Number Magic

2006-07-14T14:56:00.000-04:00

Guess a positive integer n

if (n is even) {
n = n/2
} else { /* n is odd */
n = 3n + 1
}

Apply this process repeatedly.
This process will always reach the number 1

Eg : 6 -- 3 -- 10 -- 5 -- 16 -- 8 -- 4 -- 2 -- 1

This is Collatz conjecture and remains open till date !!

CRICKET is NP-Complete

2006-07-13T14:21:00.000-04:00

How do we decide the order of batsmen to maximize the cumulative runs made by them in 50 overs ? Here is my perspective......

Let's say we have the following statistics of batsmen based on their past performances.

average time spent by a batsman on the field.
average runs per over made (during past partnerships) for each pair of batsmen.

Given this data, we would like to decide the order of batsmen to maximize their runs (assuming they don't deviate much from their average past performance).

Formally speaking, we have a complete undirected weighted (vertex-weighted and edge-weighted) graph on n vertices. The vertices represent the batsmen and the weights on the vertices indicate the average time spent by the batsman on the field. The weight w on the edge (u,v) represents the average runs per over made (during past partnerships) by (u,v). That is, if u and v are playing on the field, they can together contribute at the rate of w runs per over. Having a bad partner hurts you, even if you are a high-scorer.

For example, the input graph can be as shown below...

The best schedule for m (=50) overs can be as shown below....

In the above figure, we have two rows representing the two batsmen on the field at any given time. The number of runs for the above schedule is derived by adding the length-of-overlap*edge-weight for each pair of players.

Theorem : Given the input graph G(V,E), finding the optimum (maximizing runs) schedule is NP-Complete.

I will post the proof at a later time in a later post. In the menwhile, you can try your own approaches to prove it. The next obvious question is about the approximability.

This model might not be pratical (due to noise, does not take other factors (like the skills of bowlers and bowler's schedule) into account) in real-life, but serves as a good mathematical puzzle.

P.S. Beginners can read the rules of cricket here. World Cup 2007 Schedule is here. Add this cool countdown to world cup to your google personalized homepage.

Transactions Minimization Problem

2006-07-12T18:35:00.000-04:00

In April 2000, I visited Agra with one of my friends (Amit) and his roommates (X,Y,Z) . At the end of the tour we ended up owing money to each other, due to the transactions during the trip (Eg : Amit paid for my taxi, I paid for X's food, Y paid for Amit's photo's at taj mahal etc etc.,). At the end of the trip we have to decide "who owes whom how much".

Normal human-beings might solve this problem in a step by step fashion through multiple transactions. Since we are computer sceintists, we will add some "constraints" and solve this problem "efficiently"'.

Formally speaking, we have a weighted directed graph G(V,E) where the vertices represent the people and a directed edge (u,v) with weight w means that u owes w-dollars to v.

For example, the following graph shows that a owes $10 to b, and b owes $20 to c.

There are two ways to perform the transactions.

First way :

a withdraws $10 from ATM
b withdraws $20 from ATM
a pays $10 to b
b pays $20 to c

Second way : reduce G to G' as shown below :

a withdraws $10 from ATM
b withdraws only $10 from ATM
a pays $10 to c
b pays $10 to c

Second way is better in the following sense :

b has withdrawn just as much money as required.
there are smaller (less money involved) transactions.
often there are lesser transactions (you can construct a complicated example to see this)
The transactions are still parallelizable !! (i.e., all the payments can occur simultaneously).

Formally, we want to reduce the graph G(V,E) to G'(V',E') such that,

Net amount (payed/received) is preserved for each person. (I am too lazy to write down the equations)
|E'| is as small as possible (or)

The sum of the weights of the edges in G' is minimized (or)

The maximum weight of an edge in G' is minimized.

Question : Design an efficient algorithm to reduce G to G'

I will stop here and let you solve this problem on your own.....

Graceful Tree Conjecture

2006-07-10T18:42:00.000-04:00

Label the vertices of a simple undirected graph G(V,E) (where V = n and E = m) with integers from 0 to m. Now label each edge with absolute difference of the labels of its incident vertices. The labeling is said to be graceful if the edges are labelled 1 through m inclusive (with no number repeated).

A graph is called graceful if it has atleast one such labeling. This labeling was originally introduced in 1967 by Rosa. The name graceful labeling was coined later by Golomb.

Gracefully labeled graphs serve as models in a wide range of applications including coding theory and communication network addressing.

The graceful labeling problem is to determine which graphs are graceful. It is conjectured (by Kotzig, Ringel and Rosa) that all trees are graceful.

Despite numerous (more than 200) publications on graceful labeling for over three decades, only a very restricted classes of trees have been shown to be graceful. These restriced classes include paths, stars, complete bi-partite graphs, prism graphs, wheel graphs, caterpillar graphs, olive trees, and symmetrical trees.