All reports by Author Yuichi Yoshida:

__
TR22-051
| 18th April 2022
__

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida#### Low Degree Testing over the Reals

__
TR20-103
| 9th July 2020
__

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida#### One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

Revisions: 1

__
TR16-201
| 19th December 2016
__

Eric Blais, Yuichi Yoshida#### A Characterization of Constant-Sample Testable Properties

__
TR14-066
| 17th April 2014
__

Suguru Tamaki, Yuichi Yoshida#### Robust Approximation of Temporal CSP

__
TR12-103
| 16th August 2012
__

Arnab Bhattacharyya, Yuichi Yoshida#### Testing Assignments of Boolean CSPs

__
TR10-106
| 17th June 2010
__

Yuichi Yoshida#### Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP

Revisions: 1

__
TR09-074
| 10th September 2009
__

Suguru Tamaki, Yuichi Yoshida#### A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida

We study the problem of testing whether a function $f: \mathbb{R}^n \to \mathbb{R}$ is a polynomial of degree at most $d$ in the distribution-free testing model. Here, the distance between functions is measured with respect to an unknown distribution $\mathcal{D}$ over $\mathbb{R}^n$ from which we can draw samples. In contrast ... more >>>

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A ... more >>>

Eric Blais, Yuichi Yoshida

We characterize the set of properties of Boolean-valued functions on a finite domain $\mathcal{X}$ that are testable with a constant number of samples.

Specifically, we show that a property $\mathcal{P}$ is testable with a constant number of samples if and only if it is (essentially) a $k$-part symmetric property ...
more >>>

Suguru Tamaki, Yuichi Yoshida

A temporal constraint language $\Gamma$ is a set of relations with first-order definitions in $({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from $\Gamma$. CSP($\Gamma$) admits robust approximation if, for any $\varepsilon \geq 0$, given a $(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an ... more >>>

Arnab Bhattacharyya, Yuichi Yoshida

Given an instance $\mathcal{I}$ of a CSP, a tester for $\mathcal{I}$ distinguishes assignments satisfying $\mathcal{I}$ from those which are far from any assignment satisfying $\mathcal{I}$. The efficiency of a tester is measured by its query complexity, the number of variable assignments queried by the algorithm. In this paper, we characterize ... more >>>

Yuichi Yoshida

Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it.

In this paper, we show that a ...
more >>>

Suguru Tamaki, Yuichi Yoshida

Long Code testing is a fundamental problem in the area of property

testing and hardness of approximation.

Long Code is a function of the form $f(x)=x_i$ for some index $i$.

In the Long Code testing, the problem is, given oracle access to a

collection of Boolean functions, to decide whether ...
more >>>