5 citations · 7 across the 10 of their papers we have counts for
11 papers
Bayes Complexity of Learners vs Overfitting
Grzegorz Głuch, Rudiger Urbanke
We introduce a new notion of complexity of functions and we show that it has the following properties: (i) it governs a PAC Bayes-like generalization bound, (ii) for neural network…
Nonlocality under Computational Assumptions
Khashayar Barooti, Alexandru Gheorghiu, Grzegorz Głuch +1
Nonlocality and its connections to entanglement are fundamental features of quantum mechanics that have found numerous applications in quantum information science. A set of correla…
Provable Adversarial Robustness in the Quantum Model
Khashayar Barooti, Grzegorz Głuch, Ruediger Urbanke
Modern machine learning systems have been applied successfully to a variety of tasks in recent years but making such systems robust against adversarially chosen modifications of in…
Noether: The More Things Change, the More Stay the Same
Grzegorz Głuch, Rüdiger Urbanke
Symmetries have proven to be important ingredients in the analysis of neural networks. So far their use has mostly been implicit or seemingly coincidental. We undertake a systemati…
Adversarial Robustness: What fools you makes you stronger
Grzegorz Głuch, Rüdiger Urbanke
We prove an exponential separation for the sample complexity between the standard PAC-learning model and a version of the Equivalence-Query-learning model. We then show that this s…
Spectral Clustering Oracles in Sublinear Time
Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi +2
Given a graph that can be partitioned into disjoint expanders with outer conductance upper bounded by , can we efficiently construct a small space data structure th…
Query complexity of adversarial attacks
Grzegorz Głuch, Rüdiger Urbanke
There are two main attack models considered in the adversarial robustness literature: black-box and white-box. We consider these threat models as two ends of a fine-grained spectru…
Constructing a provably adversarially-robust classifier from a high accuracy one
Grzegorz Głuch, Rüdiger Urbanke
Modern machine learning models with very high accuracy have been shown to be vulnerable to small, adversarially chosen perturbations of the input. Given black-box access to a high-…
The First Order Truth behind Undecidability of Regular Path Queries Determinacy
Grzegorz Głuch, Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja
In our paper [Głuch, Marcinkowski, Ostropolski-Nalewaja, LICS ACM, 2018] we have solved an old problem stated in [Calvanese, De Giacomo, Lenzerini, Vardi, SPDS ACM, 2000] showing t…
Can One Escape Red Chains? Regular Path Queries Determinacy is Undecidable
Grzegorz Głuch, Jerzy Marcinkowski, Piotr Ostropolski-Nalewaja
For a given set of queries (which are expressions in some query language) , and for another query we say that determines…
4/3 Rectangle Tiling lower bound
Grzegorz Głuch, Krzysztof Loryś
The problem that we consider is the following: given an array of positive numbers, find a tiling using at most rectangles (which means that each array element…