Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Karteek Sreenivasaiah:

TR23-014 | 16th February 2023
Tameem Choudhury, Karteek Sreenivasaiah

Depth-3 Circuit Lower Bounds for k-OV

The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples $A$ and $B$ of $n$ vectors each of dimension $d$, decide if there exists a vector $u\in A$, and $v\in B$ such that $u$ and $v$ are orthogonal. This problem, and its generalization $k$-OV defined analogously for $k$ tuples, ... more >>>

TR23-012 | 16th February 2023
Yogesh Dahiya, Vignesh K, Meena Mahajan, Karteek Sreenivasaiah

Linear threshold functions in decision lists, decision trees, and depth-2 circuits

We show that polynomial-size constant-rank linear decision trees (LDTs) can be converted to polynomial-size depth-2 threshold circuits LTF$\circ$LTF. An intermediate construct is polynomial-size decision lists that query a conjunction of a constant number of linear threshold functions (LTFs); we show that these are equivalent to polynomial-size exact linear decision lists ... more >>>

ISSN 1433-8092 | Imprint