research
∙
07/01/2023
On Finding Constrained Independent Sets in Cycles
A subset of [n] = {1,2,…,n} is called stable if it forms an independent ...
share
research
∙
01/02/2023
Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
The orthogonality dimension of a graph G over ℝ is the smallest integer ...
research
∙
04/19/2022
A Fixed-Parameter Algorithm for the Schrijver Problem
The Schrijver graph S(n,k) is defined for integers n and k with n ≥ 2k a...
research
∙
04/19/2022
The Binary Rank of Circulant Block Matrices
The binary rank of a 0,1 matrix is the smallest size of a partition of i...
research
∙
04/14/2022
A Fixed-Parameter Algorithm for the Kneser Problem
The Kneser graph K(n,k) is defined for integers n and k with n ≥ 2k as t...
research
∙
03/24/2022
On the Binary and Boolean Rank of Regular Matrices
A 0,1 matrix is said to be regular if all of its rows and columns have t...
research
∙
10/02/2021
Local Orthogonality Dimension
An orthogonal representation of a graph G over a field 𝔽 is an assignmen...
research
∙
11/03/2020
The Complexity of Finding Fair Independent Sets in Cycles
Let G be a cycle graph and let V_1,…,V_m be a partition of its vertex se...
research
∙
05/14/2020
Minimizing the alphabet size of erasure codes with restricted decoding sets
A Maximum Distance Separable code over an alphabet F is defined via an e...
research
∙
02/20/2020
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
The orthogonality dimension of a graph G=(V,E) over a field 𝔽 is the sma...
research
∙
06/24/2019
Task-based Solutions to Embedded Index Coding
In the index coding problem a sender holds a message x ∈{0,1}^n and wish...
research
∙
06/12/2019
Approximating the Orthogonality Dimension of Graphs and Hypergraphs
A t-dimensional orthogonal representation of a hypergraph is an assignme...
research
∙
11/28/2018
Topological Bounds on the Dimension of Orthogonal Representations of Graphs
An orthogonal representation of a graph is an assignment of nonzero real...
research
∙
06/11/2018
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
We show that unless ⊆ (2^(n)), there is no polynomial-time algorithm a...
research
∙
06/11/2018
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
In 1991, Papadimitriou and Yannakakis gave a reduction implying the -h...
research
∙
06/02/2018
On Minrank and Forbidden Subgraphs
The minrank over a field F of a graph G on the vertex set {1,2,...,n} is...
research
∙
02/12/2018