Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with average case:
TR12-033 | 5th April 2012
Ankit Gupta, Neeraj Kayal, Youming Qiao

Random Arithmetic Formulas can be Reconstructed Efficiently

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

TR16-158 | 9th October 2016
Alexander Kulikov, Vladimir Podolskii

Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

We study the following computational problem: for which values of $k$, the majority of $n$ bits $\text{MAJ}_n$ can be computed with a depth two formula whose each gate computes a majority function of at most $k$ bits? The corresponding computational model is denoted by $\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>>

TR21-155 | 13th November 2021
Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

Learning generalized depth-three arithmetic circuits in the non-degenerate case

Consider a homogeneous degree $d$ polynomial $f = T_1 + \cdots + T_s$, $T_i = g_i(\ell_{i,1}, \ldots, \ell_{i, m})$ where $g_i$'s are homogeneous $m$-variate degree $d$ polynomials and $\ell_{i,j}$'s are linear polynomials in $n$ variables. We design a (randomized) learning algorithm that given black-box access to $f$, computes black-boxes for ... more >>>

TR22-020 | 18th February 2022
Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar

Worst-Case to Average-Case Reductions via Additive Combinatorics

We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time $T$ that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time $\widetilde{O}(T)$ that are correct on ... more >>>

ISSN 1433-8092 | Imprint