STOC 2010 Accepted Papers (with pdf files)

STOC 2010 accepted paper list is here.

As usual I am collecting pointers to online versions.

• Budget Constrained Auctions with Heterogeneous Items [arXiv]
  Sayan Bhattacharya (Duke), Gagan Goel (Georgia Tech), Sreenivas Gollapudi (Microsoft Research) and Kamesh Munagala (Duke)

• On the Structure of Cubic and Quartic Polynomials [arXiv]
  Elad Haramaty and Amir Shpilka (Technion)

• BQP and the Polynomial Hierarchy [arXiv] [ppt]
  Scott Aaronson (MIT)

• Sorting under Partial Information (without the Ellipsoid Algorithm) [arXiv]
  Jean Cardinal (ULB), Samuel Fiorini (ULB), Gwenaël Joret (ULB), Raphaël Jungers (MIT) and J. Ian Munro (University of Waterloo)

• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth [arXiv]
  MohammadHossein Bateni (Princeton University), MohammadTaghi Hajiaghayi (AT&T Labs — Research) and Dániel Marx (Tel Aviv University)

• Extensions and Limits to Vertex Sparsification
  Tom Leighton (MIT and Akamai Technologies, Inc) and Ankur Moitra (MIT)

• Efficiently Learning Mixtures of Two Gaussians
  Adam Tauman Kalai (Microsoft), Ankur Moitra (MIT), and Gregory Valiant (UC Berkeley)

• Oblivious RAMs without Cryptographic Assumptions
  Miklos Ajtai (IBM Almaden Research Center)

• The HOM problem is decidable [pdf]
  Guillem Godoy, Omer Giménez, Lander Ramos and Carme Àlvarez (Universitat Polit`ecnica de Catalunya)

• Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in [pdf]
  Zohar S. Karnin and Partha Mukhopadhyay and Amir Shpilka and Ilya Volkovich (Technion)

• Improved Algorithms for Computing Fisher’s Market Clearing Prices
  James B. Orlin (MIT)

• Optimal Bounds for Sign-Representing the Intersection of Two Halfspaces by Polynomials [arXiv]
  Alexander A. Sherstov (Microsoft Research)

• QIP = PSPACE [arXiv]
  Rahul Jain (National University of Singapore), Zhengfeng Ji (Perimeter Institute), Sarvagya Upadhyay (University of Waterloo) and John Watrous (University of Waterloo)

• Augmenting undirected node-connectivity by one [pdf]
  Laszlo A. Vegh (MTA-ELTE Egervary Research Group and Department of Operations Research, Eotvos University)

• Solving Polynomial Equations in Smoothed Polynomial Time and a Near Solution to Smale’s 17th Problem
  Peter Buergisser (University of Paderborn) and Felipe Cucker (City University of Hong Kong)

• Matroid Matching: the Power of Local Search [IBM TechReport]
  Jon Lee (IBM TJ Watson Research Center), Maxim Sviridenko (IBM TJ Watson Research Center) and Jan Vondrak (IBM Almaden Research Center)

• Tensor-Rank and Lower Bounds for Arithmetic Formulas [pdf]
  Ran Raz (Weizmann Institute)

• Towards Polynomial Lower Bounds for Dynamic Problems [pdf]
  Mihai Patrascu (AT&T Labs)

• Improving Exhaustive Search Implies Superpolynomial Lower Bounds [pdf]
  Ryan Williams (IBM Almaden Research Center)

• An Optimal Ancestry Scheme and Small Universal Posets
  Pierre Fraigniaud and Amos Korman (CNRS and Univ. Paris Diderot)

• Tractable hypergraph properties for constraint satisfaction and conjunctive queries [arXiv]
  Dániel Marx (Tel Aviv University)

• On the searchability of small-world networks with arbitrary underlying structure
  Pierre Fraigniaud (CNRS and Univ. Paris Diderot) and George Giakkoupis (Univ. Paris Diderot)

• Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses
  Holger Dell (Humboldt University of Berlin) and Dieter van Melkebeek (University of Wisconsin-Madison)

• A shorter proof of the Graph Minor Algorithm – The Unique Linkage Theorem
  Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo) and Paul Wollan (University of Rome, La Sapienza)

• Pseudorandom Generators for Polynomial Threshold Functions [arXiv]
  Raghu Meka and David Zuckerman (University of Texas at Austin)

• How to Compress Interactive Communication [pdf]
  Boaz Barak (Princeton University), Mark Braverman (Microsoft Research New England), Xi Chen (University of Southern California) and Anup Rao (University of Washington)

• Zero-One Frequency Laws
  Vladimir Braverman and Rafail Ostrovsky (UCLA)

• The maximum multiflow problems with bounded fractionality
  Hiroshi Hirai (Reseach Institute for Mathematical Sciences, Kyoto University)

• Measuring Independence of Datasets [arXiv]
  Vladimir Braverman and Rafail Ostrovsky (UCLA)

• On the Geometry of Differential Privacy [arXiv]
  Moritz Hardt (Princeton University) and Kunal Talwar (Microsoft Research)

• An Invariance Principle For Polytopes [arXiv]
  Prahladh Harsha (Tata Institute of Fundamental Research), Adam Klivans (UT-Austin) and Raghu Meka (UT-Austin)

• Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs [arXiv]
  Ashish Goel (Stanford University and Twitter), Michael Kapralov (Stanford University) and Sanjeev Khanna (University of Pennsylvania)

• A Quantum Lovasz Local Lemma [arXiv]
  Andris Ambainis (University of Latvia), Julia Kempe (Tel Aviv University) and Or Sattath (Hebrew University and Tel Aviv University)

• Bayesian Algorithmic Mechanism Design [arXiv]
  Jason D. Hartline (Northwestern University) and Brendan Lucier (University of Toronto)

• A Strong Direct Product Theorem for Disjointness [arXiv]
  Hartmut Klauck (Centre for Quantum Technologies, Singapore)

• Recognizing well-parenthesized expressions in the streaming model [arXiv]
  Frederic Magniez (LRI, Univ. Paris-Sud, CNRS), Claire Mathieu (Brown University) and Ashwin Nayak (U. Waterloo and Perimeter Institute)

• Conditional Hardness of Precedence Constrained Scheduling on Identical Machines [pdf]
  Ola Svensson (KTH – Royal Institute of Technology, Stockholm)

• An Improved LP-based Approximation for Steiner Tree
  Jaroslaw Byrka (EPFL, Lausanne), Fabrizio Grandoni (Universita di Roma Tor Vergata), Thomas Rothvoss (EPFL, Lausanne) and Laura Sanita (EPFL, Lausanne)

• On the Complexity of #CSP
  Martin Dyer and David Richerby (University of Leeds)

• Approximate Sparse Recovery: Optimizing Time and Measurements [arXiv]
  Anna Gilbert (University of Michigan) Yi Li (University of Michigan), Ely Porat (Bar Ilan University) and Martin Strauss (University of Michigan)

• On the Hardness of the Noncommutative Determinant [arXiv]
  Vikraman Arvind and Srikanth Srinivasan (Institute of Mathematical Sciences, Chennai)

• A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations [ECCC]
  Daniele Micciancio and Panagiotis Voulgaris (UCSD)

• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs [arXiv]
  Mohsen Bayati (Stanford), David Gamarnik (MIT) and Prasad Tetali (Georgia Institute of Technology)

• Weighted Geometric Set Cover via Quasi-Uniform Sampling
  Kasturi Varadarajan (University of Iowa)

• Complexity Theory for Operators in Analysis [pdf]
  Akitoshi Kawamura and Stephen Cook (University of Toronto)

• Odd Cycle Packing
  Ken-ichi Kawarabayashi (National Institute of Informatics, Japan) and Bruce Reed (McGill University and Projet MASCOTTE)

• The Median Mechanism: Interactive and Efficient Privacy with Multiple Queries [pdf]
  Aaron Roth (CMU) and Tim Roughgarden (Stanford)

• On the Round Complexity of Covert Computation
  Vipul Goyal (MSR India) and Abhishek Jain (UCLA)

• Public-Key Cryptography from Different Assumptions
  Benny Applebaum (Weizmann Institute of Science), Boaz Barak (Princeton University) and Avi Wigderson (Institute for Advanced Study)

• On the List-Decodability of Random Linear Codes [arXiv]
  Venkatesan Guruswami (Carnegie Mellon University), Johan Håstad (KTH – Royal Institute of Technology) and Swastik Koppart (Massachusetts Institute of Technology)

• Hardness Amplification in Proof Complexity [arXiv]
  Paul Beame (University of Washington), Trinh Huynh (University of Washington) and Toniann Pitassi (University of Toronto)

• Non-commutative circuits and the sum-of-squares problem [pdf]
  Pavel Hrubes (Princeton University), Avi Wigderson (Institute for Advanced Study) and Amir Yehudayoff (Institute for Advanced Study)

• Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
  Aleksander Madry (MIT)

• Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions
  Iftach Haitner (Microsoft Research New England), Omer Reingold (Microsoft Research Silicon Valley and Weizmann Institute of Science) and Salil Vadhan (Harvard University)

• Load balancing and orientability thresholds for random hypergraphs
  Pu Gao and Nicholas Wormald (University of Waterloo)

• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
  Ilias Diakonikolas (Columbia University), Prahladh Harsha (Tata Institute of Fundamental Research), Adam R. Klivans (University of Texas), Raghu Meka (University of Texas), Prasad Raghavendra (Microsoft Research New England), Rocco A. Servedio (Columbia University) and Li-Yang Tan (Columbia University)

• Graph Expansion and the Unique Games Conjecture
  Prasad Raghavendra (Microsoft Research New England) and David Steurer (Princeton University)

• Approximations for the Isoperimetric and Spectral Profile of Graphs and Related Parameters
  Prasad Raghavendra (Microsoft Research New England), David Steurer (Princeton University) and Prasad Tetali (Georgia Tech)

• Detecting High Log-Densities — an $O(n^{1/4})$ Approximation for Densest $k$-Subgraph [arXiv]
  Aditya Bhaskara (Princeton University), Moses Charikar (Princeton University), Eden Chlamtac (Weizmann Institute of Science), Uriel Feige (Weizmann Institute of Science) and Aravindan Vijayaraghavan (Princeton University)

• Near-optimal extractors against quantum storage [arXiv]
  Anindya De and Thomas Vidick (UC Berkeley)

• On the Complexity of Circuit Satisfiability [pdf] [video]
  Ramamohan Paturi (University of California, San Diego) and Pavel Pudl\’ak (Mathematical Institute of the Czech Academy of Sciences)

• Connectivity Oracles for Failure Prone Graphs
  Seth Pettie and Ran Duan (University of Michigan)

• Multi-parameter mechanism design and sequential posted pricing [arXiv]
  Shuchi Chawla (University of Wisconsin-Madison), Jason Hartline (Northwestern University), David Malec (University of Wisconsin-Madison) and Balasubramanian Sivan (University of Wisconsin-Madison)

• Subgraph Sparsification and Nearly Optimal Ultrasparsifiers [arXiv]
  Alexandra Kolla (Institute for Advanced Study), Yury Makarychev (Toyota Technological Institute at Chicago), Amin Saberi (Stanford University) and Shang-Hua Teng (University of Southern California)

• Bilipschitz snowflakes, metrics of negative type, and PSD flows
  James R. Lee and Mohammad Moharrami (University of Washington)

• The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model
  Elad Verbin (ITCS, Tsinghua University) and Qin Zhang (Hong Kong University of Science and Technology)

• Optimal Homologous Cycles, Total Unimodularity, and Linear Programming [arXiv]
  Tamal K. Dey (Ohio State University), Anil N. Hirani (University of Illinois at Urbana-Champaign) and Bala Krishnamoorthy (Washington State University)

• Distributed Computation in Dynamic Networks [MIT TechReport]
  Fabian Kuhn (University of Lugano), Nancy Lynch (MIT) and Rotem Oshman (MIT)

• A Full Characterization of Quantum Advice
  Scott Aaronson and Andrew Drucker (MIT)

• Maintaining a Large Matching or a Small Vertex Cover
  Krzysztof Onak (MIT) and Ronitt Rubinfeld (MIT and Tel Aviv University)

• Almost Tight Bounds for Rumour Spreading with Conductance
  Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi (Sapienza University)

• Changing Base without Losing Space
  Yevgeniy Dodis (New York University) and Mihai Pastrascu (AT&T Labs) and Mikkel Thorup (AT&T Labs)

• The Price of Privately Releasing Contingency Tables and the Spectra of Random Matrices with Correlated Rows
  Shiva Kasiviswanathan (Los Alamos National Laboratory), Mark Rudelson (University of Missouri), Adam Smith (Pennsylvania State University) and Jonathan Ullman (Harvard University)

• Saving Space by Algebraization
  Daniel Lokshtanov and Jesper Nederlof (University of Bergen)

• Privacy Amplification with Asymptotically Optimal Entropy Loss
  Nishanth Chandran (UCLA), Bhavana Kanukurthi (Boston University), Rafail Ostrovsky (UCLA) and Leonid Reyzin (Boston University)

• A Sparse Johnson-Lindenstrauss Transform
  Anirban Dasgupta and Ravi Kumar and Tamas Sarlos (Yahoo! Research)

• Local List-Decoding and Testing of Random Linear Codes from High-Error [pdf]
  Swastik Kopparty and Shubhangi Saraf (MIT)

• Differential Privacy Under Continual Observation
  Cynthia Dwork (Microsoft Research), Moni Naor (Weizmann Institute), Toniann Pitassi (University of Toronto) and Guy Rothblum (Princeton University)

Logspace vs Polynomial time

One of the primary goals of complexity theory is separating complexity classes, a.k.a proving lower bounds. Embarrassingly we have only a handful of unconditional separation results. Separating P from NP is of course the mother of all such goals. Anybody who understands the philosophical underpinnings of the P vs NP problem would love to LIVE to see its resolution. Towards resolving this, we made some (“anti”)-progress (Eg : Relativization, Natural proofs, Algebrization) and have a new geometric complexity theory approach which relies on an Extended-Extended-Extended-Extended-Riemann-Hypothesis !! For more information about the history and status of P vs NP problem read Sipser’s paper [Sipser'92], Allender’s status report [Allender'09] or Fortnow’s article [Fortnow'09].

Today’s post is about the Logspace (L) vs Polynomial time (P) problem, which (in my opinion) is right next to the P vs NP problem in its theoretical importance. I guess many researchers believe that . Did we make any progress/anti-progress towards resolving the conjecture ?  Here are two attempts both based on branching programs and appeared in MFCS with a gap of 20 years !!

1) A conjecture by Barrington and McKenzie (BM’89): The problem is defined as follows :

: Given an table filled with entries from , which we interpret as the multiplication table of an -element groupoid, and a subset of which includes element 1, determine whether the subgroupoid , defined as the closure of under the groupoid product, includes element .

Barrington-McKenzie Conjecture : For each , a branching program in which each node can only evaluate a binary product within an -element groupoid, branching ways according to the possible outcomes, must have at least nodes to solve all instances with singleton starting set .

The problem is known to be P-complete [JL'76]. Barrington-McKenzie Conjecture would imply that for any . In particular, it would imply that . I don’t know if there is any partial progress towards resolving this conjecture.

2) Thrifty Hypothesis : This is a recent approach by Braverman et. al [BCMSW'09] towards proving a stronger theorem . Stephen Cook presented this approach at Valiant’s 60th birthday celebration and Barriers Workshop. He also announced a $100 prize for solving an intermediate open problem mentioned in his slides.

Tree Evaluation Problem (TEP): The input to the problem is a rooted, balanced -ary tree of height , whose internal nodes are labeled with -ary functions on , and whose leaves are labeled with elements of . Each node obtains a value in equal to its -ary function applied to the values of its children. The output is the value of the root.

In their paper they show that and conjecture that . They introduce Thrifty Branching Programs and prove that TEP can be solved by a thrifty branching program. A proof of the following conjecture implies that . For more details, read this paper.

Thrifty Hypothesis : Thrifty Branching Programs are optimal among deterministic branching programs solving TEP.

Open Problems :

• My knowledge about the history of L vs P problem is limited.  Are there other approaches/attempts in the last four decades to separate L from P ?
• An intermediate open problem is mentioned in the last slide of these slides. The authors announced $100 prize for the first correct proof. Read their paper for more open problems.

References :

• [BM'89] David A. Mix Barrington, Pierre McKenzie: Oracle Branching Programs and Logspace versus P. MFCS 1989: 370-379
• [BCMSW'09] Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr: Branching Programs for Tree Evaluation. MFCS 2009: 175-186
• [Sipser'92] Michael Sipser: The History and Status of the P versus NP Question STOC 1992: 603-618
• [Allender'09] Eric Allender: A Status Report on the P Versus NP Question. Advances in Computers 77: 117-147 (2009) [pdf]
• [Fortnow'09] Lance Fortnow: The status of the P versus NP problem. Commun. ACM 52(9): 78-86 (2009) [pdf]
• [JL'76] Neil D. Jones, William T. Laaser: Complete Problems for Deterministic Polynomial Time. Theor. Comput. Sci. 3(1): 105-117 (1976)

The Ideal TabletPC

Today’s post is about “Why tabletPC ?” and more importantly “What features should an ideal tabletPC have ?“ I have been thinking of writing this post for more than an year. Somehow I think I have to write this asap, because there are  too many silly “magical” gadgets in the market now. I agree that these gadgets have their own advantages. For example (i) your mom who knows nothing about computers can use it (ii) your father can use it to read New York Times (iii) your book-loving girlfriend can read e-books and so on. While I appreciate these features, I refuse to call these gadgets “A Tablet“. It is a huge disrespect to some really good products in the market.

Whenever I buy any electronic gadget I always try to buy the best one on the market. No compromises. Let me repeat “No compromises“. When I wanted to buy a tabletPC three years back, I looked at the models that my friends and colleagues have and none of them really impressed me. They have some missing feature or the other. I said to myself “probably the world is not ready for a tabletPC that can be used on a daily basis”. Then I stumbled upon a company named Motion Computing that makes tabletpcs primarily for the healthcare market. None of my colleagues seem to have even heard its name. I noticed that Motion’s tabletPCs are really costly. After going back and forth for six months I bought LE1700 for around $2000 (along with the detachable keyboard). Well… why would a PhD student, living on a paycheck-to-paycheck basis, spend so much money on a tabletPC. Well… having used it for over two years now, I never felt that I made a wrong decision. In fact, now I cannot imagine doing my research without my tabletPC.

Following are some reasons to like my tabletPC. Hopefully, they will also answer the big question “Why TabletPC ?“. Please use these as a checklist before you buy any tabletPC. If you are a student/professional and want to use your tabletPC on a daily basis, I think the following features are a must.

• Basic features : Of course you want all the basic features that a regular laptop has. For example, fast processor, large memory, enough hard drive capacity, Wifi, bluetooth, good battery life and so on.

• Weight : When it comes to tabletpcs weight is a major factor. Sometimes you might want to take quick notes holding it in your hands. I think 3 lbs weight of LE1700 is decent, but 2.5lbs would have been ideal.

• Diplay size : If you are doing serious work like annotating pdf files, writing lecture notes in OneNote etc., then 12 inch display is a must. LE1700 has 12.1 inch display. Notice that most of the software (OneNote, PDF Annotator, Internet browser with bookmarks and extensions) already use at least one inch for the header (if you carefully arrange all the frequently used features as buttons).

• Look and Feel of the screen : You want a screen that feels right. You should be able to write on it without messing up your handwriting. Also the view angle of the display is very important. If you don’t have a laptop stand you should still be able to put it on a flat desk and read/write without straining your neck. Motion Computing did a good job in this department. They have award-winning View Anywhere Display Technology, which is simply awesome.

• Good grip : Believe me, you don’t want to hold your tabletpc like a dinner plate in a buffet party. You should be able to hold it like a regular notepad and take notes, without blocking any of the display. LE1700 has an nice vertical non-slippery grip which (elegantly) is the battery itself.

• Security : LE1700 has an inbuilt fingerprint scanner that can be used for secure login. Pretty cool.

Apart from the above must-have features, if you have the right kind of software, working on a tabletpc is a real pleasure. Following are some must-have software along with the reasons.

• Operating System : The windows tabletpc software is awesome. The on-screen keyboard with inbuilt dictionary and handwriting (learning and) recognition software and the snipping tool are indispensable. I agree that Vista sucked big time (because it is freaking slooooooow), but Windows 7 (with tablet PC enhancements) rocks !! Many of Windows 7 features are better exploited in a tabletpc than in a laptop. For example sticky notes, which I use all the time.

If somebody asks me ‘what are the best software products that came out of Microsoft ?’, I would say Powerpoint, OneNote and VC++. The first two are very neat on a tabletPC.

• Powerpoint : Again, many of the features of powerpoint (eg : able to draw free hand diagrams during presentations) are better exploited on a tabletpc. In fact sometimes I prepare handwritten slides. Saves me a lot of time. You don’t have to search for greek symbols. Just write it and move on (assuming you have a decent hand writing). Sometimes I leave blank slides with just the title and draw the required diagram during the talk. Makes the presentation more interactive.

• One Note : This is one software which you will use 80% of the time (if you are a student). I really appreciate the auto-save feature in OneNote. It makes a lot of sense in a frequently used editor. You can write anything, use any ink color, cut and paste any on-screen content using the snipping tool, organize your notes with notebooks/files/pages hierarchy, etc. etc., You don’t have to buy another notebook (the one with pages made out of papyrus) in your life again.

There is also a software called Windows Journal. It is “just fine” when compared to OneNote. As Spock says, “Fine has variable definitions. Fine is not acceptable”.

• Hand-writing Recognition : I use hand-writing recognition to convert my OneNote notes to text. I wrote most of this post on my tabletPC and converted to text. Cool eh !!

• Voice recognition : This is a cool feature which I hardly use. You can speak “open windows media player”, “play savatage song” and your PC obeys.

Third party software : I use the following third party software to make life a little better.

• PDF Annotator : If you are reading lots of pdf files (if you are a student you will), then you need PDF annotator. It allows you to write on any pdf file, add blank pages and save them as pdf files. I bought LE1700 2.5 years back, so I had an older version of PDF annotator. I had to upgrade it for $19.90 (special price for students).

• PDF Printer : This free software allows you to save anything (in particular your OneNote notes) as a pdf file, using a virtual printer. Very useful.

• Dropbox : Dropbox is somewhat unrelated to tabletpc, but nevertheless an awesome must-have software. Read my earlier post for more details.

• WinEdt : This is also unrelated to tabletpc. I want to say that WinEdt+MikTex makes your latex editing easy.

Accessories : I bought a detachable keyboard (which also acts a screen protector when you are cramming your tabletPC in your laptop bag) from motion computing. I also bought a third party laptop stand (a.k.a laptop lifter) for around $30. It gives me a good writing angle when I am using my tabletpc on my desk.

To summarize, two of the biggest advantages of having a tabletPC are :

• Go Paperless : After I bought my tabletPC the number of times I use my printer went down to zero. Now I use my printer only if I have to print fandango movie tickets or airfare tickets for reimbursement. Why do I need a printer if I can annotate e-books and research articles. You might say “its bad for your eyes to stare at the screen for a long time”. Well this is where the intelligent View Anywhere Display comes in. Set the display in dynamic mode and you won’t feel a thing.

• Easy Travel : When I go to school or conference or travel anywhere all I need is my tabletPC. If I have it, I know that all my research work is with me. Now thats the type of freedom I always wanted. Also, all my documents including OneNote notes, pdf files, latex source files, are automagically backed-up through Dropbox.

Disadvantages : I would like to note the following negative points about LE1700.

• Price : Whenever I show my tabletPC to my friends and colleagues they say “WOW !!”. But none of them bought it. The main reason being the price. It would be great if motion computing can make affordable models targeting students. They did a good job in healthcare market. Why not the student market ?
• Weight : 3lbs is decent. But 2.5 lbs would be ideal.
• Marketing : When I say I have Motion Computing LE1700 tabletPC, I see many blank faces. Not many people know that this company exists. At least not as well as they know HP/Fujitsu/Dell. Well… you have a good product why don’t you market it aggressively ?

Bottom line : I hope more companies make sensible and affordable tabletpcs targeting students. If they are designed and used appropriately, they can make your life and work a lot of fun.

Update (30th Jan 11:00pm EST) : I forgot to mention that LE1700 is being discontinued. Now motion computing has an even better model called J3400. I envy this model because it is better than LE1700 in overall build quality and its look and feel. I also like its rubber finish at the bottom. It has better accessories too. For example, its detachable keyboard is more elegant compared to that of LE1700.

If I want to buy a tabletPC today, I would go for J3400.

Approximating TreeWidth

Today’s post is about TreeWidth, an awesome concept introduced by Robertson and Seymour, 25 years ago. When I first came across treewidth, I became an instant fan.

Definition : A tree-decomposition of a graph is a pair where is a family of subsets of , one for each node of , and is a tree such that :

• The union of the sets is equal to .
• for all edges , there exists an with and .
• for all : if is on the path from to in , then .

The treewidth of a tree-decomposition is . The treewidth of a graph is the minimum treewidth over all possible tree-decompositions of .

Following are some interesting facts :

• Exercise : TreeWidth of a tree is 1.
• Exercise : TreeWidth of a clique on vertices in .
• Determining whether treewidth of a given graph is at most is NP-complete.
• See [BGHK'95] for interesting applications of treewidth Eg : Choleski factorization on sparse symmetric matrices.
• There is an analogous notion of pathwidth which is also NP-complete.

Approximating tree-width : Bodlaender et. al [BGHK'95] presented an factor approximation algorithm for treewidth. This also gives an factor approximation algorithm for pathwidth. Their algorithm works by repeatedly finding vertex separators and uses Leighton-Rao’s algorithm at its heart. The main insights from their paper are as follows :

• If there is a factor approximation algorithm for vertex separator then there is an approximation algorithm for treewidth.
• if there is a factor approximation algorithm for treewidth then there is an approximation algorithm for pathwidth.

In 1995 the best known approximation factor for vertex separator was . Feige, Hajiaghayi and Lee [FHL'2008] improved this to . Hence we have  and  factor approximation factors for treewidth and pathwidth respectively.

Special cases : What about computing treewidth of restricted classes of graphs ?

• When is any fixed constant, the graphs with treewidth can be recognized, and a width tree decomposition can be constructed for them, in linear time [Bodlaender'96].
• Seymour and Thomas [ST'] showed that branchwidth of planar graphs can be computed in polynomial time. This implies a factor 3/2 approximation for treewdith of planar graphs.

Bounded TreeWidth : If the treewidth of a graph is bounded by some fixed constant , then several problems (that are NP-hard (even PSPACE-hard) for general graphs) can be solved in polynomial-time and often linear time !! Some of them include Maximum Independent set (hence maximum Clique), Hamiltonian cycle, Graph Isomorphism. Instead of listing all these problems, lets look at the following awesome theorem.

Courcelle’s Theorem : Any property of graphs definable in monadic second-order logic (MSO2) can be decided in linear time on any class of graphs of bounded tree-width. In other words, MSO2 is fixed-parameter tractable on any such class of graphs.

More information about Courcelle’s theorem can be found in this book. A recent paper (appeared today on arXiv) proved the following lower bound.

Theorem [KT'2010] : If C is any class of graphs which is closed under taking sub-graphs and whose tree-width is not bounded by a poly-logarithmic function then MSO2-model checking is intractable on C (under suitable assumptions from complexity theory)

There are several open problems related to treewidth, pathwidth, branchwidth and the related cops-robber games. Following are some that interest me :

Open Problems :

• Perhaps the most interesting open question is to obtain a constant factor approximation for treewidth.
• Bodlaender et. al ruled out absolute approximation algorithm, (unless P = NP) for treewidth and pathwidth. This is the best known hardness. Can we even rule out PTAS for treewidth ? Note that the hardness of treewidth implies the hardness of vertex separator (with constant factor blow-up).
• How hard is computing treewidth of planar graphs ? NP-hardness is not known. Many researchers I talked to, believe that treewidth of planar graphs can be computed in polynomial-time.
• Can the lower bound from [KT'2010] be improved ? In this context, it is interesting to note that Maximum Independent Set can be solved in polynomial time even when the treewidth is bounded by .
• Datta et. al [DLNTW'2009] showed that planar graph isomorphism is in logspace. Is isomorphism for graphs with bounded treewidth in logspace ? I asked this question to some researchers, and this seems to be an open problem.

References :

• [BGHK'95] Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, Ton Kloks: Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree. J. Algorithms 18(2): 238-255 (1995)
• [Bodlaender'96] Bodlaender, Hans L. : A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25 (6): 1305–1317 (1996)
• [KT'2010] Stephan Kreutzer, Siamak Tazari Lower Bounds for the Complexity of Monadic Second-Order Logic arXiv:1001.5019
• [FHL'2008] Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee: Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput. 38(2): 629-657 (2008)
• [ST'90] PaulD.Seymour and Robin Thomas : Call Routing and the Ratcacher. Combinatorica 14(2): 217-241 (1994)
• [DLNTW'2009] Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Planar Graph Isomorphism is in Log-Space. IEEE Conference on Computational Complexity 2009: 203-214

Open Problems from FOCS 2009

Here are some open problems (that interest me) from FOCS 2009. If you want to share an open problem, please leave a comment.

Starting with my paper…….

1) Reducibility Among Fractional Stability Problems [pdf]

Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng.

Summary : We resolve the computational complexity of a number of outstanding open problems with practical applications and introduce a simple PPAD-complete game (the preference game). Here is the list of problems we show to be PPAD-complete, along with the domains of practical significance:  1) Fractional Stable Paths Problem (FSPP) – Internet routing;  2) Core of Balanced Games – Economics and Game theory;  3) Scarf’s Lemma – Combinatorics;  4) Hypergraph Matching – Social Choice and Preference Systems;  5) Fractional Bounded Budget Connection Games (FBBC) – Social networks; and 6) Strong Fractional Kernel – Graph Theory.

Open Problems : The complexity of Discrete Ham Sandwich Problem and Necklace Splitting Problem are open. These are shown to be in PPAD by Papadimitiou in 1994.

2) Linear systems over composite moduli [pdf]

Arkadev Chattopadhyay and Avi Wigderson.

Summary and Open Problems : Dick Lipton already summarized their result along with open problems.

3) Regularity Lemmas and Combinatorial Algorithms [pdf]

Nikhil Bansal, Ryan Williams

Summary : This paper presents new combinatorial algorithms for Boolean matrix multiplication (BMM) and preprocessing a graph to answer independent set queries. The authors give the first asymptotic improvements on “combinatorial” algorithms for dense BMM in many years, improving on the Four Russians bound. Their use of Triangle removal lemma and Regularity lemma are particularly interesting.

Open Problems : Ryan mentioned the following open problems in his talk : (1) Can one construct a Weak Regular partition in time, deterministically ? (2) Can their techniques be applied to All Pairs Shortest Paths Problems ? (3) is there a Regularity concept that is better suited for Matrix Multiplication ?

4) Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP [pdf]

Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Howard Karloff

Summary : They give a factor 1.990283 approximation algorithm for Prize-collecting TSP. This is the first result to break the barrier of 2 improving the primal-dual algorithm  of Goemans and Williamson. Recently Goemans, presented a 1.91457-approximation algorithm for the prize-collecting travelling salesman problem.

Open Problem : Obvious open problem is to improve this approximation factor.

5) Blackbox Polynomial Identity Testing for Depth 3 Circuits [pdf]

Neeraj Kayal and Shubhangi Saraf.

Open Problems : This paper has a well-written open problems section with specific open problems. If you are interested in polynomial identity testing, I encourage you to read them.

Complexity of Matrix Multiplication

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.

Today’s post is about the following question and related problems.

Given an undirected graph , how fast can we detect if is triangle-free ?

Cubic time is obvious. A faster algorithm computes the square of the adjacency matrix of  and runs in time , where is the matrix multiplication exponent. This simple algorithm is the best known !!

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

Look at [AKKR'06] for recent results. A related problem is all pairs shortest paths (APSP). This is a fundamental graph problem and its exact complexity is still open.

Is APSP (for undirected graphs) as difficult as the Boolean multiplication of two |V| x |V | matrices?

These problems are tightly related to matrix multiplication, whose complexity is also open. The best value of is 2.376. At Barriers Workshop, Chris Umans presented an exciting group-theoretic approach [CU'03, CKSU'05] to improving . Using their techniques, the best value of they achieved is 2.41. In their paper, they made two conjectures, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.

Is  ?

Now, that would be a surprise in mathematics and theory. Many well-known problems are reducible to matrix multiplication. Eg : determinant, LUP decompositions, matrix inversion and many problems in linear algebra.

The techniques which led to 2.376 are primarily based on divide and conquer. The technique of [CU'03, CKSU'05] is a different one and worth pursuing. Are there any other techniques explored ? If you know of other techniques, please leave a comment, even if they resulted in a modest value of .

References :

• [AKKR'06] 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.
• [CKSU'05] Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, Christopher Umans. Group-theoretic Algorithms for Matrix Multiplication. FOCS 2005: 379-388
• [CU'03] Henry Cohn, Christopher Umans: A Group-Theoretic Approach to Fast Matrix Multiplication. FOCS 2003: 438-449

A Generalization of Erdos’s Proof of Bertrand-Chebyshev Theorem

Bertrand’s postulate states that for every positive integer n, there is always at least one prime psuch 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

• Goldbach’s conjecture : Every even integer n > 2 can be written as the sum of two primes ?
• Twin prime conjecture : There are infinitely many primes p such that p+2 is prime ?
• Are there infinitely many primes p such that p-1 is a perfect square ?

All these problems are open till date !! Lets look at 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. Recently I generalized Erdos’s Proof of Bertrand-Chebyshev’s Theorem and 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.

Like Erdos’s Proof, my generalization uses elementary combinatorial techniques without appealing to the prime number theorem. An initial draft is available on my homepage.

I have the following question :

Are there infinitely many primes p such that p+k is prime ?

Is the answer known for any fixed k > 2 ? What if k is allowed to depend on p ? If you know any papers addressing such questions, please leave a comment.

Random Restriction and Circuit Lower Bounds

The class \aczero\ consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class \saczero\ is the semi-unbounded version of \aczero\ i.e., AND gates have constant fan-in.

The class consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class  is the semi-unbounded version of  i.e., AND gates have constant fan-in. In the class  both AND and OR gates have constant fan-in. The following strict hierarchy is known.

For all prime numbers , .

Todays post is is about the following theorem.

Theorem :

Proof : is closed under complementation and is not.

Exercise : Prove that is not closed under complementation.

Recently I came up with an alternate proof of the above theorem using the technique of random restriction of Furst, Saxe and Sipser [FSS'81]. I think my proof can be given as a cool homework problem in introductory complexity theory course. Here it goes…..

Let be a directed simple graph (i.e., does not have self-loops or multi-edges) with and . Let represent the indegree of a vertex . Motivated by cycle languages, we define the language as follows :

= .

is represented as where each and is in encoded as binary strings. The meaning of is that there is a directed edge from to . We may assume that circuits computing will have binary inputs in a prespecified order.

Exercise : .

Lemma : If a CNF or a DNF computes , then

• each term includes at least variables, and
• there are at least terms.

Hence there is no circuit of depth two for .

Proof : We will prove this lemma for CNFs. The proof for DNFs is similar. Let be a CNF circuit computing .

• Assume that has some term that depends on less than variables. Then when all inputs to are 0, outputs 0 and hence outputs 0. Consider the graph consisting of a cycle on vertices (say ) and an isolated vertex . Note that . Let be the graph obtained by adding the edge to . Now for . If does not depend on all variables of the form then outputs 0 for some , which is a contradiction.
• Consider the graph consisting of a cycle on vertices (these are the vertices from except ) and an isolated vertex . must output zero on for . outputs 0 only when one of the terms (OR gates) outputs zero. But each OR gate outputs 0 on exactly one assignment of the input variables, Hence, must have at least terms.

Restriction : Let be a circuit computing . Setting an input of to 0 (resp. 1) corresponds to deleting (resp. contracting) the corresponding edge from the input graph .

Observation : If some of the inputs of are restricted to 0 or 1, the resulting circuit still computes , albeit on a smaller graph.

Theorem : .

Proof : We assume that there is an circuit (say of some constant depth ) computing and derive a contradiction. Using the random restriction technique of [FSS'81] we squash down to depth while still computing on many variables. This squashing still preserves the constant fanin of AND gates. We repeat this method times to obtain an circuit of depth 2 with constant AND fanin, which contradicts the previous lemma.

Corollary : .

References :

• [FSS'81] Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In FOCS, pages 260–270, 1981.

Relativization Barrier

I am back in Atlanta after attending an awesome Barriers Workshop. This workshop is mainly about the barriers in resolving P vs NP problem and possible techniques to overcome these barriers. It is a five day workshop covering circuits lower bounds, arithmetic circuits, proof complexity, learning theory and pseudo-random generators. I enjoyed every talk and panel discussions. Everybody seemed very positive that .

Todays post is a quick introduction to Relativization Barrier. I will write separate posts about natural proofs and algebrization barriers soon. Relativization Barrier is one of the first barriers we learn in an introductory graduate level complexity course.

In relativized world we grant the Turing machine M the access to an oracle that could compute some function A in a single time step. Such a machine, called oracle TM, computes relative to A, is represented by . Oracle TMs are used in Turing-reducibility, a generalization of mapping-reducibility.

The method of diagonalization relativizes i.e.,  any separation result in the real world, proved using diagonalization, extends to the relativized world. Baker, Gill and Solovay [BGS'75] showed that there exists oracles A and B for which and are provably different and and are provably equal. That is P vs NP has different answers in different worlds !! Hence techniques such as diagonalization, cannot be used to resolve P versus NP.

Theorem : An oracle A exists such that . An oracle B exists such that .

Let B be any PSPACE-complete problem. We have . The first and third containments are trivial and the second containment follows from Savitch’s theorem. Hence . Constructing A is a non-trivial task. Look at Sipser’s book (page 350) for details.

Therefore any solution to the P versus NP problem will require non-relativizing techniques i.e., techniques that exploit properties of computation that are specific to the real world i.e., techniques that analyze the computations not just simulate them.

References :

• [BGS'75] T. Baker, J. Gill, and R. Solovay : Relativizations of the P=?NP question. SIAM J. Comput., 4:431–442, 1975.

Baker, Gill and Solovay [BGS'75] showed that techniques such as diagonalization,

cannot be used to resolve P versus NP. Such techniques would work in [relativized]

world, where both P and NP machines could compute some function

f in a single time step.

However, there are some relativized

worlds where P = NP, and other relativized worlds

where P != NP. Therefore any solution to the P versus NP

problem will require non-relativizing techniques i.e., techniques

that exploit properties of computation that are specific to

the real world.

Linear Complementarity Problem

Linear Complementarity Problem (LCP) is a generalization of Linear Programming and a special case of quadratic programming. I stumbled upon LCP theory due to my interest in complexity problems in game theory and PPAD-completeness. As we will see these concepts are very closely related.

Let M be a square matrix and q an n dimensional vector. Let LCP(q,M) be the following problem : Find two vectors w and z satisfying

LCP(q,M) consists of linear constraints and complementary conditions. Since the complementary conditions is equivalent to . There is an obvious exponential time algorithm to solve LCP. For every i, set either or and solve the resulting system of linear equations. If one of these linear systems has a solution then the corresponding LCP is solvable. Deciding if a given LCP has a solution is NP-complete. The following exercise shows that LCP is a generalization of LP.

Exercise : Every LP can solved by solving a corresponding LCP, representing the complementary slackness of the LP.

LCP can also be expressed in the following equivalent form :

Lemke’s algorithm is a “path-following” algorithm (similar to simplex algorithm) to solve LCP. Unfortunately, Lemke’s algorithm can sometimes fail to produce a solution even if one exists !! There are many special instances of LCP on which Lemke’s algorithm always produces a solution or a certificate that no solution exists.

As mentioned earlier, solving an LCP is NP-complete. What about special cases ? i.e., when the input matrix M is special.

• If M is a Positive Semi-Definite matrix, then LCP(q,M) can be solved in polynomial time. In fact, every LCP with a PSD matrix is a convex quadratic program and every convex quadratic program can be expressed as an LCP with a PSD matrix.
• If M is a Z-matrix, Chandrasekaran’s algorithm solves LCP(q,M) in polynomial time [Chandrasekaran'70].
• If M is a triangular P-matrix, LCP(q,M) can be solved in polynomial time by using a back substitution method.
• If M is a P-matrix, LCP(q,M) has a unique solution for every q.

Following is one of the coolest applications of LCP.

Exercise : Finding a Nash Equilibrium in a bimatrix game can be expressed as an LCP.

Lemke-Howson’s algorithm [Lemke,Howson'64] to solve a bimatrix game is known to take exponential number of steps in the worst case [Savani, vonStengel'04]. It is also known that finding Nash equilibrium in a bimatrix game is PPAD-complete [Chen,Deng'09].

Open Problems :

• The complexity of solving LCP with a P-matrix (P-LCP) is open for more than two decades !! P-LCP is known to be in PPAD [Papadimitriou'94]. Note that recognizing Z-matrices and PSD-matrices can be done in polynomial-time but recognizing P-matrices is coNP-complete [Coxson'94].
• Are there other interesting classes of matrices M for which LCP(q,M) is solvable in polynomial time ?
• Savani and von Stengel’s instance of bimatrix game has “full support mixed equilibrium”, which can easily solved using linear programming techniques. It is an open problem to construct an instance of a bimatrix game that does not have full-support mixed equilibrium and the Lemke-Howson algorithm takes exponential number of steps on this instance.
  Savani and von Stengel’s instance of bimatrix game has full support.
  It is open problem to construct an instance of bimatrix game that
  does not have full-support mixed equilibrium and the Lemke-Howson algorithm
  takes exponential number of steps.

References :

• [Chandrasekaran'70] R. Chandrasekaran. “A Special Case of the Complementary Pivot Problem“, Opsearch, 7(1970) 263 268.
• [Coxson'94] G. E. Coxson. The P-matrix problem is co-NP-complete. Math. Programming, 64(2):173–178, 1994.
• [Chen,Deng'09] Xi Chen, Xiaotie Deng, Shang-Hua Teng: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3): (2009)
• [Savani, vonStengel'04] Rahul Savani, Bernhard von Stengel: Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. FOCS 2004: 258-267
• [Lemke,Howson'64] Lemke, C. E. and J. T. Howson, Jr. (1964), Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics 12, 413–423.
• [Papadimitriou'94] 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)