More Like this

1. On Students' Usage of Tracing for Understanding Code

   https://doi.org/10.1145/3545945.3569741  

   Hassan, Mohammed; Zilles, Craig (March 2023, SIGCSE 2023: Proceedings of the 54th ACM Technical Symposium on Computer Science Education)

   Explain in Plain English (EiPE) questions evaluate whether students can understand and explain the high-level purpose of code. We conducted a qualitative think-aloud study of introductory programming students solving EiPE questions. In this paper, we focus on how students use tracing (mental execution) to understand code in order to explain it. We found that, in some cases, tracing can be an effective strategy for novices to understand and explain code. Furthermore, we observed three problems that prevented tracing from being helpful, which are 1) not employing tracing when it could be helpful (some struggling students explained correctly after the interviewer suggested tracing the code), 2) tracing incorrectly due to misunderstandings of the programming language, and 3) tracing with a set of inputs that did not sufficiently expose the code’s behavior (upon interviewer suggesting inputs, students explained correctly). These results suggest that we should teach students to use tracing as a method for understanding code and teach them how to select appropriate inputs to trace. 

   more » « less
2. Defining $$\mathbb Z$$ using unit groups

   https://doi.org/10.4064/aa230505-6-6  

   Mazur, Barry; Rubin, Karl; Shlapentokh, Alexandra (January 2024, Acta Arithmetica)

   We consider first-order definability and decidability questions over rings of integers of algebraic extensions of $$\Q$$, paying attention to the uniformity of definitions. The uniformity follows from the simplicity of our first-order definition of $$\Z$$. Namely, we prove that for a large collection of algebraic extensions $$K/\Q$$, $$ \{x \in \oo_K : \text{$$\forall \e \in \oo_K^\times \;\exists \delta \in \oo_K^\times$ such that $$\delta-1 \equiv (\e-1)x \pmod{(\e-1)^2}$$}\} = \Z $$ where $$\oo_K$$ denotes the ring of integers of $$K$$. One of the corollaries of our results is undecidability of the field of constructible numbers, a question posed by Tarski in 1948. \end{abstract} 

   more » « less
3. Classical Coding Problem from Transversal T Gates

   https://doi.org/10.1109/ISIT44484.2020.9174408  

   Rengaswamy, Narayanan; Calderbank, Robert; Newman, Michael; Pfister, Henry D. (June 2020, 2020 IEEE International Symposium on Information Theory (ISIT))

   null (Ed.)

   Universal quantum computation requires the implementation of a logical non-Clifford gate. In this paper, we characterize all stabilizer codes whose code subspaces are preserved under physical T and T † gates. For example, this could enable magic state distillation with non-CSS codes and, thus, provide better parameters than CSS-based protocols. However, among non-degenerate stabilizer codes that support transversal T, we prove that CSS codes are optimal. We also show that triorthogonal codes are, essentially, the only family of CSS codes that realize logical transversal T via physical transversal T. Using our algebraic approach, we reveal new purely-classical coding problems that are intimately related to the realization of logical operations via transversal T. Decreasing monomial codes are also used to construct a code that realizes logical CCZ. Finally, we use Ax's theorem to characterize the logical operation realized on a family of quantum Reed-Muller codes. This result is generalized to finer angle Z-rotations in https://arxiv.org/abs/1910.09333. 

   more » « less
4. Structural, point-free, non-Hausdorff topological realization of Borel groupoid actions

   https://doi.org/10.1017/fms.2024.25  

   Chen, Ruiyuan (March 2024, Forum of Mathematics, Sigma)

   We extend the Becker–Kechris topological realization and change-of-topology theorems for Polish group actions in several directions. For Polish group actions, we prove a single result that implies the original Becker–Kechris theorems, as well as Sami’s and Hjorth’s sharpenings adapted levelwise to the Borel hierarchy; automatic continuity of Borel actions via homeomorphisms and the equivalence of ‘potentially open’ versus ‘orbitwise open’ Borel sets. We also characterize ‘potentially open’ n-ary relations, thus yielding a topological realization theorem for invariant Borel first-order structures. We then generalize to groupoid actions and prove a result subsuming Lupini’s Becker–Kechris-type theorems for open Polish groupoids, newly adapted to the Borel hierarchy, as well as topological realizations of actions on fiberwise topological bundles and bundles of first-order structures. Our proof method is new even in the classical case of Polish groups and is based entirely on formal algebraic properties of category quantifiers; in particular, we make no use of either metrizability or the strong Choquet game. Consequently, our proofs work equally well in the non-Hausdorff context, for open quasi-Polish groupoids and more generally in the point-free context, for open localic groupoids. 

   more » « less
5. The Ceresa class: tropical, topological, and algebraic

   Corey, Daniel; Ellenberg, Jordan; Li, Wanlin (September 2020, ArXivorg)

   null (Ed.)

   The Ceresa cycle is an algebraic cycle attached to a smooth algebraic curve with a marked point, which is trivial when the curve is hyperelliptic with a marked Weierstrass point. The image of the Ceresa cycle under a certain cycle class map provides a class in étale cohomology called the Ceresa class. Describing the Ceresa class explicitly for non-hyperelliptic curves is in general not easy. We present a "combinatorialization" of this problem, explaining how to define a Ceresa class for a tropical algebraic curve, and also for a topological surface endowed with a multiset of commuting Dehn twists (where it is related to the Morita cocycle on the mapping class group). We explain how these are related to the Ceresa class of a smooth algebraic curve over ℂ((t)), and show that the Ceresa class in each of these settings is torsion. 

   more » « less