BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Nitya Mani

Nitya Mani appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COData Structures and AlgorithmsDiscrete Mathematicsmath.NTInformation Theorymath.IT

Catalog footprint

What is connected

8works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2022arXiv

Enumerating k-SAT functions

How many $k$-SAT functions on $n$ boolean variables are there? What does a typical such function look like? Bollobás, Brightwell, and Leader conjectured that, for each fixed $k \ge 2$, the number of $k$-SAT functions on $n$ variables is $(1+o(1))2^{\binom{n}{k} + n}$, or equivalently: a $1-o(1)$ fraction of all $k$-SAT functions are unate, i.e., monotone after negating some variables. They proved a weaker version of the conjecture for $k=2$. The conjecture was confirmed for $k=2$ by Allen and $k=3$ by Ilinca and Kahn. We show that the problem of enumerating $k$-SAT functions is equivalent to a Turán density problem for partially directed hypergraphs. Our proof uses the hypergraph container method. Furthermore, we confirm the Bollobás--Brightwell--Leader conjecture for $k=4$ by solving the corresponding Turán density problem. Our solution applies a recent result of Füredi and Maleki on the minimum triangular edge density in a graph of given edge density. In an appendix (by Nitya Mani and Edward Yu), we further confirm the $k=5$ case of the conjecture via a brute force computer search.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Extremal results on feedback arc sets in digraphs

A directed graph is oriented if it can be obtained by orienting the edges of a simple, undirected graph. For an oriented graph $G$, let $β(G)$ denote the size of a minimum feedback arc set, a smallest subset of edges whose deletion leaves an acyclic subgraph. A simple consequence of a result of Berger and Shor is that any oriented graph $G$ with $m$ edges satisfies $β(G) = m/2 - Ω(m^{3/4})$. We observe that if an oriented graph $G$ has a fixed forbidden subgraph $B$, the upper bound of $β(G) = m/2 - Ω(m^{3/4})$ is best possible as a function of the number of edges if $B$ is not bipartite, but the exponent $3/4$ in the lower order term can be improved if $B$ is bipartite. We also show that for every rational number $r$ between $3/4$ and $1$, there is a finite collection of digraphs $\mathcal{B}$ such that every $\mathcal{B}$-free digraph $G$ with $m$ edges satisfies $β(G) = m/2 - Ω(m^r)$, and this bound is best possible up to the implied constant factor. The proof uses a connection to Turán numbers and a result of Bukh and Conlon. Both of our upper bounds come equipped with randomized linear-time algorithms that construct feedback arc sets achieving those bounds. Finally, we give a characterization of quasirandom directed graphs via minimum feedback arc sets.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

From algorithms to connectivity and back: finding a giant component in random k-SAT

We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree $k$-CNFs for large $k$. In the course of doing so, we establish that with high probability, a random $k$-CNF $Φ$ with $n$ variables and clause density $α= m/n \lesssim 2^{k/6}$ has a giant component of solutions that are connected in a graph where solutions are adjacent if they have Hamming distance $O_k(\log n)$ and that a similar result holds for bounded degree $k$-CNFs at similar densities. We are also able to deduce looseness results for random and bounded degree $k$-CNFs in a similar regime. Although our main motivation was understanding the geometry of the solution space, our methods have algorithmic implications. Towards that end, we construct an idealized block dynamics that samples solutions from a random $k$-CNF $Φ$ with density $α= m/n \lesssim 2^{k/52}$. We show this Markov chain can with high probability be implemented in polynomial time and by leveraging spectral independence, we also observe that it mixes relatively fast, giving a polynomial time algorithm to with high probability sample a uniformly random solution to a random $k$-CNF. Our work suggests that the natural route to pinning down when a giant component exists is to develop sharper algorithms for sampling solutions in random $k$-CNFs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the number of error correcting codes

We show that for a fixed $q$, the number of $q$-ary $t$-error correcting codes of length $n$ is at most $2^{(1 + o(1)) H_q(n,t)}$ for all $t \leq (1 - q^{-1})n - C_q\sqrt{n \log n}$ (for sufficiently large constant $C_q$), where $H_q(n, t) = q^n / V_q(n,t)$ is the Hamming bound and $V_q(n,t)$ is the cardinality of the radius $t$ Hamming ball. This proves a conjecture of Balogh, Treglown, and Wagner, who showed the result for $t = o(n^{1/3} (\log n)^{-2/3})$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming

For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming (SDP), to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with few triangles and in $K_r$-free graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Max-Cut in Degenerate $H$-Free Graphs

We obtain several lower bounds on the $\textsf{Max-Cut}$ of $d$-degenerate $H$-free graphs. Let $f(m,d,H)$ denote the smallest $\textsf{Max-Cut}$ of an $H$-free $d$-degenerate graph on $m$ edges. We show that $f(m,d,K_r)\ge \left(\frac{1}{2} + d^{-1+Ω(r^{-1})}\right)m$, generalizing a recent work of Carlson, Kolla, and Trevisan. We also give bounds on $f(m,d,H)$ when $H$ is a cycle, odd wheel, or a complete bipartite graph with at most 4 vertices on one side. We also show stronger bounds on $f(m,d,K_r)$ assuming a conjecture of Alon, Bollabas, Krivelevich, and Sudakov (2003). We conjecture that $f(m,d,K_r)= \left( \frac{1}{2} + Θ_r(d^{-1/2}) \right)m$ for every $r\ge 3$, and show that this conjecture implies the ABKS conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Infinite Product Exponents for Modular Forms

Recently, D. Choi obtained a description of the coefficients of the infinite product expansions of meromorphic modular forms over $Γ_0(N)$. Using this result, we provide some bounds on these infinite product coefficients for holomorphic modular forms. We give an exponential upper bound for the growth of these coefficients. We show that this bound is also a lower bound in the case that the genus of the associated modular curve $X_0(N)$ is $0$ or $1$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

$N$-Division Points of Hypocycloids

We show that the $n$-division points of all rational hypocycloids are constructible with an unmarked straightedge and compass for all integers $n$, given a pre-drawn hypocycloid. We also consider the question of constructibility of $n$-division points of hypocycloids without a pre-drawn hypocycloid in the case of a tricuspoid, concluding that only the $1$, $2$, $3$, and $6$-division points of a tricuspoid are constructible in this manner.

0 citations0 reviewsNo code linkedOpen access