6 Search Results for "Shokrollahi, Amin"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.33
Bit-Fixing Extractors for Almost-Logarithmic Entropy

Authors: Dean Doron and Ori Fridman

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

Abstract
An oblivious bit-fixing source is a distribution over {0,1}ⁿ, where k bits are uniform and independent and the rest n-k are fixed a priori to some constant value. Extracting (close to) true randomness from an oblivious bit-fixing source has been studied since the 1980s, with applications in cryptography and complexity theory. We construct explicit extractors for oblivious bit-fixing source that support k = Õ(log n), outputting almost all the entropy with low error. The previous state-of-the-art construction that outputs many bits is due to Rao [Rao, CCC '09], and requires entropy k ≥ log^{c} n for some large constant c. The two key components in our constructions are new low-error affine condensers for poly-logarithmic entropies (that we achieve using techniques from the nonmalleable extractors literature), and a dual use of linear condensers for OBF sources.
Cite as

Dean Doron and Ori Fridman. Bit-Fixing Extractors for Almost-Logarithmic Entropy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2025.33,
  author =	{Doron, Dean and Fridman, Ori},
  title =	{{Bit-Fixing Extractors for Almost-Logarithmic Entropy}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{33:1--33:19},
  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.33},
  URN =		{urn:nbn:de:0030-drops-243994},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.33},
  annote =	{Keywords: Seedless extractors, oblivious bit-fixing sources}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.62
Faster Algorithms on Linear Delta-Matroids

Authors: Tomohiro Koana and Magnus Wahlström

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

Abstract
We present new algorithms and constructions for linear delta-matroids. Delta-matroids are generalizations of matroids that also capture structures such as matchable vertex sets in graphs and path-packing problems. As with matroids, an important class of delta-matroids is given by linear delta-matroids, which generalize linear matroids and are represented via a "twist" of a skew-symmetric matrix. We observe an alternative representation, termed a contraction representation over a skew-symmetric matrix. This representation is equivalent to the more standard twist representation up to O(n^ω)-time transformations (where n is the dimension of the delta-matroid and ω < 2.372 the matrix multiplication exponent), but it is much more convenient for algorithmic tasks. For instance, the problem of finding a max-weight feasible set now reduces directly to finding a max-weight basis in a linear matroid. Supported by this representation, we provide new algorithms and constructions for linear delta-matroids. In particular, we show that the union and delta-sum of linear delta-matroids are again linear delta-matroids, and that a representation for the resulting delta-matroid can be constructed in randomized time O(n^ω) (or more precisely, in O(n^ω) field operations, over a field of size at least Ω(n⋅(1/ε)), where ε > 0 is an error parameter). Previously, it was only known that these operations define delta-matroids. We also note that every projected linear delta-matroid can be represented as an elementary projection. This implies that several optimization problems over (projected) linear delta-matroids, including the coverage, delta-coverage, and parity problems, reduce (in their decision versions) to a single O(n^ω)-time matrix rank computation. Using the methods of Harvey, previously applied by Cheung, Lao and Leung for linear matroid parity, we furthermore show how to solve the search versions in the same time. This improves on the O(n⁴)-time augmenting path algorithm of Geelen, Iwata and Murota, albeit with randomization. Finally, we consider the maximum-cardinality delta-matroid intersection problem (equivalently, the maximum-cardinality delta-matroid matching problem). Using Storjohann’s algorithms for symbolic determinants, we show that such a solution can be found in O(n^{ω+1}) time. This provides the first (randomized) polynomial-time solution for the problem, thereby solving an open question of Kakimura and Takamatsu.
Cite as

