Zobrazeno 1 - 10
of 23
pro vyhledávání: '"Singer, Noah"'
We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of Buchbinder et al. (FOCS'12) and Censor-Hillel et al. (ALGOSENSORS'17), we develop stre
Externí odkaz:
http://arxiv.org/abs/2411.18829
In the maximum directed cut problem, the input is a directed graph $G=(V,E)$, and the goal is to pick a partition $V = S \cup (V \setminus S)$ of the vertices such that as many edges as possible go from $S$ to $V\setminus S$. Oblivious algorithms, in
Externí odkaz:
http://arxiv.org/abs/2411.12976
Autor:
O'Donnell, Ryan, Singer, Noah G.
Recent major results in property testing~\cite{BLM24,DDL24} and PCPs~\cite{BMV24} were unlocked by moving to high-dimensional expanders (HDXs) constructed from $\widetilde{C}_d$-type buildings, rather than the long-known $\widetilde{A}_d$-type ones.
Externí odkaz:
http://arxiv.org/abs/2411.05916
Autor:
Singer, Noah G.
Motivated by recent works on streaming algorithms for constraint satisfaction problems (CSPs), we define and analyze oblivious algorithms for the Max-$k$AND problem. This generalizes the definition by Feige and Jozeph (Algorithmica '15) of oblivious
Externí odkaz:
http://arxiv.org/abs/2305.04438
Autor:
Singer, Noah G.
In this thesis, we explore streaming algorithms for approximating constraint satisfaction problems (CSPs). The setup is roughly the following: A computer has limited memory space, sees a long "stream" of local constraints on a set of variables, and t
Externí odkaz:
http://arxiv.org/abs/2304.06664
We give an $\widetilde{O}(\sqrt{n})$-space single-pass $0.483$-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on $n$ vertices. This improves over an $O(\log n)$-space $4/9 < 0.45$ approx
Externí odkaz:
http://arxiv.org/abs/2211.03916
We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely $\textsf{Max-DICUT}$, for which random ordering makes a provable differe
Externí odkaz:
http://arxiv.org/abs/2207.07158
A Boolean maximum constraint satisfaction problem, Max-CSP($f$), is specified by a predicate $f:\{-1,1\}^k\to\{0,1\}$. An $n$-variable instance of Max-CSP($f$) consists of a list of constraints, each of which applies $f$ to $k$ distinct literals draw
Externí odkaz:
http://arxiv.org/abs/2112.06319
An ordering constraint satisfaction problem (OCSP) is defined by a family $\mathcal{F}$ of predicates mapping permutations on $\{1,\ldots,k\}$ to $\{0,1\}$. An instance of Max-OCSP($\mathcal{F}$) on $n$ variables consists of a list of constraints, ea
Externí odkaz:
http://arxiv.org/abs/2105.01782
Autor:
Singer, Noah, Sudan, Madhu
Publikováno v:
ACM T. Comput. Thy. 14.2 (2022)
We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in $\mathbb{R}^d$ that is covered by constant-sized sets of parallel hyperplanes, there exists an a
Externí odkaz:
http://arxiv.org/abs/2101.09592