Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > CHRISTOS TZAMOS:
All reports by Author Christos Tzamos:

TR22-178 | 8th December 2022
Ilias Diakonikolas, Christos Tzamos, Daniel Kane

A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning

The Forster transform is a method of regularizing a dataset
by placing it in {\em radial isotropic position}
while maintaining some of its essential properties.
Forster transforms have played a key role in a diverse range of settings
spanning computer science and functional analysis. Prior work had given
{\em ... more >>>


TR18-131 | 17th July 2018
Gautam Kamath, Christos Tzamos

Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing

We investigate distribution testing with access to non-adaptive conditional samples.
In the conditional sampling model, the algorithm is given the following access to a distribution: it submits a query set $S$ to an oracle, which returns a sample from the distribution conditioned on being from $S$.
In the non-adaptive setting, ... more >>>




ISSN 1433-8092 | Imprint