10 Search Results for "Boppana, Ravi"

Document
DOI: 10.4230/LIPIcs.STACS.2026.28
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank

Authors: Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Arina Smirnova

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform (algorithm) lower bounds and nonuniform (circuit) lower bounds in restricted circuit models. About a decade ago, Williams (STOC 2010) showed how to derive nonuniform lower bounds from uniform upper bounds: roughly, by designing a fast algorithm for checking satisfiability of circuits, one gets a lower bound for this circuit class. Since then, a number of results of this kind have been proved. For example, Jahanjou et al. (ICALP 2015) and Carmosino et al. (ITCS 2016) proved that if NSETH fails, then E^{NP} has series-parallel circuit size ω(n). One can also derive nonuniform lower bounds from nondeterministic uniform lower bounds. Perhaps the most well-known example is the Karp-Lipton theorem (STOC 1980): if Σ₂ ≠ Π₂, then NP ⊄ P/poly. Some recent examples include the following. Nederlof (STOC 2020) proved a lower bound on the matrix multiplication tensor rank under an assumption that TSP cannot be solved faster than in 2ⁿ time. Belova et al. (SODA 2024) proved that there exists an explicit polynomial family of arithmetic circuit size Ω(n^{δ}), for any δ > 0, assuming that MAX-3-SAT cannot be solved faster than in 2ⁿ nondeterministic time. Williams (FOCS 2024) proved an exponential lower bound for ETHR ∘ ETHR circuits under the Orthogonal Vectors conjecture. Whereas all the lower bounds above are proved under strong assumptions that might eventually be refuted, the revealed connections are of great interest and may still give further insights: one may be able to weaken the used assumptions or to construct generators from other fine-grained reductions. In this paper, we continue developing this line of research and show how uniform nondeterministic lower bounds can be used to construct generators of various types of combinatorial objects that are notoriously hard to analyze: Boolean functions of high circuit size, matrices of high rigidity, and tensors of high rank. Specifically, we prove the following. - If, for some ε and k, k-SAT cannot be solved in input-oblivious co-nondeterministic time O(2^{(1/2+ε)n}), then there exists a monotone Boolean function family in coNP of monotone circuit size 2^{Ω(n / log n)}. Combining this with the result above, we get win-win circuit lower bounds: either E^{NP{}} requires series-parallel circuits of size ω(n) or coNP requires monotone circuits of size 2^{Ω(n / log n)}. - If, for all ε > 0, MAX-3-SAT cannot be solved in co-nondeterministic time O(2^{(1 - ε)n}), then there exist small families of matrices with rigidity exceeding the best known constructions as well as small families of three-dimensional tensors of rank n^{1+Δ}, for some Δ > 0.
Cite as

Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Arina Smirnova. Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chukhin_et_al:LIPIcs.STACS.2026.28,
  author =	{Chukhin, Nikolai and Kulikov, Alexander S. and Mihajlin, Ivan and Smirnova, Arina},
  title =	{{Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{28:1--28:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.28},
  URN =		{urn:nbn:de:0030-drops-255177},
  doi =		{10.4230/LIPIcs.STACS.2026.28},
  annote =	{Keywords: computational complexity, circuit complexity, lower bounds, conditional lower bounds, monotone circuits, matrix rigidity, tensor rank, arithmetic circuits, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.66
Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds

Authors: Yupan Liu

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We investigate the computational hardness of estimating the quantum α-Rényi entropy S^𝚁_α(ρ) = (ln Tr(ρ^α))/(1-α) and the quantum q-Tsallis entropy S^𝚃_q(ρ) = (1-Tr(ρ^q))/(q-1), both converging to the von Neumann entropy as the order approaches 1. The promise problems Quantum α-Rényi Entropy Approximation (RényiQEA_α) and Quantum q-Tsallis Entropy Approximation (TsallisQEA_q) ask whether S^𝚁_α(ρ) or S^𝚃_q(ρ), respectively, is at least τ_Y or at most τ_N, where τ_Y - τ_N is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 1) and some cases of the quantum q-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real orders, the rank-2 variants Rank2RényiQEA_α and Rank2TsallisQEA_q are BQP-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), our results imply: - For all real order α > 0 and 0 < q ≤ 1, LowRankRényiQEA_α and LowRankTsallisQEA_q are BQP-complete, where both are restricted versions of RényiQEA_α and TsallisQEA_q with ρ of polynomial rank. - For all real order q > 1, TsallisQEA_q is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the α-Rényi or q-Tsallis binary entropies of different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.
Cite as

Yupan Liu. Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 66:1-66:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.STACS.2026.66,
  author =	{Liu, Yupan},
  title =	{{Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{66:1--66:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.66},
  URN =		{urn:nbn:de:0030-drops-255550},
  doi =		{10.4230/LIPIcs.STACS.2026.66},
  annote =	{Keywords: computational hardness, quantum state testing, quantum R\'{e}nyi entropy, quantum Tsallis entropy, von Neumann entropy}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.73
Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

Authors: Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We construct a family of distributions {𝒟_n}_n with 𝒟_n over {0, 1}ⁿ and a family of depth-7 quantum circuits {C_n}_n such that 𝒟_n is produced exactly by C_n with the all zeros state as input, yet any constant-depth classical circuit with bounded fan-in gates evaluated on any binary product distribution has total variation distance 1 - e^{-Ω(n)} from 𝒟_n. Moreover, the quantum circuits we construct are geometrically local and use a relatively standard gate set: Hadamard, controlled-phase, CNOT, and Toffoli gates. All previous separations of this type suffer from some undesirable constraint on the classical circuit model or the quantum circuits witnessing the separation. Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on the work of Bravyi, Gosset, and König (Science, 2018) to separate shallow quantum and classical circuits for relational problems.
Cite as

Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu. Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grier_et_al:LIPIcs.ITCS.2026.73,
  author =	{Grier, Daniel and Kane, Daniel M. and Morris, Jackson and Ostuni, Anthony and Wu, Kewen},
  title =	{{Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{73:1--73:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.73},
  URN =		{urn:nbn:de:0030-drops-253607},
  doi =		{10.4230/LIPIcs.ITCS.2026.73},
  annote =	{Keywords: Shallow circuits, sampling, quantum circuits}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.54
Brief Announcement: Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs

Authors: Salwa Faour and Fabian Kuhn

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
The maximum independent set problem is a classic optimization problem in graph theory that has also been studied quite intensively in the distributed setting. Although the problem is hard to approximate within reasonable factors in general, there are good approximation algorithms known for several sparse graph families. In the present paper, we consider deterministic distributed CONGEST algorithms for the weighted version of the problem in trees and graphs of bounded arboricity (i.e., hereditary sparse graphs). For trees, we prove that the task of deterministically computing a (1-ε)-approximate solution to the maximum weight independent set (MWIS) problem has a tight Θ(log^*(n) / ε) complexity. The lower bound already holds on unweighted oriented paths. On the upper bound side, we show that the bound can be achieved even in unrooted trees. For graphs G = (V,E) of arboricity β > 1, we give two algorithms. If the sum of all node weights is w(V), we show that for any ε > 0, an independent set of weight at least (1-ε)⋅(w(V))/(4β) can be computed in O(log²(β/ε)/ε + log^* n) rounds. This result is obtained by a direct application of the local rounding framework of Faour, Ghaffari, Grunau, Kuhn, and Rozhoň [SODA ‘23]. We further show that for any ε > 0, an independent set of weight at least (1-ε)⋅(w(V))/(2β+1) can be computed in O(log³(β)⋅log(1/ε)/ε² ⋅log n) rounds. For ε = ω(1/√{β}), this significantly improves on a recent result of Gil [OPODIS ‘23], who showed that a 1/⌊(2+ε)β⌋-approximation to the MWIS problem can be computed in O(β/ε⋅log n) rounds. As an intermediate step to our result, we design an algorithm to compute an independent set of total weight at least (1-ε)⋅∑_{v ∈ V}(w(v))/(deg(v)+1) in time O(log³(Δ)⋅log(1/ε)/ε + log^* n), where Δ is the maximum degree of the graph.
Cite as

Salwa Faour and Fabian Kuhn. Brief Announcement: Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 54:1-54:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{faour_et_al:LIPIcs.DISC.2025.54,
  author =	{Faour, Salwa and Kuhn, Fabian},
  title =	{{Brief Announcement: Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{54:1--54:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.54},
  URN =		{urn:nbn:de:0030-drops-248704},
  doi =		{10.4230/LIPIcs.DISC.2025.54},
  annote =	{Keywords: CONGEST model, weighted independent set, approximation, trees, arboricity}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.25
The Exchange Problem

Authors: Mohit Garg and Suneel Sarswat

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
Auctions are widely used in exchanges to match buy and sell requests. Once the buyers and sellers place their requests, the exchange determines how these requests are to be matched. The two most popular objectives used while determining the matching are maximizing volume with dynamic pricing and maximizing volume at a uniform price. In this work, we study the algorithmic complexity of the problems arising from these matching tasks. For dynamic-price matching, we establish a lower bound of Ω(n log n) on the running time, thereby proving that the currently best-known O(n log n) algorithm is time-optimal. In contrast, for uniform-price matching, we present a linear-time algorithm, improving upon previous methods that require O(n log n) time to match n requests.
Cite as

Mohit Garg and Suneel Sarswat. The Exchange Problem. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.AFT.2025.25,
  author =	{Garg, Mohit and Sarswat, Suneel},
  title =	{{The Exchange Problem}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.25},
  URN =		{urn:nbn:de:0030-drops-247449},
  doi =		{10.4230/LIPIcs.AFT.2025.25},
  annote =	{Keywords: Exchanges, Double Auctions, Matching Algorithms, Element Distinctness, Time Complexity}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.11
On Finding Randomly Planted Cliques in Arbitrary Graphs

Authors: Francesco Agrimonti, Marco Bressan, and Tommaso d'Orsi

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study a planted clique model introduced by Feige [Uriel Feige, 2021] where a complete graph of size c⋅ n is planted uniformly at random in an arbitrary n-vertex graph. We give a simple deterministic algorithm that, in almost linear time, recovers a clique of size (c/3)^O(1/c) ⋅ n as long as the original graph has maximum degree at most (1-p)n for some fixed p > 0. The proof hinges on showing that the degrees of the final graph are correlated with the planted clique, in a way similar to (but more intricate than) the classical G(n,1/2)+K_√n planted clique model. Our algorithm suggests a separation from the worst-case model, where, assuming the Unique Games Conjecture, no polynomial algorithm can find cliques of size Ω(n) for every fixed c > 0, even if the input graph has maximum degree (1-p)n. Our techniques extend beyond the planted clique model. For example, when the planted graph is a balanced biclique, we recover a balanced biclique of size larger than the best guarantees known for the worst case.
Cite as

Francesco Agrimonti, Marco Bressan, and Tommaso d'Orsi. On Finding Randomly Planted Cliques in Arbitrary Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{agrimonti_et_al:LIPIcs.APPROX/RANDOM.2025.11,
  author =	{Agrimonti, Francesco and Bressan, Marco and d'Orsi, Tommaso},
  title =	{{On Finding Randomly Planted Cliques in Arbitrary Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.11},
  URN =		{urn:nbn:de:0030-drops-243774},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.11},
  annote =	{Keywords: Computational Complexity, Planted Clique, Semi-random, Unique Games Conjecture, Approximation Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.115
On the Complexity of Hazard-Free Formulas

Authors: Leah London Arazi and Amir Shpilka

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
This paper studies the hazard-free formula complexity of Boolean functions. Our first result shows that unate functions are the only Boolean functions for which the monotone formula complexity of the hazard-derivative equals the hazard-free formula complexity of the function itself. Consequently, they are the only functions for which the hazard-derivative approach of Ikenmeyer et al. (J. ACM, 2019) yields optimal bounds. Our second result proves that the hazard-free formula complexity of a uniformly random Boolean function is at most 2^{(1+o(1))n}. Prior to this, no better upper bound than O(3ⁿ) was known. Notably, unlike in the general case of Boolean circuits and formulas, where the typical complexity is derived from that of the multiplexer function with n-bit selector, the hazard-free formula complexity of a random function is smaller than the optimal hazard-free formula for the multiplexer by an exponential factor in n. We provide two proofs of this fact. The first is direct, bounding the number of prime implicants of a random Boolean function and using this bound to construct a DNF of the claimed size. The second introduces a new and independently interesting result: a weak converse to the hazard-derivative lower bound method, which gives an upper bound on the hazard-free complexity of a function in terms of the monotone complexity of a subset of its hazard-derivatives. Additionally, we explore the hazard-free formula complexity of block composition of Boolean functions and obtain a result in the hazard-free setting that is analogous to a result of Karchmer, Raz, and Wigderson (Computational Complexity, 1995) in the monotone setting. We show that our result implies a stronger lower bound on the hazard-free formula depth of the block composition of the set covering function with the multiplexer function than the bound obtained via the hazard-derivative method.
Cite as

Leah London Arazi and Amir Shpilka. On the Complexity of Hazard-Free Formulas. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 115:1-115:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{londonarazi_et_al:LIPIcs.ICALP.2025.115,
  author =	{London Arazi, Leah and Shpilka, Amir},
  title =	{{On the Complexity of Hazard-Free Formulas}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{115:1--115:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.115},
  URN =		{urn:nbn:de:0030-drops-234920},
  doi =		{10.4230/LIPIcs.ICALP.2025.115},
  annote =	{Keywords: Hazard-free computation, Boolean formulas, monotone formulas, Karchmer-Wigderson games, communication complexity, lower bounds}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICDT.2025.1
The Quest for Faster Join Algorithms (Invited Talk)

Authors: Paraschos Koutris, Shaleen Deep, Austen Fan, and Hangdong Zhao

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
Joins are the cornerstone of relational databases. Surprisingly, even after several decades of research in the systems and theory database community, we still lack an understanding of how to design the fastest possible join algorithm. In this talk, we will present the exciting progress the database theory community has achieved in join algorithms over the last two decades. The talk will revolve around five key ideas fundamentally shaping this research area: tree decompositions, data partitioning, leveraging statistical information, enumeration, and algebraic techniques.
Cite as

Paraschos Koutris, Shaleen Deep, Austen Fan, and Hangdong Zhao. The Quest for Faster Join Algorithms (Invited Talk). In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 1:1-1:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koutris_et_al:LIPIcs.ICDT.2025.1,
  author =	{Koutris, Paraschos and Deep, Shaleen and Fan, Austen and Zhao, Hangdong},
  title =	{{The Quest for Faster Join Algorithms}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{1:1--1:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.1},
  URN =		{urn:nbn:de:0030-drops-229428},
  doi =		{10.4230/LIPIcs.ICDT.2025.1},
  annote =	{Keywords: Conjunctive Queries, Joins, Tree Decompositions, Enumeration, Semirings}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2025.4
Some Recent Advancements in Monotone Circuit Complexity (Invited Talk)

Authors: Susanna F. de Rezende

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In 1985, Razborov [Razborov, 1985] proved the first superpolynomial size lower bound for monotone Boolean circuits for the perfect matching the clique functions, and, independently, Andreev [Andreev, 1985] obtained exponential size lower bounds. These breakthroughs were soon followed by further advancements in monotone complexity, including better lower bounds for clique [Alon and Boppana, 1987; Ingo Wegener, 1987], superlogarithmic depth lower bounds for connectivity by Karchmer and Wigderson [Karchmer and Wigderson, 1990], and the separations mon-NC ≠ mon-P and that mon-NC^i ≠ mon-NC^{i+1} by Raz and McKenzie [Ran Raz and Pierre McKenzie, 1999]. Karchmer and Wigderson [Karchmer and Wigderson, 1990] proved their result by establishing a relation between communication complexity and (monotone) circuit depth, and Raz and McKenzie [Ran Raz and Pierre McKenzie, 1999] introduced a new technique, now called lifting theorems, for obtaining communication lower bounds from query complexity lower bounds, In this talk, we will survey recent advancements in monotone complexity driven by query-to-communication lifting theorems. A decade ago, Göös, Pitassi, and Watson [Mika Göös et al., 2018] brought to light the generality of the result of Raz and McKenzie [Ran Raz and Pierre McKenzie, 1999] and reignited this line of work. A notable extension is the lifting theorem [Ankit Garg et al., 2020] for a model of DAG-like communication [Alexander A. Razborov, 1995; Dmitry Sokolov, 2017] that corresponds to circuit size. These powerful theorems, in their different flavours, have been instrumental in addressing many open questions in monotone circuit complexity, including: optimal 2^Ω(n) lower bounds on the size of monotone Boolean formulas computing an explicit function in NP [Toniann Pitassi and Robert Robere, 2017]; a complete picture of the relation between the mon-AC and mon-NC hierarchies [Susanna F. de Rezende et al., 2016]; a near optimal separation between monotone circuit and monotone formula size [Susanna F. de Rezende et al., 2020]; exponential separation between NC^2 and mon-P [Ankit Garg et al., 2020; Mika Göös et al., 2019]; and better lower bounds for clique [de Rezende and Vinyals, 2025; Lovett et al., 2022], improving on [Cavalar et al., 2021]. Very recently, lifting theorems were also used to prove supercritical trade-offs for monotone circuits showing that there are functions computable by small circuits for which any small circuit must have superlinear or even superpolynomial depth [de Rezende et al., 2024; Göös et al., 2024]. We will explore these results and their implications, and conclude by discussing some open problems.
Cite as

Susanna F. de Rezende. Some Recent Advancements in Monotone Circuit Complexity (Invited Talk). In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 4:1-4:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derezende:LIPIcs.STACS.2025.4,
  author =	{de Rezende, Susanna F.},
  title =	{{Some Recent Advancements in Monotone Circuit Complexity}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{4:1--4:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.4},
  URN =		{urn:nbn:de:0030-drops-228291},
  doi =		{10.4230/LIPIcs.STACS.2025.4},
  annote =	{Keywords: monotone circuit complexity, query complexity, lifting theorems}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.24
Bounded Independence vs. Moduli

Authors: Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
Let k = k(n) be the largest integer such that there exists a k-wise uniform distribution over {0,1}^n that is supported on the set S_m := {x in {0,1}^n: sum_i x_i equiv 0 mod m}, where m is any integer. We show that Omega(n/m^2 log m) <= k <= 2n/m + 2. For k = O(n/m) we also show that any k-wise uniform distribution puts probability mass at most 1/m + 1/100 over S_m. For any fixed odd m there is k \ge (1 - Omega(1))n such that any k-wise uniform distribution lands in S_m with probability exponentially close to |S_m|/2^n; and this result is false for any even m.
Cite as

Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola. Bounded Independence vs. Moduli. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 24:1-24:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{boppana_et_al:LIPIcs.APPROX-RANDOM.2016.24,
  author =	{Boppana, Ravi and H\r{a}stad, Johan and Lee, Chin Ho and Viola, Emanuele},
  title =	{{Bounded Independence vs. Moduli}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{24:1--24:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.24},
  URN =		{urn:nbn:de:0030-drops-66475},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.24},
  annote =	{Keywords: Bounded independence, Modulus}
}
  • Refine by Type
  • 10 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 6 2025
  • 1 2016

  • Refine by Author
  • 1 Agrimonti, Francesco
  • 1 Boppana, Ravi
  • 1 Bressan, Marco
  • 1 Chukhin, Nikolai
  • 1 Deep, Shaleen
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Circuit complexity
  • 2 Theory of computation → Communication complexity
  • 2 Theory of computation → Quantum complexity theory
  • 1 Applied computing → Electronic commerce
  • 1 Mathematics of computing → Approximation algorithms
  • Show More...

  • Refine by Keyword
  • 2 lower bounds
  • 1 Approximation Algorithms
  • 1 Boolean formulas
  • 1 Bounded independence
  • 1 CONGEST model
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact