All reports by Author Karteek Sreenivasaiah:

__
TR23-014
| 16th February 2023
__

Tameem Choudhury, Karteek Sreenivasaiah#### Depth-3 Circuit Lower Bounds for k-OV

Revisions: 3

__
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

Tameem Choudhury, Karteek Sreenivasaiah

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

Yogesh Dahiya, Vignesh K, Meena Mahajan, Karteek Sreenivasaiah

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