A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

**V**

__
TR05-118
| 16th October 2005
__

Jin-Yi Cai, Vinay Choudhary#### Valiant's Holant Theorem and Matchgate Tensors

__
TR04-003
| 22nd December 2003
__

Pascal Koiran#### Valiant's model and the cost of computing integers

__
TR08-063
| 21st April 2008
__

MÃ¼ller Moritz#### Valiant-Vazirani Lemmata for Various Logics

__
TR22-075
| 21st May 2022
__

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan#### Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

Revisions: 1

__
TR19-121
| 17th September 2019
__

Alexander A. Sherstov, Justin Thaler#### Vanishing-Error Approximate Degree and QMA Complexity

__
TR18-135
| 31st July 2018
__

Prasad Chaugule, Nutan Limaye, Aditya Varre#### Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes

Revisions: 1

__
TR20-152
| 7th October 2020
__

Prasad Chaugule, Nutan Limaye, Shourya Pandey#### Variants of the Determinant polynomial and VP-completeness

__
TR21-067
| 6th May 2021
__

Zeyu Guo#### Variety Evasive Subspace Families

Revisions: 1

__
TR95-051
| 16th October 1995
__

Pascal Koiran#### VC Dimension in Circuit Complexity

__
TR95-055
| 24th November 1995
__

Marek Karpinski, Angus Macintyre#### VC Dimension of Sigmoidal and General Pfaffian Networks

__
TR14-039
| 28th March 2014
__

Andrzej Lingas#### Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps :-)

Revisions: 1

__
TR17-005
| 10th January 2017
__

Nir Bitansky#### Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs

Revisions: 3

__
TR14-086
| 11th July 2014
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian#### Verifiable Stream Computation and Arthurâ€“Merlin Communication

__
TR10-159
| 28th October 2010
__

Graham Cormode, Justin Thaler, Ke Yi#### Verifying Computations with Streaming Interactive Proofs

__
TR13-165
| 28th November 2013
__

Michael Walfish, Andrew Blumberg#### Verifying computations without reexecuting them: from theoretical possibility to near-practicality

Revisions: 3

__
TR23-195
| 6th December 2023
__

Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski#### Verifying Groups in Linear Time

__
TR12-079
| 14th June 2012
__

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer#### Verifying Proofs in Constant Depth

__
TR22-052
| 18th April 2022
__

Tal Herman, Guy Rothblum#### Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties

__
TR15-036
| 17th February 2015
__

David Gajser#### Verifying whether One-Tape Turing Machines Run in Linear Time

__
TR01-094
| 3rd December 2001
__

Jonas Holmerin#### Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2 - \epsilon

__
TR02-027
| 30th April 2002
__

Irit Dinur, Venkatesan Guruswami, Subhash Khot#### Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon)

__
TR21-119
| 13th August 2021
__

Omar Alrabiah, Venkatesan Guruswami#### Visible Rank and Codes with Locality

Revisions: 2

__
TR14-177
| 14th December 2014
__

Andreas Krebs, Klaus-Joern Lange, Michael Ludwig#### Visibly Counter Languages and Constant Depth Circuits

__
TR96-012
| 14th December 1995
__

Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson#### Visual Cryptography for General Access Structures

Jin-Yi Cai, Vinay Choudhary

We propose matchgate tensors as a natural and proper language

to develop Valiant's new theory of Holographic Algorithms.

We give a treatment of the central theorem in this theory---the Holant

Theorem---in terms of matchgate tensors.

Some generalizations are presented.

Pascal Koiran

Let $\tau(k)$ be the minimum number of arithmetic operations

required to build the integer $k \in \N$ from the constant 1.

A sequence $x_k$ is said to be ``easy to compute'' if

there exists a polynomial $p$ such that $\tau(x_k) \leq p(\log k)$

for all $k \geq ...
more >>>

MÃ¼ller Moritz

We show analogues of a theorem due to Valiant and Vazirani

for intractable parameterized complexity classes such as W[P], W[SAT]

and the classes of the W-hierarchy as well as those of the A-hierarchy.

We do so by proving a general ``logical'' version of it which may be of

independent interest

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

We study the following natural question on random sets of points in $\mathbb{F}_2^m$:

Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most $r$ multilinear polynomials that vanish on all points in $Z$?

We ... more >>>

Alexander A. Sherstov, Justin Thaler

The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing ... more >>>

Prasad Chaugule, Nutan Limaye, Aditya Varre

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2016). We consider three different variants of graph homomorphisms, namely injective ... more >>>

Prasad Chaugule, Nutan Limaye, Shourya Pandey

The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call $StackDet_n(X)$ and $CountDet_n(X)$ and show that they are VP and VNP complete respectively under $p$-projections. The definitions of the polynomials are inspired by a ... more >>>

