Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors apply algebraic geometry to program synthesis, by identifying programs with points of analytic varieties. They construct a smooth relaxation to the synthesis problem by considering the space of probability distributions over codes for universal turning machines (which is a smooth/continuous manifold), and then translate this probability into corresponding probabilities of generating a correct program. This allows them to extend the KL divergence on the discrete distribution of codes to a smooth function, whose zeros correspond to the desired programs. They use MCMC to find (approximate) these zeros.

Overall, the approach seems interesting, but seems to be a bit complex for a real application (both examples considered in the experiments seem pretty small/toy problems). While the ideas are interesting, it seems like more work needs to be done before they could be of interest to practical program synthesis (admittedly, the authors do not claim that it is practical, but I am unable to judge the paper by quality of the theoretical work)

review_title: Review for "Geometry of Program Synthesis"

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper is very densely written with a lot of heavy mathematical formalism and not enough schematics to explain how it works. Most of the foundations are coming from theoretical computer science that is beyond my area of expertise. I spent many hours and still don't understand the point that the authors are trying to make. It seems to me that they are trying to use some extensions of the manifold variety in order to do program synthesis. They support their thesis with some theorems and assumptions around the geometry of program synthesis. The whole paper revolves around the zeros of the KL divergence between q(x,y) and p(y|x,w). They give a detailed analysis of these functions and justify why the Singular Learning Theory is appropriate for this study.
Following the references wasn't easy. The paper is based on this work https://arxiv.org/pdf/1805.11813.pdf which is outside of my research area.

I would suggest a revision and a lighter submission of the paper, I am not sure it is appropriate for this venue
review_title: Very hard to understand

final_score: rating: 7: Good paper, accept
review_content: - quality : good
- clarity : very good. I was worried about reading this due to all the math symbols, but it turns out the big pictures are clearly explained.
- originality : okay
- significance : not sure

I could not follow the more technical aspects as I'm not a theory person (although I did fail algebraic geometry at one point). The main claim of the paper is that when doing relaxations and attempt to view satisfying programs as the variety W0 of some mathematical function, W0 is typically larger than W0 \intersect Wcode. This is important because one may easily find a point of solution in the variety W0, yet it cannot be realized as a working program in Wcode. I can confirm that this is indeed the case in some limited capacity when I tried to approximate deterministic functions via neural networks, and attempted to synthesize these functions by "pulling back" from the output to the space of programs, which resulted in a relaxed representation of program that has very low loss, yet do not correspond to actual programs. It is nice to see why this happened in a formal setting.

As I am confident that my expertise in this area is not high, I will not be providing an explicit pro/con list. I would instead ask a few questions to the authors and hope I can get a good response:

- A natural thing to make program synthesis more amendable is by changing the set Wcode. For instance, if I were to represent the function that adds 3, I can either do that with x + 3, or with x+1+1+1. Now, which one of these representation would lead to a Wcode that has a better chance of intersecting better with W0? As DSL designers, we have fairly big freedom in designing what Wcode is, that is often the only thing we can control. Is there a rule of thumb that we can follow to ensure that gradient-based or sampling-based relaxation works well? i.e. W0 isn't such a horrible extended object?

- Another "knob" that we can control easily in synthesis is the number of input output examples, and which examples to give. If I want to specify a polynomial of degree 2, I can choose either 3 points, or 30 points. Which is easier? Specifically, given a specific Wcode, given two dataset of input-output examples, D1 and D2. Let Sol(D,Wcode) denote the set of programs in Wcode that satisfies D completely, in a classical sense. The question is, if Sol(D1, Wcode) = Sol(D2, Wcode), how do we quantify if synthesis is easier over D1 or over D2 ? i.e. which set, Variety(D1) or Variety(D2) is the more horrible extended object of Wcode?

final recommendation:
I maintain my score. I think this is an interesting piece of work that can easily be used as citations whenever the discussion of "why don't you just relax your program to be differentiable" comes up, and I can cite this paper and say "no that does not work theoretically".
review_title: Classically, we think of synthesis (by gradient, over a smooth relaxation) as getting lucky of arriving at a solution s.t. the loss is 0. This work says that instead, it is easy to arrive at a point where the KL 0, but it might not be a realizable program.

Meta-review: This paper is a bad fit for ICLR and the authors may consider submitting to more theoretical venues. This paper studies algebraic geometry (an area unfamiliar to most ICLR readers) of program synthesis, with the "hope that algebraic geometry can assist in developing the next generation of synthesis machines." Unfortunately, this paper does not get far enough down that path, and its implications cannot realistically be appreciated by an ICLR audience. The reviewers indicate that their low confidence is due to their lack of understanding of algebraic geometry and not due to their lack of understanding of program synthesis. The featured implication of the paper is that synthesized programs are singularities of analytic functions, which is not very meaningful to the ICLR audience. Even if external reviewers verified the correctness of the math, the ICLR audience would still not understand the implications. 
Decision: Reject