Publications associées à When Is Amplification Necessary for Composition in Randomized Query Complexity?

Publications associées (30)

Stable parameterization of continuous and piecewise-linear functions

Michaël Unser, Alexis Marie Frederic Goujon, Joaquim Gonçalves Garcia Barreto Campos

Rectified-linear-unit (ReLU) neural networks, which play a prominent role in deep learning, generate continuous and piecewise-linear (CPWL) functions. While they provide a powerful parametric representation, the mapping between the parameter and function s ...

2023

Fairness and Explainability in Clustering Problems

Xinrui Jia

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

EPFL2023

Debates on the dorsomedial prefrontal/dorsal anterior cingulate cortex: insights for future research

Nicolas Clairis

The dorsomedial prefrontal cortex/dorsal anterior cingulate cortex (dmPFC/dACC) is a brain area subject to many theories and debates over its function(s). Even its precise anatomical borders are subject to much controversy. In the past decades, the dmPFC/d ...

Oxford Univ Press2023

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Mehmet Fatih Sahin

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...

EPFL2023

A Functional Perspective on Information Measures

Amedeo Roberto Esposito

Since the birth of Information Theory, researchers have defined and exploited various information measures, as well as endowed them with operational meanings. Some were born as a "solution to a problem", like Shannon's Entropy and Mutual Information. Other ...

EPFL2022

Nothing New Under the Sun: Novelty Constructs and Measures in Social Studies

Davide Bavato

The concept of novelty is central to questions of creativity, innovation, and discovery. Despite the prominence in scientific inquiry and everyday discourse, there is a chronic ambiguity over its meaning and a surprising variety of empirical measures, whic ...

Emerald Publishing Limited2022

Predictive Analysis of Errors During Robot-Mediated Gamified Training

Pierre Dillenbourg, Arzu Güneysu Özgür

This paper presents our approach to predicting future error-related events in a robot-mediated gamified phys- ical training activity for stroke patients. The ability to predict future error under such conditions suggests the existence of distinguishable fe ...

IEEE2022

Derivative voltammetry: a simple tool to probe reaction selectivity in photoelectrochemical cells

Kevin Sivula, Florent Alexandre Boudoire, Nukorn Plainpan

We demonstrate the use of the derivative voltammogram method to predict the selectivity of the photo-driven oxidation of 5-hydroxymethylfurfural (HMF) on a WO3 photoanode as a function of applied potential using only information obtained from the linear sw ...

2022

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

Adam Teodor Polak

We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of w workers and a multiset T ⊆ [t] of |T| = w tasks, a memoryless worker-task assignment function is any function ϕ that assigns the workers ...

Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik2022

Toward Mobile Distributed Ledgers

Boi Faltings, Sujit Prakash Gujar

Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on Device-to-Device (D2D) ecosystems (e.g., crowdsensing). Sophisticated applications, like cryptocurrencies, need distr ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Perturbed Fourier uniqueness and interpolation results in higher dimensions

Martin Peter Stoller, Joao Pedro Gonçalves Ramos

We obtain new Fourier interpolation and uniqueness results in all dimensions, extending methods and results by the first author and M. Sousa [11] and the second author [12]. We show that the only Schwartz function which, together with its Fourier transform ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

Fourier uniqueness and interpolation in Euclidean space

Martin Peter Stoller

We prove that every Schwartz function in Euclidean space can be completely recovered given only its restrictions and the restrictions of its Fourier transform to all origin-centered spheres whose radii are square roots of integers. In particular, the only ...

EPFL2022

Predicting involuntary hospitalization in psychiatry: A machine learning investigation

Mehdi Gholam

Background Coercion in psychiatry is a controversial issue. Identifying its predictors and their interaction using traditional statistical methods is difficult, given the large number of variables involved. The purpose of this study was to use machine-lear ...

CAMBRIDGE UNIV PRESS2021

A New Channel-Base Lightning Current Formula With Analytically Adjustable Parameters

Farhad Rachidi-Haeri

The article provides a new channel-based current function, which aims at faithfully reproducing the salient parameters of lightning currents. All the model parameters can be set in a fully analytical way, guaranteeing the possibility of changing them (acco ...

2021

Propagation on Multi-relational Graphs for Node Regression

Eda Bayram

Recent years have witnessed a rise in real-world data captured with rich structural information that can be conveniently depicted by multi-relational graphs. While inference of continuous node features across a simple graph is rather under-studied by the c ...

Springer, Cham2022

Monte Carlo Estimators for Differential Light Transport

Wenzel Alban Jakob, Tizian Lucien Zeltner, Sébastien Nicolas Speierer

Physically based differentiable rendering algorithms propagate derivatives through realistic light transport simulations and have applications in diverse areas including inverse reconstruction and machine learning. Recent progress has led to unbiased metho ...

ASSOC COMPUTING MACHINERY2021

Deterministic error bounds for kernel-based learning techniques under bounded noise

Colin Neil Jones, Emilio Maddalena, Paul Scharnhorst

We consider the problem of reconstructing a function from a finite set of noise-corrupted samples. Two kernel algorithms are analyzed, namely kernel ridge regression and epsilon-support vector regression. By assuming the ground-truth function belongs to th ...

2021

Proving and Disproving Equivalence of Functional Programming Assignments

Viktor Kuncak, Dragana Milovancevic

We present an automated approach to verify the correctness of programming assignments, such as the ones that arise in a functional programming course. Our approach takes as input student submissions and reference solutions, and uses equivalence checking to ...

2023

Loss landscape and symmetries in Neural Networks

Mario Geiger

Neural networks (NNs) have been very successful in a variety of tasks ranging from machine translation to image classification. Despite their success, the reasons for their performance are still not well-understood. This thesis explores two main themes: lo ...

EPFL2021

A Majority Lemma for Randomised Query Complexity

Mika Tapani Göös, Gilbert Théodore Maystre

We show that computing the majority of n copies of a boolean function g has randomised query complexity R(Maj∘gⁿ) = Θ(n⋅R ̅_{1/n}(g)). In fact, we show that to obtain a similar result for any composed function f∘gⁿ, it suffices to prove a sufficiently stro ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021