All reports by Author Miklos Santha:

__
TR17-123
| 2nd August 2017
__

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs#### Quadratically Tight Relations for Randomized Query Complexity

__
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-103
| 24th July 2013
__

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

__
TR12-063
| 17th May 2012
__

Raghav Kulkarni, Miklos Santha#### Query complexity of matroids

__
TR10-192
| 8th December 2010
__

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao#### Improved bounds for the randomized decision tree complexity of recursive majority

Revisions: 1

__
TR01-014
| 7th February 2001
__

Marcos Kiwi, Frederic Magniez, Miklos Santha#### Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... 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 >>>

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 >>>

Raghav Kulkarni, Miklos Santha

Let $\mathcal{M}$ be a bridgeless matroid on ground set $\{1,\ldots, n\}$ and $f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}$ be the indicator function of its independent sets. A folklore fact is that $f_\mathcal{M}$ is ``evasive," i.e., $D(f_\mathcal{M}) = n$ where $D(f)$ denotes the deterministic decision tree complexity of $f.$ Here we prove ... more >>>

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao

We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture ... more >>>

Marcos Kiwi, Frederic Magniez, Miklos Santha

In the late 80's Blum, Luby, Rubinfeld, Kannan et al. pioneered

the theory of self-testing as an alternative way of dealing with

the problem of software reliability.

Over the last decade this theory played a crucial role in

the construction of probabilistically checkable proofs and

the ...
more >>>