All reports by Author Youming Qiao:

__
TR23-004
| 13th January 2023
__

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang#### On linear-algebraic notions of expansion

__
TR14-061
| 21st April 2014
__

Raghav Kulkarni, Youming Qiao, Xiaoming Sun#### Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive

__
TR14-034
| 3rd March 2014
__

Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram#### On the complexity of trial and error for constraint satisfaction problems

__
TR13-123
| 6th September 2013
__

Joshua Grochow, Youming Qiao#### Algorithms for group isomorphism via group extensions and cohomology

__
TR13-103
| 24th July 2013
__

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha#### Generalized Wong sequences and their applications to Edmonds' problems

__
TR12-033
| 5th April 2012
__

Ankit Gupta, Neeraj Kayal, Youming Qiao#### Random Arithmetic Formulas can be Reconstructed Efficiently

__
TR10-084
| 14th May 2010
__

Maurice Jansen, Youming Qiao, Jayalal Sarma#### Deterministic Identity Testing of Read-Once Algebraic Branching Programs

__
TR10-015
| 8th February 2010
__

Maurice Jansen, Youming Qiao, Jayalal Sarma#### Deterministic Black-Box Identity Testing $\pi$-Ordered Algebraic Branching Programs

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang

A fundamental fact about bounded-degree graph expanders is that three notions of expansion---vertex expansion, edge expansion, and spectral expansion---are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion.

There are two well-studied notions of linear-algebraic expansion, namely dimension expansion ... more >>>

Raghav Kulkarni, Youming Qiao, Xiaoming Sun

For a Boolean function $f,$ let $D(f)$ denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine $f.$ In a classic paper,

Rivest and Vuillemin \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to ...
more >>>

Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram

In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if ... more >>>

Joshua Grochow, Youming Qiao

The isomorphism problem for groups given by multiplication tables (GpI) is well-known to be solvable in n^O(log n) time, but only recently has there been significant progress towards polynomial time. For example, in 2012 Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. ... more >>>

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix $M$ whose entries are homogeneous linear polynomials over the integers. Given a linear subspace $\mathcal{B}$ of the $n \times n$ matrices over some field $\mathbb{F}$, we consider ... more >>>

Ankit Gupta, Neeraj Kayal, Youming Qiao

Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial $f$ computed by an unknown/hidden arithmetic formula $\phi$ reconstructs, on the average, an equivalent or smaller formula $\hat{\phi}$ in time polynomial in the size of its output $\hat{\phi}$.

Specifically, we consider arithmetic formulas wherein the ... more >>>

Maurice Jansen, Youming Qiao, Jayalal Sarma

An algebraic branching program (ABP) is given by a directed acyclic graph with source and sink vertices $s$ and $t$, respectively, and where edges are labeled by variables or field constants. An ABP computes the sum of weights of all directed paths from $s$ to $t$, where the weight of ... more >>>

Maurice Jansen, Youming Qiao, Jayalal Sarma

In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation $\pi$ of $n$ variables, for a $\pi$-ordered ABP ($\pi$-OABP), for any directed path $p$ from source to sink, a variable can appear at ... more >>>