| 末尾に懇親会情報があります。
Program:
*** Note ***: Eric Blais (Carnegie Mellon University)'s talk was canceled
due to his emergency surgery. (It's not severe. He is recovering favorably.)
10:55-11:00: Opening: Hiro Ito (University of Electro-Communications)
11:00--11:30: Francois Le Gall (University of Tokyo)
- Sublinear Quantum Algorithms for Graph-theoretic Properties
(Lunch Break: 90 min.)
13:00--14:00: Invited: Comandur Seshadhri (Princeton University)
- Monotonicity and Lipschitz testing on hypergrids: alternating paths
to the rescue
14:00--14:30: Mitsuru Kusumoto (Kyoto University & ERATO)
- Testing Forest-Isomorphism in the Adjacency List Model
(Break: 20 min.)
14:50--15:20: Skip Jordan (Hokkaido University & ERATO)
- Property Testing, Logic and Complexity
15:20--15:50: Takahiro Ueda (Kyoto University)
- Sublinear-Time Cake-Cutting Algorithms
(Break: 20 min.)
16:10--16:40: Yuichi Yoshida (NII & Preferred Infrastructure)
- A Characterization of Locally Testable Affine-Invariant Properties
via Decomposition Theorems
16:40--17:10: Hiro Ito (University of Electro-Communications)
- A Paradigm Shift Toward The Big-Data Era
Abstracts:
- Eric Blais (Carnegie Mellon University) (Canceled)
Title: The communication complexity method in property testing
Abstract:
Since it’s introduction by Yao in 1979, the communication complexity method has been
spectacularly successful in establishing lower bounds in a wide variety of settings
throughout computer science. In this talk, we will survey recent work that shows how
this method can also be used to prove lower bounds on the complexity of property
testing algorithms. During the talk, we will explore some of the lower bounds that can
be obtained with this method, we will examine connections with the Fourier analysis of
functions, and we will discuss some of the fundamental open problems suggested by the
use of this method.
- Francois Le Gall (University of Tokyo)
Title: Sublinear Quantum Algorithms for Graph-theoretic Properties
Abstract:
Sublinear-time algorithms are omnipresent in the field of quantum algorithms. A typical
example is the well-known quantum search algorithm (discovered by Grover in 1996), which
finds a marked element among n elements in O(n^{1/2}) time, while any classical algorithm
for this task requires linear time. Recently, several new algorithmic techniques have
been developed and used to construct quantum algorithms for testing many graph-theoretic
properties, such as deciding if a given graph contains a triangle of not. In this talk
I will first survey these recent developments, and then present new quantum algorithms
for testing several properties over hypergraphs.
- Comandur Seshadhri (Princeton University)
Title: Monotonicity and Lipschitz testing on hypergrids: alternating paths to the rescue
Abstract:
Monotonicity testing is a classic problem in property testing. The domain [n]^d
is equipped with the natural coordinate-wise partial order. A function f:[n]^d -> R is
called monotone, if for all x < y, f(x) \leq f(y). A function is f is said to be \eps-far
from monotone, if it needs to be changed at at least \eps n^d values to make it monotone.
The problem of monotonicity testing is to decide (in sublinear queries to f) whether f is
monotone or \eps-far from monotone. We prove there exists a tester making O(\eps^{-1} d log n)
queries. This matches all known lower bounds, and completely resolves the problem of
monotonicity testing on hypergrids. (The complexity even for the case of the boolean
hypercube {0,1}^d was open until this result.)
The main technique is a new framework of alternating paths that is used to relate distant
violations of monotonicity to local violations. This framework allows us to get optimal
algorithms for this problem. It also gives optimal results for Lipschitz testing,
a property with known connections to data privacy. Indeed, the alternating paths framework
gets testers for a large class of "derivative-bounded properties" on hypergrids.
Joint work with Deeparnab Chakrabarty
- Mitsuru Kusumoto (Kyoto University & ERATO)
Title: Testing Forest-Isomorphism in the Adjacency List Model
Abstract:
We consider the problem of testing whether two input forests are isomorphic
or far from being so. An algorithm is called an $\epsilon$-tester for forest-isomorphism
if given query access to two forests $G$ and $H$ in the adjacency list model, with high
probability, accepts if $G$ and $H$ are isomorphic and rejects if we must modify at least
$\epsilon n$ edges to make $G$ isomorphic to $H$. We show an $\epsilon$-tester for
forest-isomorphism with query complexity $\poly \log n$ and an almost matching lower bound
of $\Omega(\sqrt{\frac{\log n}{\log \log n}})$. With the aid of the tester, we also show
that every graph property is testable in the adjacency list model with $\poly \log n$
queries if the input graph is a forest.
- Skip Jordan (Hokkaido University & ERATO)
Title: Property Testing, Logic and Complexity
Abstract:
Given a computationally intractable problem, it is natural to consider
approximations and hope to gain efficiency. In property testing, we consider what can
be achieved given only a sublinear or constant sample of the input.
Here, I will introduce various open questions concerning combinations of
property testing and logic. Most are inspired by complexity theory,
and especially by descriptive complexity.
- Takahiro Ueda (Kyoto University)
Title: Sublinear-Time Cake-Cutting Algorithms
Abstract:
In this research, we show sub-linear time algorithms for the cake-cutting problem.
The cake-cutting problem is a problem of dividing a cake into pieces and handing them down
to players who have different measures of the value of the cake, and then they must be
``satisfied.'' Though the definition of ``satisfaction'' are various, e.g. simple-fair,
envy-free and so on, we talk about simple-fair division such that each player has 1/n values
in his/her piece of cake in his/her own value function. It is known that the query complexity
for the cake-cutting problem is \Theta(n logn) for both deterministic and random algorithms.
But no o(n)-time algorithm have been knows for dividing a piece only for the first player.
We construct a framework to solve the cake-cutting problem in sublinear-time, and show
algorithms in this framework. In particular, algorithms with {\eps n}-victims for
dividing a cake for r=o(n) players in O(r/\eps) times. And then the first r players who
are assigned a piece of cake must be satisfied. Furthermore, we extend this algorithm to
general f(n)-victims.
- Yuichi Yoshida (NII & Preferred Infrastructure)
Title: A Characterization of Locally Testable Affine-Invariant Properties via Decomposition Theorems
Abstract:
Let P be a property of functions Fnp → {0, 1} for a fixed prime p. An algorithm is called
a tester for P if, given a query access to the input function f, with high probability,
it accepts when f satisfies P and rejects when f is “far” from satisfying P. In this paper,
we give a characterization of affine-invariant properties that are testable with a constant
number of queries. The characterization is stated in terms of decomposition theorems, which
roughly claim that any function can be decomposed into a structured part that is a function
of a constant number of polynomials, and a pseudo-random part whose Gowers norm is small.
We first show an algorithm that tests whether the structured part of the input function has
a specific form. We then show that an affine-invariant property is testable with a constant
number of queries if and only if it can be reduced to the problem of testing whether the
structured part of the input function is close to one of a constant number of candidates.
- Hiro Ito (University of Electro-Communications)
Title: A Paradigm Shift Toward The Big-Data Era
Abstract:
In this century we are facing the big-data era. For treating big data, traditional
common sense sometimes does not work. Though we thought that polynomial-time algorithms
are fast algorithms in the past century, it is not always true for big data, e.g.,
an O(n^2)-time algorithm may be no longer fast! For such problems, sublinear-time,
especially constant-time algorithms should take important roles.
Yes, we need a new paradigm! In this talk, we try to consider what should be this
paradigm and how does it work.
懇親会：
日時: 2014年 12月 6日 (金) 17:45 〜
場所: しゃぶしゃぶ温野菜 神保町白山通り店
懇親会参加費: 4,000円 (予定) (会場で集めます)
懇親会参加申込（〆切：12月 3日 (火) 19:00）は下記URL：
https://www.al.ics.saitama-u.ac.jp/elc/reg/2013_1206_a02/
（人数確定の必要上、懇親会は事前申し込みが必要です。）
|