More Like this

1. Arithmetic Sketching

   Boneh, Dan; Boyle, Elette; Corrigan-Gibbs, Henry; Gilboa, Niv; Ishai, Yuval (January 2023, IACR International Cryptology Conference (CRYPTO))

   This paper introduces arithmetic sketching, an abstraction of a primitive that several previous works use to achieve lightweight, low-communication zero-knowledge verification of secret-shared vectors. An arithmetic sketching scheme for a language L ⊆ F^n consists of (1) a randomized linear function compressing a long input x to a short “sketch,” and (2) a small arithmetic circuit that accepts the sketch if and only if x ∈ L, up to some small error. If the language L has an arithmetic sketching scheme with short sketches, then it is possible to test membership in L using an arithmetic circuit with few multiplication gates. Since multiplications are the dominant cost in protocols for computation on secret-shared, encrypted, and committed data, arithmetic sketching schemes give rise to lightweight protocols in each of these settings. Beyond the formalization of arithmetic sketching, our contributions are: – A general framework for constructing arithmetic sketching schemes from algebraic varieties. This framework unifies schemes from prior work and gives rise to schemes for useful new languages and with improved soundness error. – The first arithmetic sketching schemes for languages of sparse vectors: vectors with bounded Hamming weight, bounded L1 norm, and vectors whose few non-zero values satisfy a given predicate. – A method for “compiling” any arithmetic sketching scheme for a language L into a low-communication malicious-secure multi-server protocol for securely testing that a client-provided secret-shared vector is in L. We also prove the first nontrivial lower bounds showing limits on the sketch size for certain languages (e.g., vectors of Hamming-weight one) and proving the non-existence of arithmetic sketching schemes for others (e.g., the language of all vectors that contain a specific value). 

   more » « less
2. Sketching Vocabulary for Crowd Motion

   Mathew, Tharindu; Benes, Bedrich; Aliaga, Daniel (September 2022, ACM SIGGRAPH / Eurographics Symposium on Computer Animation)

   This paper proposes and evaluates a sketching language to author crowd motion. It focuses on the path, speed, thickness, and density parameters of crowd motion. A sketch-based vocabulary is proposed for each parameter and evaluated in a user study against complex crowd scenes. A sketch recognition pipeline converts the sketches into a crowd simulation. The user study results show that 1) participants at various skill levels and can draw accurate crowd motion through sketching, 2) certain sketch styles lead to a more accurate representation of crowd parameters, and 3) sketching allows to produce complex crowd motions in a few seconds. The results show that some styles although accurate actually are less preferred over less accurate ones. 

   more » « less
3. Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-Order Convergence

   https://doi.org/10.1287/opre.2023.2445  

   Luo, Yuetian; Huang, Wen; Li, Xudong; Zhang, Anru (January 2024, Operations Research)

   Solving Rank Constrained Least Squares via Recursive Importance Sketching In statistics and machine learning, we sometimes run into the rank-constrained least squares problems, for which we need to find the best low-rank fit between sets of data, such as trying to figure out what factors are affecting the data, filling in missing information, or finding connections between different sets of data. This paper introduces a new method for solving this problem called the recursive importance sketching algorithm (RISRO), in which the central idea is to break the problem down into smaller, easier parts using a unique technique called “recursive importance sketching.” This new method is not only easy to use, but it is also very efficient and gives accurate results. We prove that RISRO converges in a local quadratic-linear and quadratic rate under some mild conditions. Simulation studies also demonstrate the superior performance of RISRO. 

   more » « less
4. Improving Engineering Sketching Education Through Perspective Techniques and an AI-Based Tutoring Platform

   Weaver, Morgan B.; Ray, Samantha; Hilton, Ethan Clark; Dorozhkin, Denis; Douglas, Kerrie; Hammond, Tracy; Linsey, Julie (June 2022, International journal of engineering education)

   Freehand sketching equips engineers to rapidly represent ideas in the design process, but most engineering curriculums fall short of equipping students with adequate sketching skills. This paper is focused on methods to improve engineers’ sketching skill through type of instruction, length of instruction, and delivery of and feedback for assignments using Sketchtivity, an intelligent sketch-tutoring software. We answer several key questions for providing better sketching education for engineers. Does perspective training improve freehand drawing ability? Can an intelligent tutoring software improve education outcomes? And how much sketching instruction is necessary for engineers? Analyzing the changes in sketching skill from pre- to post-sketching instruction between different instruction types (n = 116), we found that perspective sketching instruction significantly improved freehand sketching ability compared to traditional engineering sketching methods. When comparing pre to post sketching skill of students using Sketchtivity (n = 135), there was no significant difference in improvement between students using the intelligent tutoring software and those that exclusively practiced on paper – both groups improved equally. However, completing sketching tasks on tablets did not hinder students’ skill development even when measured on paper. Future work will more directly explore the influence of Sketchtivity on sketching skill development. Additionally, we found that five weeks of sketching instruction greatly improves sketching skill compared to only three weeks of instruction (n = 108), but both approaches significantly improve sketching self-efficacy. These outcomes support more extensive sketching instruction in engineering classrooms, and changes in instruction type to promote more freehand sketching skills. 

   more » « less
5. Improving Engineering Sketching Education Through Perspective Techniques and an AI-Based Tutoring Platform

   Weaver, M. B.; Ray, S.; Hilton, E. C.; Dorozhkin, D.; Douglas, K.; Hammond, T.; Linsey, J. (January 2022, IJEE International Journal of Engineering Education)

   Freehand sketching equips engineers to represent ideas rapidly in the design process, but most engineering curriculums fall short of equipping students with adequate sketching skills. This paper is focused on methods to improve engineers’ sketching skill through type of instruction, length of instruction, and delivery of and feedback for assignments using Sketchtivity, an intelligent sketch-tutoring software. We answer several key questions for providing better sketching education for engineers. Does perspective training improve freehand drawing ability? Can an intelligent tutoring software improve education outcomes? And how much sketching instruction is necessary for engineers? Analyzing the changes in sketching skill from pre- to post-sketching instruction between different instruction types (n = 116), we found that perspective sketching instruction significantly improved freehand sketching ability compared to traditional engineering sketching methods. When comparing pre to post sketching skill of students using Sketchtivity (n = 135), there was no significant difference in improvement between students using the intelligent tutoring software and those that exclusively practiced on paper – both groups improved equally. However, completing sketching tasks on tablets did not hinder students’ skill development even when measured on paper. Future work will more directly explore the influence of Sketchtivity on sketching skill development. Additionally, we found that five weeks of sketching instruction greatly improves sketching skill compared to only three weeks of instruction (n = 108), but both approaches significantly improve sketching self-efficacy. These outcomes support more extensive sketching instruction in engineering classrooms, and changes in instruction type to promote more freehand sketching skills. 

   more » « less