Concept
Time hierarchy theorem
Publications associées (21)
Supporting Teachers' Orchestration in Robot-mediated Classrooms
To bring educational robots to classrooms, we need to consider teachers' self-efficacy and challenges in managing a robot-mediated classroom, and how to support them in overcoming these challenges. Orchestration tools are designed to support teachers by pr ...
EPFL2023Polynomial-time universality and limitations of deep learning
The goal of this paper is to characterize function distributions that general neural networks trained by descent algorithms (GD/SGD), can or cannot learn in polytime. The results are: (1) The paradigm of general neural networks trained by SGD is poly-time ...
WILEY2023Adaptive isogeometric methods with C-1 (truncated) hierarchical splines on planar multi-patch domains
Isogeometric analysis is a powerful paradigm which exploits the high smoothness of splines for the numerical solution of high order partial differential equations. However, the tensor-product structure of standard multivariate B-spline models is not well s ...
WORLD SCIENTIFIC PUBL CO PTE LTD2023Spatial Isolation Implies Zero Knowledge Even in a Quantum World
Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assu ...
ASSOC COMPUTING MACHINERY2022Knapsack and Subset Sum with Small Items
Adam Teodor Polak, Lars Rohwedder
Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...
Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021Flipped classroom in Linear Algebra
Simone Deparis, Roland John Tormey, Cécile Hardebolle
As Saitta et al. report in [1], the flipped classroom model builds on several well-known teaching approaches. In particular, using in-class time for more active learning activities as been constantly shown by research to improve learning [2]. In this prese ...
2019On the complexity of linearizability
It was previously shown that the problem of verifying whether a finite concurrent system is linearizable can be done with an EXPSPACE complexity. However, the best known lower bound is PSPACE-hardness, and can be obtained using a reduction from control-sta ...
SPRINGER WIEN2019Filtering Random Graph Processes Over Random Time-Varying Graphs
Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deterministic setting, ignoring the impact of stochasticity i ...
Institute of Electrical and Electronics Engineers2017Scaladoc Diagrams for Class Hierarchies
On numerous occasions it has been pointed out that the class hierarchy of the Scala standard library is hard to follow. This project aims at addressing the problem by automatically generating interactive class hierarchy diagrams in the scaladoc tool. ...
2012Putting research into practice: Pedagogy development workshops change the teaching philosophy of graduate students
Teaching competence is an important skill for graduate students to acquire and is often considered a precursor to an academic career. In this study, we evaluated the effects of a multi-day teaching workshop on graduate teaching philosophies by surveying 20 ...
2012