3 citations · 3 across the 6 of their papers we have counts for
4 papers · 1 filter
Nondeterministic Communication Complexity of Random Boolean Functions
Mozhgan Pourmoradnasseri, Dirk Oliver Theis
We study nondeterministic communication complexity and related concepts (fooling sets, fractional covering number) of random functions where each va…
The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
Abdullah Makkeh, Mozhgan Pourmoradnasseri, Dirk Oliver Theis
Graphs (1-skeletons) of Traveling-Salesman-related polytopes have attracted a lot of attention. Pedigree polytopes are extensions of the classical Symmetric Traveling Salesman Prob…
On the Graph of the Pedigree Polytope
Abdullah Makkeh, Mozhgan Pourmoradnasseri, Dirk Oliver Theis
Pedigree polytopes are extensions of the classical Symmetric Traveling Salesman Problem polytopes whose graphs (1-skeletons) contain the TSP polytope graphs as spanning subgraphs.…
The (minimum) rank of typical fooling set matrices
Mozhgan Pourmoradnasseri, Dirk Oliver Theis
A fooling-set matrix has nonzero diagonal, but at least one in every pair of diagonally opposite entries is 0. Dietzfelbinger et al. '96 proved that the rank of such a matrix is at…