Tomohiro Koana and Magnus Wahlström. Faster Algorithms on Linear Delta-Matroids. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.STACS.2025.62,
  author =	{Koana, Tomohiro and Wahlstr\"{o}m, Magnus},
  title =	{{Faster Algorithms on Linear Delta-Matroids}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{62:1--62:19},
  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.62},
  URN =		{urn:nbn:de:0030-drops-228876},
  doi =		{10.4230/LIPIcs.STACS.2025.62},
  annote =	{Keywords: Delta-matroids, Randomized algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.64
A Universal Sequence of Tensors for the Asymptotic Rank Conjecture

Authors: Petteri Kaski and Mateusz Michałek

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
The exponent σ(T) of a tensor T ∈ 𝔽^d⊗𝔽^d⊗𝔽^d over a field 𝔽 captures the base of the exponential growth rate of the tensor rank of T under Kronecker powers. Tensor exponents are fundamental from the standpoint of algorithms and computational complexity theory; for example, the exponent ω of square matrix multiplication can be characterized as ω = 2σ(MM₂), where MM₂ ∈ 𝔽⁴⊗𝔽⁴⊗𝔽⁴ is the tensor that represents 2×2 matrix multiplication. Strassen [FOCS 1986] initiated a duality theory for spaces of tensors that enables one to characterize the exponent of a tensor via objects in a dual space, called the asymptotic spectrum of the primal (tensor) space. While Strassen’s theory has considerable generality beyond the setting of tensors - Wigderson and Zuiddam [Asymptotic Spectra: Theory, Applications, and Extensions, preprint, 2023] give a recent exposition - progress in characterizing the dual space in the tensor setting has been slow, with the first universal points in the dual identified by Christandl, Vrana, and Zuiddam [J. Amer. Math. Soc. 36 (2023)]. In parallel to Strassen’s theory, the algebraic geometry community has developed a geometric theory of tensors aimed at characterizing the structure of the primal space and tensor exponents therein; the latter study was motivated in particular by an observation of Strassen (implicit in [J. Reine Angew. Math. 384 (1988)]) that matrix-multiplication tensors have limited universality in the sense that σ(𝔽^d⊗𝔽^d⊗𝔽^d) ≤ 2ω/3 = 4/3σ(MM₂) holds for all d ≥ 1. In particular, this limited universality of the tensor MM₂ puts forth the question whether one could construct explicit universal tensors that exactly characterize the worst-case tensor exponent in the primal space. Such explicit universal objects would, among others, give means towards a proof or a disproof of Strassen’s asymptotic rank conjecture [Progr. Math. 120 (1994)]; the former would immediately imply ω = 2 and, among others, refute the Set Cover Conjecture (cf. Björklund and Kaski [STOC 2024] and Pratt [STOC 2024]). Our main result is an explicit construction of a sequence 𝒰_d of zero-one-valued tensors that is universal for the worst-case tensor exponent; more precisely, we show that σ(𝒰_d) = σ(d) where σ(d) = sup_{T ∈ 𝔽^d⊗𝔽^d⊗𝔽^d}σ(T). We also supply an explicit universal sequence 𝒰_Δ localised to capture the worst-case exponent σ(Δ) of tensors with support contained in Δ ⊆ [d]×[d]×[d]; by combining such sequences, we obtain a universal sequence 𝒯_d such that σ(𝒯_d) = 1 holds if and only if Strassen’s asymptotic rank conjecture holds for d. Finally, we show that the limit lim_{d → ∞}σ(d) exists and can be captured as lim_{d → ∞} σ(D_d) for an explicit sequence (D_d)_{d = 1}^∞ of tensors obtained by diagonalisation of the sequences 𝒰_d. As our second result we relate the absence of polynomials of fixed degree vanishing on tensors of low rank, or more generally asymptotic rank, with upper bounds on the exponent σ(d). Using this technique, one may bound asymptotic rank for all tensors of a given format, knowing enough specific tensors of low asymptotic rank.
Cite as

Petteri Kaski and Mateusz Michałek. A Universal Sequence of Tensors for the Asymptotic Rank Conjecture. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 64:1-64:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kaski_et_al:LIPIcs.ITCS.2025.64,
  author =	{Kaski, Petteri and Micha{\l}ek, Mateusz},
  title =	{{A Universal Sequence of Tensors for the Asymptotic Rank Conjecture}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{64:1--64:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.64},
  URN =		{urn:nbn:de:0030-drops-226925},
  doi =		{10.4230/LIPIcs.ITCS.2025.64},
  annote =	{Keywords: asymptotic rank conjecture, secant variety, Specht module, tensor rank, tensor exponent}
}
Document
DOI: 10.4230/DagRep.1.11.50
Coding Theory (Dagstuhl Seminar 11461)

Authors: Joachim Rosenthal, M. Amin Shokrollahi, and Judy L. Walker

Published in: Dagstuhl Reports, Volume 1, Issue 11 (2012)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11461 ``Coding Theory''. A (channel) code is typically a set of vectors of the same length n over a finite alphabet \Sigma. By choosing a fixed codebook, binary strings of appropriate length are injectively mapped into the elements of the code. These elements are then transmitted over a communications channel which induces errors on the codeword. Depending on how well the original code is designed, and which algorithms are used, the result of this transmission and attempts to recover the original vector after transmission can be anywhere between disastrous to excellent. Coding theory is all about the design of excellent codes as a function of the communications channel, and the design of efficient algorithms for choosing the codebook vectors, and more importantly, for recovering the original vector after transmission. As such, successful design of codes requires knowledge and tools in a number of areas such as combinatorics, algorithms design, probability theory and complexity theory, to name a few. The purpose of this workshop is to bring together researchers in the field to discuss recent theoretical advances in algebraic coding, codes on graphs, and network coding, as well as new and emerging applications of coding methods to real-world problems.
Cite as

Joachim Rosenthal, M. Amin Shokrollahi, and Judy L. Walker. Coding Theory (Dagstuhl Seminar 11461). In Dagstuhl Reports, Volume 1, Issue 11, pp. 50-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{rosenthal_et_al:DagRep.1.11.50,
  author =	{Rosenthal, Joachim and Shokrollahi, M. Amin and Walker, Judy L.},
  title =	{{Coding Theory (Dagstuhl Seminar 11461)}},
  pages =	{50--65},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{11},
  editor =	{Rosenthal, Joachim and Shokrollahi, M. Amin and Walker, Judy L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.11.50},
  URN =		{urn:nbn:de:0030-drops-33770},
  doi =		{10.4230/DagRep.1.11.50},
  annote =	{Keywords: Algebraic coding theory, complexity theory, cryptography, graph theory, graph based codes, information theory, randomized algorithms, networking}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1817
Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties

Authors: Mahdi Cheraghchi and Amin Shokrollahi

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We consider the problem of uniform sampling of points on an algebraic variety. Specifically, we develop a randomized algorithm that, given a small set of multivariate polynomials over a sufficiently large finite field, produces a common zero of the polynomials almost uniformly at random. The statistical distance between the output distribution of the algorithm and the uniform distribution on the set of common zeros is polynomially small in the field size, and the running time of the algorithm is polynomial in the description of the polynomials and their degrees provided that the number of the polynomials is a constant.
Cite as

Mahdi Cheraghchi and Amin Shokrollahi. Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 277-288, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{cheraghchi_et_al:LIPIcs.STACS.2009.1817,
  author =	{Cheraghchi, Mahdi and Shokrollahi, Amin},
  title =	{{Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{277--288},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1817},
  URN =		{urn:nbn:de:0030-drops-18174},
  doi =		{10.4230/LIPIcs.STACS.2009.1817},
  annote =	{Keywords: Uniform sampling, Algebraic varieties, Randomized algorithms, Computational complexity}
}
Document
DOI: 10.4230/DagSemProc.08301.1
08301 Final Report – Group Testing in the Life Sciences

Authors: Alexander Schliep, Nicolas Thierry-Mieg, and Amin Shokrollahi

Published in: Dagstuhl Seminar Proceedings, Volume 8301, Group Testing in the Life Sciences (2008)

Abstract
Group testing AKA smart-pooling is a general strategy for minimizing the number of tests necessary for identifying positives among a large collection of items. It has the potential to efficiently identify and correct for experimental errors (false–positives and false–negatives). It can be used whenever tests can detect the presence of a positive in a group (or pool) of items, provided that positives are rare. Group testing has numerous applications in the life sciences, such as physical mapping, interactome mapping, drug–resistance screening, or designing DNA-microarrays, and many connections to computer science, mathematics and communications, from error-correcting codes to combinatorial design theory and to statistics. The seminar brought together researchers representing the different communities working on group testing and experimentalists from the life sciences. The desired outcome of the seminar was a better understanding of the requirements for and the possibilities of group testing in the life sciences.
Cite as

Alexander Schliep, Nicolas Thierry-Mieg, and Amin Shokrollahi. 08301 Final Report – Group Testing in the Life Sciences. In Group Testing in the Life Sciences. Dagstuhl Seminar Proceedings, Volume 8301, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{schliep_et_al:DagSemProc.08301.1,
  author =	{Schliep, Alexander and Thierry-Mieg, Nicolas and Shokrollahi, Amin},
  title =	{{08301 Final Report – Group Testing in the Life Sciences}},
  booktitle =	{Group Testing in the Life Sciences},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8301},
  editor =	{Alexander Schliep and Amin Shokrollahi and Nicolas Thierry-Mieg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08301.1},
  URN =		{urn:nbn:de:0030-drops-17806},
  doi =		{10.4230/DagSemProc.08301.1},
  annote =	{Keywords: Group Testing, Pooling, Combinatorics, Design Theory, Error correcting}
}
  • Refine by Type
  • 6 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2012
  • 1 2009
  • 1 2008

  • Refine by Author
  • 2 Shokrollahi, Amin
  • 1 Cheraghchi, Mahdi
  • 1 Doron, Dean
  • 1 Fridman, Ori
  • 1 Kaski, Petteri
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 DagRep
  • 1 DagSemProc

  • Refine by Classification
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Matroids and greedoids
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Expander graphs and randomness extractors

  • Refine by Keyword
  • 2 Randomized algorithms
  • 1 Algebraic coding theory
  • 1 Algebraic varieties
  • 1 Combinatorics
  • 1 Computational complexity
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact