Part II : Hardness of Graph Isomorphism of Bounded TreeWidth Graphs

I did not expect that several researchers are interested in the theorems I announced in my previous post. Here is the proof of one of the theorems :

Theorem : Graph Isomorphism (GI) of graphs of treewidth >= 4 is -hard.

If you want to know the consequences of , read this question posted by Aaron Sterling.

Proof of Theorem : As mentioned in an earlier post, the best known hardness of GI is given by Jacobo Toran. He proved that GI is hard for . Lets focus on his proof of  hardness. He used the following gadget (also used in an earlier paper by Cai, Furer, Immerman) to simulate a parity gate. Let’s call this gadget . Toran proved the following lemma.

Lemma (Toran’2000) : For any , there is a unique automorphism in  mapping to and  to for . This automorphism maps  to

Given any  circuit we first transform the circuit into a tree (by arranging the fan-out connections in a tree-like fashion) and replace each parity gate by the gadget  and obtain a graph . Toran proved that certain automorphisms of graph simulate the precise behavior of the  circuit. See his paper (lemma 3.2 and theorem 3.3) for more details of this reduction. We will now prove the following theorem.

Theorem : Tree width of is four.

Part 1 : Tree-width of  is at most four. To prove this, we use the concept of elimination order. We repeat the following procedure on . Pick a vertex of degree at most 4, delete it and add a clique on its neighbors. This process always terminates on  (resulting in an empty graph), if we choose such vertices in a bottom-up fashion. This proves that is a partial 4-tree and hence its treewidth is at most 4.

Part 2 : Tree-width of  is at least four. To prove this, we will exhibit one of the forbidden minors of graphs of treewidth at most three. Consider the  circuit consisting of only three parity gates (say A, B, C). The outputs of A and B are the inputs to C. Convert this circuit into a graph by replacing the each gate A, B and C with the parity gadget . By contracting and deleting some edges of , we can show that the following graph is a minor of .

Now lets look at the set of all forbidden minors of graphs of tree width at most three. They are shown in the following figure. This figure is take from Wikipedia article, it is drawn by David Eppstein.

Now you can see that the minor we obtained from is isomorphic to one the above forbidden minors. Hence tree width of is at least four.

To prove -hardness for treewidth t >=5, we simply add an isolated clique to the graph . I proved the following stronger theorem for larger values of treewidth.

 Theorem : Graph Isomorphism of graphs of treewidth = t is hard. Here t >= 4 and f(t) is a linear function of t.

The proof of the above theorem is based on a new structural theorem about forbidden minors of graphs with larger treewidth. More details later in my paper.

Update : The above reduction works for parity formulas. I will add more details in the follow-up post.

Hardness of Graph Isomorphism of Bounded TreeWidth Graphs

If you read my earlier post you know that I am obsessed with the following open problem :

Is there a logspace algorithm for Graph Isomorphism of bounded treewidth graphs ?

This problem is at the intersection of three of my research interests (graph isomorphism, tree width and space-bounded computation. See my earlier posts (here, here, here, here). Finally, this open problem is put to rest. I proved the following theorem :

Theorem : Graph Isomorphism of graphs of treewidth >= 4 is -hard.

As mentioned in my previous post Graph Isomorphism of graphs of treewidth <= 3 is known to be in Logspace. Hence the above theorem settles the open question in the negative (unless ). In fact, I proved better hardness results for larger values of tree width.

I proved these theorems three weeks back and still trying to motivate myself to write these results in Latex. I usually take my own sweet time to write my papers, especially the single-author ones. There are three stages of working on an open problem :

1. Reading lots of related papers. (I enjoy this process)
2. Finding new insights, proving new theorems and solving an open problem (I enjoy this more than stage 1)
3. Converting the hand-written proofs into latex. (This is the most boring part of research) I hate this stage. It is very time-consuming with zero fun factor. Stage 1 and stage 2 are roller-coaster rides. Stage 3 is like a power cut.

I don’t know how many days I will spend (a.k.a waste) typing my proofs. Meanwhile, following is a proof by picture I usually take photos of my hand-written proofs. These are the actual fun memories, not the final publications.

Are there other people who feel that writing is the most boring part of research, (or) is it just me ? How do you motivate yourself to latex your proofs ?

Update (Nov 16 7:00pm EST) : I added a proof of the above theorem in my follow-up post.

Complexity of Tessel

One of my hobbies (I developed during my PhD) is designing boardgames. I designed three boardgames so far, one of which is Tessel, a word-building game based on graph theory. I am glad that Tessel is getting good feedback especially from schools and families. One of the most time-consuming part of Tessel’s design is deciding what values to assign to the letters and deciding which pairs of letters to use in the tiles. The pairs of letters are carefully chosen based on computer simulations of frequency of letters in english words and their “relative” importance. The pairs are chosen so as to give fair share to both vocabulary skills and optimization skills.

Today’s post is about a nice theoretical problem arising from this game.

Before you read further, please read the rules of Tessel. Henceforth I will assume that you understood the rules and goal of this game.

I guess you observed that the tiles are being placed on the edges of a planar graph. Tessel uses a special planar graph that has cycles of length 3,4,5 and 6. In general, this game can be played on any planar graph. I am planning to design another board using Cairo tessellation. Anyways, here is a theoretical problem :

Let S be a set of finite alphabets. You are given two different words (using alphabets from S) of length l1 and l2. Construct a planar graph G and label each edge with two alphabets, such that there are two walks in G that correspond to the given two words. (Read the rules of tessel  and look at these examples to understand this correspondence). Your goal is to construct G with minimum number of vertices (or minimum number of edges).

In general you can ask the above question given k different words. What is the complexity of this problem ? I don’t know. I haven’t given it a deep thought. These days whatever I do for fun (to take my mind off open problems), ends up in another open problem

Graph Isomorphism, Tree Width, Path Width and LogSpace

Every once in a while, I can’t help thinking about “the complexity of graph isomorphism for bounded treewidth graphs“. Today has been one of those days again. See my earlier post to get the context.

Theorem ([Das, Toran and Wagner'10]) : Graph isomorphism of bounded treewidth graphs is in LogCFL.

The proof of the above theorem is as follows

1. Graph isomorphism of bounded tree-distance width graphs is in L.
2. Given two graphs and their tree decompositions, computing the isomorphism respecting these tree decompositions is reducible to (1).
3. Given tree decomposition of only one graph, we can guess the tree decomposition of the other and guess the isomorphism (respecting the tree bags) and verify them using a non-deterministic auxiliary pushdown automata (a.k.a LogCFL).
4. Since tree decomposition of a graph can be computed in LogCFL, the above theorem follows.

One of the bottlenecks, finding a tree decomposition of bounded treewidth graphs in logspace, is resolved by [Elberfeld, Jakoby and Tantau'10]. The following seems to be another major bottleneck.

Given a graph and a decomposition , how fast can we verify that is a valid tree decomposition of ? The upper bound of LogDCFL (the deterministic version of LogCFL) is clear from the above mentioned results. Can this verification be done in logspace ?

The answer is frustratingly unknown. An even more frustrating realization I had today is that “it is not clear how to beat the LogDCFL upper bound for the more restricted path decomposition“. Even though the underlying tree in a path decomposition is just a path, verifying the connectivity conditions of a path decomposition does seem to require recursion. It is not clear how to avoid recursion.

I thought that logspace upper bound is possible. Now I am much less confident about logspace upper bound. I cannot waste more time on this.

The truth is “this is a cute problem“. I need to do something to take my mind off this problem and move on. Easy enough, except I need an idea.

Update (Oct 12 2011) : Noticed that verification of path decompositions is easy.

FOCS 2011 Accepted Papers (with pdf files)

FOCS 2011 accepted paper list with abstracts is here. Following are PDF pointers to online versions.

1. The Grothendieck constant is strictly smaller than Krivine’s bound [arXiv]

Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor

2. The minimum k-way cut of bounded size is fixed-parameter tractable [arXiv]

Mikkel Thorup and Ken-ichi Kawarabayashi

3. Randomness buys depth for approximate counting [ECCC]

Emanuele Viola

4. Local Distributed Decision [arXiv]

Pierre Fraigniaud and Amos Korman and David Peleg

5. A Small PRG for Polynomial Threshold Functions of Gaussians [arXiv]

Daniel M. Kane

6. Evolution with Recombination [pdf]

Varun Kanade

7. Extractors for circuit sources [pdf]

Emanuele Viola

8. The Second-Belief Mechanism. [pdf]

Jing Chen and Silvio Micali

9. New extension of the Weil bound for character sums with applications to coding [ECCC]

Tali Kaufman and Shachar Lovett

10. A Two Prover One Round Game with Strong Soundness

Subhash Khot and Muli Safra

11. Optimal testing of multivariate polynomials over small prime fields [ECCC]

Elad Haramaty and Amir Shpilka and Madhu Sudan

12. Fully dynamic maximal matching in O(log n) update time [arXiv]

Surender Baswana and Manoj Gupta and Sandeep Sen

13. Optimal bounds for quantum bit commitment [arXiv]

André Chailloux and Iordanis Kerenidis

14. SHARP MIXING TIME BOUNDS FOR SAMPLING RANDOM SURFACES

PIETRO CAPUTO AND FABIO MARTINELLI AND FABIO LUCIO TONINELLI

15. Solving connectivity problems parameterized by treewidth in single exponential time [arXiv]

Marek Cygan and Jesper Nederlof and Marcin Pilipczuk and Micha3 Pilipczuk and Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk

16. How to Play Unique Games Against a Semi-Random Adversary [arXiv]

Alexandra Kolla and Konstantin Makarychev and Yury Makarychev

17. Near-Optimal Column-Based Matrix Reconstruction [arXiv]

Christos Boutsidis and Petros Drineas and Malik Magdon-Ismail

18. Tight lower bounds for 2-query LCCs over finite fields [ECCC]

Arnab Bhattacharyya and Zeev Dvir and Shubhangi Saraf and Amir Shpilka

19. Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications [arXiv]

Christian Wulff-Nilsen

20. 3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General [arXiv]

Timon Hertli

21. On Range Searching in the Group Model and Combinatorial Discrepancy [pdf]

Kasper Green Larsen

22. Coin Flipping with Constant Bias Implies One-Way Functions

Iftach Haitner and Eran Omri

23. The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke- Howson Solutions. [arXiv]

Paul W. Goldberg and Christos H. Papadimitriou and Rahul Savani

24. Information Equals Amortized Communication [arXiv]

Mark Braverman and Anup Rao

25. Graph Connectivities, Network Coding, and Expander Graphs

Ho Yee Cheung and Lap Chi Lau and Kai Man Leung

26. Limitations of Randomized Mechanisms for Combinatorial Auctions

Shaddin Dughmi and Jan Vondrak

27. How to Store a Secret on Continually Leaky Devices [pdf]

Yevgeniy Dodis and Allison Lewko and Brent Waters and Daniel Wichs

28. A Polylogarithmic-Competitive Algorithm for the k-Server Problem

Nikhil Bansal and Niv Buchbinder and Aleksander Madry and Seffi Naor

29. Minimum Weight Cycles and Triangles: Equivalences and Algorithms [arXiv]

Liam Roditty and Virginia Vassilevska Williams

30. Streaming Algorithms via Precision Sampling [arXiv]

Alexandr Andoni and Robert Krauthgamer and Krzysztof Onak

31. A Parallel Approximation Algorithm for Positive Semidefinite Programming [arXiv]

Rahul Jain and Penghui Yao

32. Planar Graphs: Random Walks and Bipartiteness Testing

Artur Czumaj and Morteza Monemizadeh and Krzysztof Onak and Christian Sohler

33. Pseudorandomness for read-once formulas

Andrej Bogdanov and Periklis Papakonstantinou and Andrew Wan

34. Approximating Graphic TSP by Matchings [arXiv]

Tobias Moemke and Ola Svensson

35. Efficient Distributed Medium Access [arXiv]

Devavrat Shah and Jinwoo Shin and Prasad Tetali

36. Near Linear Lower Bound for Dimension Reduction in L1 [pdf]

Alexandr Andoni and Moses S. Charikar and Ofer Neiman and Huy L. Nguyen

37. Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2

Lo\”ic S\’eguin-Charbonneau and F. Bruce Shepherd

38. Min-Max Graph Partitioning and Small-Set Expansion

Nikhil Bansal and Uriel Feige and Robert Krauthgamer and Konstantin Makarychev and Viswanath Nagarajan and Joseph (Seffi) Naor and Roy Schwartz

39. An FPTAS for #Knapsack and Related Counting Problems

Parikshit Gopalan and Adam Klivans and Raghu Meka and Daniel Stefankovic and Santosh Vempala and Eric Vigoda

40. Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets [arXiv]

Ricardo Restrepo and Jinwoo Shin and Prasad Tetali and Eric Vigoda and Linji Yang

41. Balls and Bins: Smaller Hash Families and Faster Evaluation [ECCC]

L. Elisa Celis and Omer Reingold and Gil Segev and Udi Wieder

42. Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time [arXiv]

Glencora Borradaile and Philip N. Klein and Shay Mozes and Yahav Nussbaum and Christian Wulff-Nilsen

43. Quantum query complexity of state conversion

Troy Lee and Rajat Mittal and Ben W. Reichardt and Robert Spalek and Mario Szegedy

44. A constant factor approximation algorithm for unsplittable flow on paths [arXiv]

Paul Bonsma and Jens Schulz and Andreas Wiese

45. The Graph Minor Algorithm with Parity Conditions

Ken-ichi Kawarabayashi and Bruce Reed and Paul Wollan

46. Mutual Exclusion with O(log2 log n) Amortized Work

Michael A. Bender and Seth Gilbert

47. How Bad is Forming Your Own Opinion? [pdf]

David Bindel and Jon Kleinberg and Sigal Oren

48. The Complexity of Renaming [HTML]

Dan Alistarh and James Aspnes and Seth Gilbert and Rachid Guerraoui

49. On the Power of Adaptivity in Sparse Recovery

Piotr Indyk and Eric Price and David Woodruff

50. Enumerative Lattice Algorithms in any Norm via M-ellipsoid Coverings [arXiv]

Daniel Dadush and Chris Peikert and Santosh Vempala

51. Efficient and Explicit Coding for Interactive Communication

Ran Gelles and Ankur Moitra and Amit Sahai

52. Dispersers for affine sources with sub-polynomial entropy

Ronen Shaltiel

53. Approximation Algorithms for Correlated Knaspacks and Non-Martingale Bandits [pdf]

Anupam Gupta and Ravishankar Krishnaswamy and Marco Molinaro and R. Ravi

54. Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives [arXiv]

Venkatesan Guruswami and Ali Kemal Sinop

55. A Unified Continuous Greedy Algorithm for Submodular Maximization

Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz

56. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers [arXiv]

Saeed Alaei

57.  Extreme-Value Theorems for Optimal Multidimensional Pricing [arXiv]

Yang Cai and Constantinos Daskalakis

58.  Approximation Algorithms for Submodular Multiway Partition [arXiv]

Chandra Chekuri and Alina Ene

59. Delays and the Capacity of Continuous-time Channels [arXiv]

Sanjeev Khanna and Madhu Sudan

60. Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits [ePrint]

Craig Gentry and Shai Halevi

61. A Randomized Rounding Approach to the Traveling Salesman Problem [pdf]

Shayan Oveis Gharan and Amin Saberi and Mohit Singh

62.  Algorithms for the Generalized Sorting Problem

Zhiyi Huang and Sampath Kannan and Sanjeev Khanna

63. Privacy Amplification and Non-Malleable Extractors Via Character Sums [arXiv]

Xin Li and Trevor D. Wooley and David Zuckerman

64. A nearly mlogn time solver for SDD linear systems

Ioannis Koutis and Gary L. Miller and Richard Peng

65. Which Networks Are Least Susceptible to Cascading Failures? [pdf]

Lawrence Blume and David Easley and Jon Kleinberg and Robert Kleinberg and Eva Tardos

66. Online Node-weighted Steiner Tree and Related Problems

Joseph (Seffi) Naor and Debmalya Panigrahi and Mohit Singh

67. Welfare and Profit Maximization with Production Costs

Avrim Blum and Anupam Gupta and Yishay Mansour and Ankit Sharma

68. On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems [arXiv]

Dorit Aharonov and Lior Eldar

69. Efficient Fully Homomorphic Encryption from (Standard) LWE [ePrint]

Zvika Brakerski and Vinod Vaikuntanathan

70. Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy [ECCC]

Madhav Jha and Sofya Raskhodnikova

71. Lexicographic Products and the Power of Non-Linear Network Coding

Anna Blasiak and Robert Kleinberg and Eyal Lubetzky

72. Efficient computation of approximate pure Nash equilibria in congestion games [arXiv]

Ioannis Caragiannis and Angelo Fanelli and Nick Gravin and Alexander Skopalik

73.  How to Garble Arithmetic Circuits

Benny Applebaum and Yuval Ishai and Eyal Kushilevitz

74. Rounding Semidefinite Programming Hierarchies via Global Correlation [arXiv]

Boaz Barak and Prasad Raghavendra and David Steurer

75. Efficient Reconstruction of Random Multilinear Formulas

Ankit Gupta and Neeraj Kayal and Satya Lokam

76. Markov Layout

Flavio Chierichetti and Ravi Kumar and Prabhakar Raghavan

77. (1+eps)-Approximate Sparse Recovery

Eric Price and David P. Woodruff

78. Quadratic Goldreich-Levin Theorems [arXiv]

Madhur Tulsiani and Julia Wolf

79. Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems [arXiv]

Jian Li and Amol Deshpande

80. Stateless Cryptographic Protocols

Vipul Goyal and Hemanta K. Maji

81. Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones

Michael Elkin and Shay Solomon

82. An algebraic proof of a robust social choice impossibility theorem

Dvir Falik and Ehud Friedgut

83. The Power of Linear Estimators [pdf]

Gregory Valiant and Paul Valiant

84. The Randomness Complexity of Parallel Repetition

Kai-Min Chung and Rafael Pass

85. The Complexity of Quantum States – a combinatorial approach

Dorit Aharonov and Itai Arad and Zeph Landau and Umesh Vazirani

Kriesell’s Conjecture

Today’s short post is about Kriesell’s conjecture. In my first year of PhD I enjoyed reading several papers related to this cute conjecture.

Nash-Williams [N'61] and Tutte [Tutte'61] independently proved that a graph has edge-disjoint spanning trees if and only if for every partition of into non-empty classes, where denotes the number of edges connecting distinct classes of . One interesting corollary of this result is the following :

Theorem : Every -edge-connected graph has edge-disjoint spanning trees.

Let be an undirected multigraph and . An is a tree of that contains every vertex in . An is a subset of edges whose removal disconnects some vertices in . A graph is if every has at least edges. Kriesell conjectured the following generalization of the above theorem.

Kriesell’s conjecture : If is , then has edge-disjoint .

The first breakthrough towards proving Kriesell’s conjecture was by Lau. He proved that if G is -edge-connected in  then it has  edge-disjoint Steiner trees. Recently, West and Wu [pdf] proved that it suffices for to be -edge-connected in .

Open Problems

1. Obvious open problem is to prove or disprove Kriesell’s conjecture.
2. There a several related open problems about S-connectors in West-Wu’s paper.

References :

• [Tutte'61] W.T.Tutte : On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 36 (1961), 221–230.
• [N'61] C.St.J.A.Nash-Williams : Edge disjoint spanning trees of finite graphs, J. London Math. Soc. 36 (1961), 445–450.
• [Lau'07] L. C. Lau : An approximate max-Steiner-tree-packing min-Steiner-cut theorem. Combinatorica 27 (2007), 71–90

Graph Isomorphism and Bounded Tree Width

If you read my earlier post, you known that I am fan of treewidth. Who isn’t !! The complexity of Graph Isomorphism (earlier post) is one of the long-standing open problem. Intersecting these two with one of my research interests (space-bounded computation) we get the following open problem :

Open Problem : What is the complexity of graph isomorphism for graphs with bounded treewidth ?

Graphs with treewidth at most are also called partial -trees. In 1992 Lindell proved that trees (graphs with treewidth=1) can be canonized in logspace [Lindel'92]. What about canonization for ? Recently Datta et. al [DLNTW'09] proved that the canonization of planar graph is logspace-complete. The following simple exercise shows that partial 2-trees are planar graphs. Hence the result of [DLNTW'09] implies that partial 2-trees can be canonized in logspace.

Exercise : Every partial 2-tree is planar.

In fact, canonization of partial 2-trees is settled earlier by [ADK'08]. What about ? Partial 3-trees may not be planar. An example is itself. The tree width of is three. I wanted to work on the case of and realized the following simple fact.

Exercise : Partial 3-trees are -free.

In a follow-up paper to [DLNTW'09], Datta et al [DNTW'10] proved that canonization of -free and -free graphs is in Log-space. Hence we get the following corollary :

Corollary : Partial 3-trees can be canonized in log-space.

Since the above result is not explicitly mentioned in any papers, I wanted to make it clear in this post. Hence the open problem is for . LogCFL is the best known upper bound for graph isomorphism of partial k-trees [DTW'10]. One of the bottleneck, finding a tree decomposition of partial k-tree in logspace, is resolved recently [EJT'10]. The above mentioned papers make use of a decomposition of the input graph into two- or three-connected subgraphs, constructing an appropriate tree of these subgraphs, using the known structural properties of two- and three-connected graphs to canonize these subgraphs and using Lindell’s result to canonize the entire graph. Unfortunately no clean characterization exists for graphs with connectivity at least four. Many long-standing open problems in graph theory are trivial for 2- and 3- connected graphs and open for higher connectivity. A clean characterization of 4-connected graphs seems to be a major bottleneck in improving the space complexity of canonization of partial 4-trees. I am lost

Open Problems

• Is graph isomorphism of partial k-trees (for ) in logspace ?
• Is canonization of partial k-trees in LogCFL ? The paper of [DTW'10] solves isomorphism only.

References :

• [Lindell'92] Steven Lindell: A Logspace Algorithm for Tree Canonization STOC 1992: pages 400-404
• [DLNTW'09] 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
• [DNTW'10] Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Graph Isomorphism for K{3, 3}-free and K5-free graphs is in Log-space. Electronic Colloquium on Computational Complexity (ECCC) 17: 50 (2010)
• [ADK'08] Vikraman Arvind, Bireswar Das, Johannes Köbler: A Logspace Algorithm for Partial 2-Tree Canonization. CSR 2008: 40-51
• [DTW'10] Bireswar Das, Jacobo Torán, Fabian Wagner: Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. STACS 2010: 227-238
• [EJT'10] Michael Elberfeld, Andreas Jakoby, Till Tantau: Logspace Versions of the Theorems of Bodlaender and Courcelle. FOCS 2010: 143-152

STOC 2011 Accepted Papers (with pdf files)

1. Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication Bo’az Klartag and Oded Regev [arXiv]
2. Multicut is FPT Nicolas Bousquet and Jean Daligault and Stephan Thomasse [arXiv]
3. Pareto Optimal Solutions for Smoothed Analysts Ankur Moitra and Ryan O’Donnell [arXiv]
4. An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance Amit Chakrabarti and Oded Regev [arXiv]
5. Constant Round Non-Malleable Protocols using One Way Functions Vipul Goyal [ePrint]
6. Fixed-parameter tractability of multicut parameterized by the size of the cutset Daniel Marx and Igor Razgon [arXiv]
7. Secure Computation with Information Leaking to an Adversary Miklos Ajtai
8. Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP Yuichi Yoshida [ECCC]
9. Near-Optimal Private Approximation Protocols via a Black-Box Transformation David P. Woodruff
10. Cover times, blanket times, and majorizing measures Jian Ding and James R. Lee and Yuval Peres [arXiv]
11. Breaking the $k^2$ barrier for explicit RIP matrices Jean Bourgain, S. J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova [pdf]
12. Analyzing Network Coding Gossip Made Easy Bernhard Haeupler [arXiv]
13. Deterministic Construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$ Zohar S. Karnin [ECCC]
14. Schaefer’s Theorem for Graphs Manuel Bodirsky and Michael Pinsker [arXiv]
15. Tight Bounds for Parallel Randomized Load Balancing Christoph Lenzen and Roger Wattenhofer [pdf]
16. Pseudorandom Generators for Group Products Michal Koucky and Prajakta Nimbhorkar and Pavel Pudlak [pdf]
17. Contraction Decomposition in H-Minor-Free Graphs and Algorithmic Applications Erik Demaine and Mohammad Hajiaghayi and Ken-ichi Kawarabayashi
18. Correlation testing for affine invariant properties on $\F_p^n$ in the high error regime Hamed Hatami and Shachar Lovett
19. Every Property of Hyperfinite Graphs is Testable Ilan Newman and Christian Sohler
20. Fast Moment Estimation in Data Streams in Optimal Space Daniel M. Kane and Jelani Nelson and Ely Porat and David P. Woodruff [arXiv]
21. An Algorithm for the Graph Crossing Number Problem Julia Chuzhoy [arXiv]
22. From Affine to Two-Source Extractors via Approximate Duality Eli Ben-Sasson, Noga Zewi [ECCC]
23. On Optimal Single-Item Auctions Christos Papadimitriou and George Pierrakos [arXiv]
24. Directed Spanners via Flow-Based Linear Programs Michael Dinitz and Robert Krauthgamer [arXiv]
25. Mechanism design with uncertain inputs (to err is human, to forgive divine) Uriel Feige and Moshe Tennenholtz
26. Santa Claus Schedules Jobs on Unrelated Machines Ola Svensson [arXiv]
27. Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes Boaz Barak and Zeev Dvir and Avi Wigderson and Amir Yehudayoff [ECCC]
28. A simpler algorithm and shorter proof for the graph minor decomposition Ken-ichi Kawarabayashi and Paul Wollan
29. Finding topological subgraphs is fixed-parameter tractable Martin Grohe and Ken-ichi Kawarabayashi and Daniel Marx and Paul Wollan [arXiv]
30. Constant-Round Non-Malleable Commitments from Any One-Way Function Huijia Lin, Rafael Pass [ePrint]
31. Privacy-preserving Statistical Estimation with Optimal Convergence Rates Adam Smith
32. Learning Submodular Functions Maria Florina Balcan and Nicholas J. A. Harvey [arXiv]
33. Pseudorandom Generators for Combinatorial Shapes Parikshit Gopalan and Raghu Meka and Omer Reingold and David Zuckerman [ECCC]
34. NP-Hardness of Approximately Solving Linear Equations Over Reals Subhash Khot and Dana Moshkovitz [ECCC]
35. Towards Coding for Maximum Errors in Interactive Communication Mark Braverman and Anup Rao [pdf]
36. K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance Piotr Indyk and Eric Price
37. Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs Paul Christiano and Jonathan A. Kelner and Aleksander Madry and Daniel A. Spielman and Shang-Hua Teng [arXiv]
38. A General Framework for Graph Sparsification Wai Shing Fung and Ramesh Hariharan and Nicholas J. A. Harvey and Debmalya Panigrahi
39. Breaking O(n^{1/2})-approximation algorithms for the edge-disjoint paths problem Ken-ichi Kawarabayashi and Yusuke Kobayashi
40. Linearizable Implementations Do Not Suffice for Randomized Distributed Computation Wojciech Golab and Lisa Higham and Philipp Woelfel
41. Online Bipartite Matching with Unknown Distributions Chinmay Karande and Aranyak Mehta and Pushkar Tripathi
42. Near-optimal distortion bounds for embedding doubling spaces into $L_1$ James R. Lee and Anastasios Sidiropoulos
43. Mechanisms for (Mis)allocating Scientific Credit Jon Kleinberg and Sigal Oren
44. Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes Chandra Chekuri and Jan Vondrak and Rico Zenklusen
45. Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen
46. An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations Shahar Dobzinski [arXiv]
47. Geometric Complexity Theory and Tensor Rank Peter Buergisser and Christian Ikenmeyer [arXiv]
48. A quasipolynomial-time algorithm for the quantum separability problem Fernando Brandao and Matthias Christandl and Jon Yard
49. A Full Derandomization of Schoening’s k-SAT Algorithm Robin A. Moser and Dominik Scheder [arXiv]
50. Rank-1 Bimatrix Games: A Homeomorphism and a Polynomial Time Algorithm Bharat Adsul and Jugal Garg and Ruta Mehta and Milind Sohoni [arXiv]
51. How to Leak on Key Updates Allison Lewko and Mark Lewko and Brent Waters
52. Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions Craig Gentry and Daniel Wichs [ePrint]
53. Social Networks Spread Rumors in Sublogarithmic Time Benjamin Doerr and Mahmoud Fouz and Tobias Friedrich
54. High-rate codes with sublinear-time decoding Swastik Kopparty and Shubhangi Saraf and Sergey Yekhanin [ECCC]
55. The Computational Complexity of Linear Optics Scott Aaronson and Alex Arkhipov [arXiv]
56. Dueling algorithms Nicole Immorlica and Adam Tauman Kalai and Brendan Lucier and Ankur Moitra and Andrew Postlewaite and Moshe Tennenholtz [arXiv]
57. Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn’t matter Nitin Saxena and C. Seshadhri [ECCC]
58. Don’t Rush into a Union: Take Time to Find Your Roots Mihai Patrascu and Mikkel Thorup
59. From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions for Submodular Bidders Shaddin Dughmi and Tim Roughgarden and Qiqi Yan
60. Privately Releasing Conjunctions and the Statistical Query Barrier Anupam Gupta and Moritz Hardt and Aaron Roth and Jonathan Ullman [arXiv]
61. Optimal Path Search in Small Worlds: Dimension Matters George Giakkoupis and Nicolas Schabanel
62. Distributed Verification and Hardness of Distributed Approximation Atish Das Sarma and Stephan Holzer and Liah Kor and Amos Korman and Danupon Nanongkai and Gopal Pandurangan and David Peleg and Roger Wattenhofer [arXiv]
63. Parallel Repetition of Entangled Games Julia Kempe and Thomas Vidick [arXiv]
64. Subspace Embeddings for the L_1-norm with Applications Christian Sohler and David Woodruff
65. A Unified Framework for Approximating and Clustering Data Dan Feldman and Michael Langberg
66. The Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited Thomas Holenstein and Robin Kunzler and Stefano Tessaro [arXiv]
67. Limits of Provable Security From Standard Assumptions Rafael Pass
68. Optimal Auctions with Correlated Bidders are Easy Shahar Dobzinski and Hu Fu and Robert Kleinberg [arXiv]
69. Strong Direct Product Theorems for Quantum Communication and Query Complexity Alexander A. Sherstov [arXiv]
70. Inner Product Spaces for MinSum Coordination Mechanisms Richard Cole and Jose R. Correa and Vasilis Gkatzelis and Vahab Mirrokni and Neil Olver [arXiv]
71. The Topology of Wireless Communication Erez Kantor and Zvi Lotker and Merav Parter and David Peleg
72. An LLL-Reduction Algorithm with Quasi-linear Time Complexity Andrew Novocin and Damien Stehle and Gilles Villard [pdf]
73. From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking Omar Fawzi and Patrick Hayden and Pranab Sen [arXiv]
74. The Power of Simple Tabulation Hashing Mihai Patrascu and Mikkel Thorup [arXiv]
75. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm Oliver Friedmann and Thomas Dueholm Hansen and Uri Zwick [pdf]
76. Almost Settling the Hardness of Noncommutative Determinant Steve Chien and Prahladh Harsha and Alistair Sinclair and Srikanth Srinivasan [arXiv]
77. Approximate Polytope Membership Queries Sunil Arya and Guilherme D. da Fonseca and David M. Mount [pdf]
78. Exact Algorithms for Solving Stochastic Games Kristoffer Arnsfelt Hansen and Michal Koucky and Niels Lauritzen and Peter Bro Miltersen and Elias P. Tsigaridas
79. Online Bipartite Matching with Random Arrivals: A Strongly Factor Revealing LP Approach Mohammad Mahdian and Qiqi Yan
80. Estimating the unseen: an n/log(n)-sample estimator for entropy, support size, and other distribution properties, with a proof of optimality via two new central limit theorems Gregory Valiant and Paul Valiant
81. Almost Tight Bounds for Reordering Buffer Management Anna Adamaszek and Artur Czumaj and Matthias Englert and Harald Raecke
82. Black-Box Identity Testing of Depth-4 Multilinear Circuits Shubhangi Saraf and Ilya Volkovich
83. Moser and Tardos meet Lovasz Kashyap Kolipaka and Mario Szegedy
84. On the Complexity of Powering in Finite Fields Swastik Kopparty

Type Sensitive Depth and Karchmer Wigderson Games

Throughout this post, we will be considering circuits over the basis where -gates have fanin 2 and -gates are only applied to input variables. Let be a boolean function on variables and be a circuit computing . For an output gate , let and be the sub-circuits, whose outputs are inputs to . Let be the depth of circuit and be the minimum depth of a circuit computing .

Karchmer and Wigderson [KW'90] showed an equivalence between circuit depth and a related problem in communication complexity. It is a simple observation that we can designate the two players as an “and-player” and an “or-player”. Let such that . Consider the communication game between two players ( and ), where gets and gets . The goal of the players to find a coordinate such that . Let represent the minimum number of bits they have to communicate in order for both to agree on such coordinate.

Karchmer-Wigderson Theorem : For every function we have .

Karchmer and Wigderson used the above theorem to prove that ‘monotone circuits for connectivity require super-logarithmic depth’. Let (resp. ) represent the minimum number of bits that (resp ) has to communicate. We can define type-sensitive depths of a circuit as follows. Let (resp. ) represent the AND-depth (resp. OR-depth) of .

AND-depth : AND-depth of an input gate is defined to be zero. AND-depth of an AND gate is max() + 1. AND-depth of an OR gate is max(). AND-depth of a circuit is the AND-depth of its output gate.

OR-depth is defined analogously. Let (resp. ) be the minimum AND-depth (resp. OR-depth) of a circuit computing .

Observation : For every function we have that corresponds to the AND-depth and corresponds to the OR-depth of the circuit constructed by Karchmer-Wigderson.

 

Open Problems :

• Can we prove explicit non-trivial lower bounds of  (or ) of a given function ? This sort of “asymmetric” communication complexity is partially addressed in [MNSW'98].
• A suitable notion of uniformity in communication games is to be defined to address such lower bounds. More on this in future posts.

 

References :

• [KW'90] Mauricio Karchmer and Avi Wigderson : Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255–265, 1990.
• [MNSW'98] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57(1): 37-49 (1998)
  

 

Balanced ST-Connectivity

Today’s post is about a new open problem arising from my recent paper  (available on ECCC). The problem is as follows :

Let be a directed graph. Let be the underlying undirected graph of . Let be a path in . Let be an edge along the path . Edge is called neutral edge if both and are in . Edge is called forward edge if and . Edge is called backward edge if and .

A path (say ) from to in is called balanced if the number of forward edges along is equal to the number of backward edges along . A balanced path might have any number of neutral edges. By definition, if there is a balanced path from to then there is a balanced path from to . The path may not be a simple path. We are concerned with balanced paths of length at most .

Balanced ST-Connectivity : Given a directed graph and two distinguished nodes and , decide if there is balanced path (of length at most ) between and .

In my paper, I proved that SGSLOGCFL, a generalization of Balanced ST-Connectivity, is contained in DSPACE(lognloglogn). Details about SGSLOGCFL are in my paper.

Theorem 1 : SGSLOGCFL is in DSPACE(lognloglogn).

Open Problem : Is ?

Cash Prize : I will offer $100 for a proof of . I have spent enough sleepless nights trying to prove it. In fact, an alternate proof of Theorem 1 (or even any upper bound better than ) using zig-zag graph product seems to be a challenging task.

Usually people offer cash prizes for a mathematical problem when they are convinced that :

• it is a hard problem.
• it is an important problem worth advertising.
• the solution would be beautiful, requires new techniques and sheds new light on our understanding of related problems.

My reason is “All the above”. Have Fun solving it !!

A cute puzzle : In Balanced ST-Connectivity we are only looking for paths of length at most . There are directed graphs where the only balanced st-path is super-linear. The example in the following figure shows an instance of Balanced ST-Connectivity where the only balanced path between and is of length . The directed simple path from to is of length . There is a cycle of length at the vertex . All the edges (except ) on this cycle are undirected. The balanced path from to is obtained by traversing from to , traversing the cycle clockwise for times and then traversing from to .

Puzzle : Are there directed graphs where every balanced st-path is of super-polynomial size ?

Update : The above puzzle is now solved.

Open Problems

• Is ?
• Are there directed graphs where every balanced st-path is of super-polynomial size ? (solved)
• More open problems are mentioned in my paper.