Graph Theory

Moved to wordpress

2012-07-21T17:26:00.005-04:00

I am no longer maintaining this blog. Visit my new blog hosted on wordpress at My Brain is Open.

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

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.

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

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.

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.

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.

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.

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.

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.

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.

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...

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 !!

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.

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 ?

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 like 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 !!

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.

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.

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.

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.