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
Streaming and Sketching Complexity of CSPs: {A} Survey (Invited Talk)
In this survey we describe progress over the last decade or so in understanding the complexity of solving constraint satisfaction problems (CSPs) approximately in the streaming and sketching models of computation. After surveying some of the results we give some sketches of the proofs and in particular try to explain why there is a tight dichotomy result for sketching algorithms working in subpolynomial space regime.
more »
« less
- Award ID(s):
- 2152413
- NSF-PAR ID:
- 10400121
- Editor(s):
- Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P.
- Date Published:
- Journal Name:
- 49th International Colloquium on Automata, Languages, and Programming, {ICALP} 2022
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract In this paper we consider large-scale smooth optimization problems with multiple linear coupled constraints. Due to the non-separability of the constraints, arbitrary random sketching would not be guaranteed to work. Thus, we first investigate necessary and sufficient conditions for the sketch sampling to have well-defined algorithms. Based on these sampling conditions we develop new sketch descent methods for solving general smooth linearly constrained problems, in particular, random sketch descent (RSD) and accelerated random sketch descent (A-RSD) methods. To our knowledge, this is the first convergence analysis of RSD algorithms for optimization problems with multiple non-separable linear constraints. For the general case, when the objective function is smooth and non-convex, we prove for the non-accelerated variant sublinear rate in expectation for an appropriate optimality measure. In the smooth convex case, we derive for both algorithms, non-accelerated and A-RSD, sublinear convergence rates in the expected values of the objective function. Additionally, if the objective function satisfies a strong convexity type condition, both algorithms converge linearly in expectation. In special cases, where complexity bounds are known for some particular sketching algorithms, such as coordinate descent methods for optimization problems with a single linear coupled constraint, our theory recovers the best known bounds. Finally, we present several numerical examples to illustrate the performances of our new algorithms.more » « less
-
null (Ed.)Spatial reasoning skills contribute to performance in many STEM fields. For example, drawing sectional views of three-dimensional objects is an essential skill for engineering students. There is considerable variation in the spatial reasoning skills of prospective engineering students, putting some at risk for compromised performance in their classes. This study takes place in a first-year engineering Spatial Visualization course to integrate recent practices in engineering design education with cognitive psychology research on the nature of spatial learning. We employed three main pedagogical strategies in the course - 1) in class instruction on sketching; 2) spatial visualization training; and 3) manipulation of physical objects (CAD/3D print creations). This course endeavors to use current technology, online accessibility, and implementation of the three pedagogical strategies to bring about student growth in spatial reasoning. This study is designed to determine the effect of adding two different spatial reasoning training apps to this environment. Over 230 students (three sections) participated in our study. In two of the three sections, students received interactive spatial visualization training using either a spatial visualization mobile touchscreen app in one section or an Augmented Reality (AR) app in the other section. Research suggests that there are benefits to using the Spatial Vis Classroom mobile app for college students.The app has been shown to increase student persistence resulting in large learning gains as measured by the Purdue assessment of spatial visualization (PSVT-R), especially for students starting with poor spatial visualization skills. The Spatial Vis Classroom app can be used in the classroom or assigned as homework. The AR app is designed to help users develop their mental rotation abilities. It is designed to support a holistic understanding of 3-dimensional objects, and research has shown that, in combination with a traditional curriculum, it increases students’ abilities also measured by the PSVT-R. Of particular interest, the data suggest that the app overcomes the advantage found by males over females in a traditional class alone focused on spatial reasoning. Both of the course sections were required to use the apps for approximately the same time in class and outside of class. Students in the control section were required to do hand sketching activities in class and outside of class, with roughly the same completion time as for the sections with the apps. Students grades were not affected by using the three different approaches as grading was based on completion only. Based on current literature, we hypothesize that overall benefits (PSVT-R gains) will be comparable across the 3 treatments but there will be different effects on attitude and engagement (confidence,enjoyment, and self-efficacy). Lastly, we hypothesize that the treatments will have different effects on male/female and ethnic categories of the study participants. The final paper will include an analysis of results and a report of the findings.more » « less
-
Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. Popular sketching approaches to this problem (e.g., CountMin and CountSketch) come with worst-case guarantees that probabilistically bound the error of the estimated frequencies for any possible input. The work of Hsu et al.~(2019) introduced the idea of using machine learning to tailor sketching algorithms to the specific data distribution they are being run on. In particular, their learning-augmented frequency estimation algorithm uses a learned heavy-hitter oracle which predicts which elements will appear many times in the stream. We give a novel algorithm, which in some parameter regimes, already theoretically outperforms the learning based algorithm of Hsu et al. without the use of any predictions. Augmenting our algorithm with heavy-hitter predictions further reduces the error and improves upon the state of the art. Empirically, our algorithms achieve superior performance in all experiments compared to prior approaches.more » « less
-
In online or large in-person course sections, instructors often adopt an online homework tool to alleviate the burden of grading. While these systems can quickly tell students whether they got a problem correct for a multiple-choice or numeric answer, they are unable to provide feedback on students’ free body diagrams. As the process of sketching a free body diagram correctly is a foundational skill to solving engineering problems, the loss of feedback to the students in this area is a detriment to students. To address the need for rapid feedback on students’ free body diagram sketching, the research team developed an online, sketch-recognition system called Mechanix. This system allows students to sketch free body diagrams, including for trusses, and receive instant feedback on their sketches. The sketching feedback is ungraded. After the students have a correct sketch, they are then able to enter in the numeric answers for the problem and submit those for a grade. Thereby, the platform offers the grading convenience of other online homework systems but also helps the students develop their free body diagram sketching skills. To assess the efficacy of this experimental system, standard concept inventories were administered pre- and post-semester for both experimental and control groups. The unfamiliarity or difficulty of some advanced problems in the Statics Concept Inventory, however, appeared to discourage students, and many would stop putting in any effort after a few problems that were especially challenging to solve. This effect was especially pronounced with the Construction majors versus the Mechanical Engineering majors in the test group. To address this tendency and therefore collect more complete pre- and post-semester concept inventory data, the research group worked on reordering the Statics Concept Inventory questions from more familiar to more challenging, based upon the past performance of the initial students taking the survey. This paper describes the process and results of the effort to reorder this instrument in order to increase Construction student participation and, therefore, the researchers’ ability to measure the impact of the Mechanix system.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