Zeyu Guo

We introduce the problem of constructing explicit variety evasive subspace families. Given a family $\mathcal{F}$ of subvarieties of a projective or affine space, a collection $\mathcal{H}$ of projective or affine $k$-subspaces is $(\mathcal{F},\epsilon)$-evasive if for every $\mathcal{V}\in\mathcal{F}$, all but at most $\epsilon$-fraction of $W\in\mathcal{H}$ intersect every irreducible component of $\mathcal{V}$ ... more >>>

Pascal Koiran

The main result of this paper is a Omega(n^{1/4}) lower bound

on the size of a sigmoidal circuit computing a specific AC^0_2 function.

This is the first lower bound for the computation model of sigmoidal

circuits with unbounded weights. We also give upper and lower bounds for

the ...
more >>>

Marek Karpinski, Angus Macintyre

We introduce a new method for proving explicit upper bounds

on the VC Dimension of general functional basis networks,

and prove as an application, for the first time, that the

VC Dimension of analog neural networks with the sigmoidal

activation function $\sigma(y)=1/1+e^{-y}$ ...
more >>>

Andrzej Lingas

We observe that if we allow for the use of

division and the floor function

besides multiplication, addition and

subtraction then we can

compute the arithmetic convolution

of two n-dimensional integer vectors in O(n) steps and

perform the arithmetic matrix multiplication

of two integer n times n matrices ...
more >>>

Nir Bitansky

Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function's value $y$ at any point $x$, can also generate a non-interactive proof $\pi$ that $y$ is correct (relative to so), without compromising pseudorandomness at other points. Being a natural primitive with ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function on a massive stream of data, arriving online, but is unable to store even a small fraction of the data. It outsources the processing to a third party service (prover), but is unwilling ... more >>>

Graham Cormode, Justin Thaler, Ke Yi

Applications based on outsourcing computation require guarantees to the data owner that the desired computation has been performed correctly by the service provider. Methods based on proof systems can give the data owner the necessary assurance, but previous work does not give a sufficiently scalable and practical solution, requiring a ... more >>>

Michael Walfish, Andrew Blumberg

How can we trust results computed by a third party, or the integrity of data stored by such a party? This is a classic question in systems security, and it is particularly relevant in the context of cloud computing.

Various solutions have been proposed that make assumptions about the class ... more >>>

Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski

We consider the following problem: Given an $n \times n$ multiplication table, decide whether it is a Cayley multiplication table of a group. Among deterministic algorithms for this problem, the best known algorithm is implied by F. W. Light's associativity test (1949) and has running time of $O(n^2 \log n)$. ... more >>>

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

Tal Herman, Guy Rothblum

Given i.i.d. samples from an unknown distribution over a large domain $[N]$, approximating several basic quantities, including the distribution's support size, its entropy, and its distance from the uniform distribution, requires $\Theta(N / \log N)$ samples [Valiant and Valiant, STOC 2011].

Suppose, however, that we can interact with a powerful ... more >>>

David Gajser

We discuss the following family of problems, parameterized by integers $C\geq 2$ and $D\geq 1$: Does a given one-tape non-deterministic $q$-state Turing machine make at most $Cn+D$ steps on all computations on all inputs of length $n$, for all $n$?

Assuming a fixed tape and input alphabet, we show that ... more >>>

Jonas Holmerin

We prove that Minimum vertex cover on 4-regular hyper-graphs (or

in other words, hitting set where all sets have size exactly 4),

is hard to approximate within 2 - \epsilon.

We also prove that the maximization version, in which we

are allowed to pick ...
more >>>

Irit Dinur, Venkatesan Guruswami, Subhash Khot

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is

to find a minimum subset of vertices that ``hits'' every edge. We

show that for every integer $k \geq 5$, E$k$-Vertex-Cover is

NP-hard to approximate within a factor of $(k-3-\epsilon)$, for

an arbitrarily small constant $\epsilon > 0$.

This almost matches the ... more >>>

Omar Alrabiah, Venkatesan Guruswami

We propose a framework to study the effect of local recovery requirements of codeword symbols on the dimension of linear codes, based on a combinatorial proxy that we call "visible rank." The locality constraints of a linear code are stipulated by a matrix $H$ of $\star$'s and $0$'s (which we ... more >>>

Andreas Krebs, Klaus-Joern Lange, Michael Ludwig

We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC0, and show that they are contained in FO[+].

more >>>Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson

A visual cryptography scheme for a

set $\cal P $ of $n$ participants is a method to encode a secret

image $SI$ into $n$ shadow images called shares, where each participant in

$\cal P$ receives one share. Certain qualified subsets of participants

can ``visually'' recover the secret image, but

other, ...
more >>>