Publication

When Is Amplification Necessary for Composition in Randomized Query Complexity?

Related publications (30)

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, Paul Scharnhorst, Emilio Maddalena

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